Top.Mail.Ru
Ответы

Код на pascal abc net , накидайте рабочих вариантов

На плоскости задано множество попарно различных прямых ( коэффициентами своих уравнений ). Указать среди них прямую, которая имеет наибольшее число пересечений с остальными прямыми.

По дате
По рейтингу
Аватар пользователя
Искусственный Интеллект
1мес

Смотри сюда.
Не пересекаются параллельные прямые.
А параллельны те, у которых коэффициенты наклона одинаковые.
Значит, тебе надо составить словарик с коэффициентами наклона и их количеством.
А потом выбрать такой коэффициент, у которого наименьшее (!) количество. Линии с такими коэффициентами будут пересекать больше всего остальных линий.
Это простой алгоритм сложности O(n), выгодно отличающийся от ИИшного выше, который O(n²).
Как это записать на абц - извиняй, не в курсе. Могу налабать на C#. Но уж точно не стоит использовать ИИшные решения, они тупые до невозможности.

Аватар пользователя
Искусственный Интеллект
1мес
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
 // Вариант 1: Используя записи (records) 
uses System.Linq; // Для использования ToArray() и других LINQ методов, если потребуется 
 
type 
  // Запись для представления прямой Ax + By + C = 0 
  TLine = record 
    A, B, C: real; 
    Id: string; // Для идентификации прямой (например, "Прямая 1") 
    OriginalIndex: integer; // Для ссылки на исходный индекс, если нужно 
  end; 
 
// Функция для проверки пересечения двух прямых 
function DoIntersect(line1: TLine; line2: TLine): boolean; 
begin 
  // A1*B2 - A2*B1 
  Result := Abs(line1.A * line2.B - line2.A * line1.B) > 1e-9; // Используем малое число для сравнения с нулем (эпсилон) 
                                                             // для учета погрешностей вычислений с вещественными числами 
end; 
 
begin 
  // Пример набора прямых 
  // Можно организовать ввод с клавиатуры или из файла 
  var lines := new TLine[5]; 
  lines[0] := new TLine(1, -1, 0, 'Прямая 1 (y=x)', 0);         // y = x 
  lines[1] := new TLine(1, 1, -2, 'Прямая 2 (y=-x+2)', 1);     // y = -x + 2 
  lines[2] := new TLine(1, 0, -3, 'Прямая 3 (x=3)', 2);        // x = 3 
  lines[3] := new TLine(0, 1, -1, 'Прямая 4 (y=1)', 3);        // y = 1 
  lines[4] := new TLine(2, -2, 0, 'Прямая 5 (y=x, совпадает с 1 графически)', 4); // y = x (параллельна или совпадает с первой) 
 
  // Если прямые 0 и 4 считать различными по коэффициентам, но они параллельны/совпадают, 
  // то DoIntersect вернет false, так как A1*B2 - A2*B1 = 1*(-2) - 2*(-1) = -2 + 2 = 0. 
  // Это корректно, так как они не дадут уникальной точки пересечения, отличной от самих себя. 
  // "Попарно различных прямых" обычно означает геометрически различных. 
  // Если есть прямые типа x+y=0 и 2x+2y=0, они не считаются "различными" для задачи пересечений. 
  // Если они заданы как различные элементы массива, то проверка на параллельность их отсеет. 
 
  var n := lines.Length; 
 
  if n < 2 then 
  begin 
    Writeln('Недостаточно прямых для поиска пересечений.'); 
    exit; 
  end; 
 
  var intersectionCounts := new integer[n]; // Массив для хранения числа пересечений для каждой прямой 
 
  for var i := 0 to n - 1 do 
  begin 
    for var j := i + 1 to n - 1 do // Сравниваем каждую прямую с последующими 
    begin 
      if DoIntersect(lines[i], lines[j]) then 
      begin 
        intersectionCounts[i] += 1; 
        intersectionCounts[j] += 1; 
      end; 
    end; 
  end; 
 
  // Поиск прямой с максимальным числом пересечений 
  var maxIntersections := -1; 
  var lineWithMaxIntersections: TLine; 
  var found := false; 
 
  for var i := 0 to n - 1 do 
  begin 
    Writeln($'Прямая "{lines[i].Id}" (A={lines[i].A}, B={lines[i].B}, C={lines[i].C}) пересекается с {intersectionCounts[i]} другими прямыми.'); 
    if intersectionCounts[i] > maxIntersections then 
    begin 
      maxIntersections := intersectionCounts[i]; 
      lineWithMaxIntersections := lines[i]; 
      found := true; 
    end; 
  end; 
 
  if found then 
    Writeln(#13#10'Прямая с наибольшим числом пересечений ({maxIntersections} пересечений):'); 
    Writeln($'ID: {lineWithMaxIntersections.Id}, Уравнение: {lineWithMaxIntersections.A}x + {lineWithMaxIntersections.B}y + {lineWithMaxIntersections.C} = 0') 
  else 
    Writeln('Не найдено пересекающихся прямых (возможно, все параллельны или прямых < 2).'); 
 
end.