leopatra

помогите решить задачу, есть две параллельные линии (параллельные или нет это не столь важно), на первой линии точки A B C D E F..., на второй линии точки 1 2 3 4 5 ... они соеденены прямыми, например А-1 А-3 С-2 С-1, надо написать программу, которая находит минимальное пересечение этих прямых. Решение этой задачи вроди как должно быть в интернете, но я не могу найти, помогите пожалуйста, очень надо.

Миниатюры

 

Long Cat

Какой язык и сроки?

leopatra

срок среда, язык всё равно какой, лучше Java, можно С.

Long Cat

Что понимается под минимальным пересечением? Вы пробовали решать самостоятельно?

leopatra

когда проводишь прямые через все буквы и точки, они пересекаются, на рисунке прикреплённом это хорошо видно, так вот необходимо создать такую программу, чтобы при проведении этих прямых было минимальное пересечение. Преподователь обяснил так, хотя задание я тоже до конца не понимаю, думаю может есть какое-то классическое аналогичное задание, т.к. он сказал что такую программу можно в нете найти, но я ничего не могу найти

leopatra

Преподователь сказал также что эту задачу можно решать через матрицу, но это сложнее

Long Cat

Я пока плохо себе представляю, что требуется. Уточните, какие данные на входе.

leopatra

Суть задания заключается в том, что надо соединить прямыми линиями точки на одной прямой с точками на другой таким образом, чтобы пересечение между линиями было бы минимальным

Миниатюры

 

Vladimir_S

Уважаемый(-ая) Leopatra, ни в коей мере не намереваясь встревать в Ваш с LongCat диалог, я всё-таки позволю себе некоторые разъяснения того, чего, на мой взгляд, от Вас добиваются.
1. "Пересечение между линиями" не может быть ни минимальным, ни максимальным - оно либо есть, либо нет. Возможно, речь идет о минимальном количестве точек пересечения отрезков? Тогда так и надо писать.
2. Если так, то по какому алгоритму происходит соединение точек? Поясню. Если Вы соедините попарно точки
А - 1
B - 2
C - 3
и т.п., то никаких точек пересечения вообще не будет. Но, очевидно, так нельзя. А как можно? Со сколькими точками нижней горизонтальной прямой должна соединяться каждая точка верхней и наоборот? Чем это регламентируется? Каков алгоритм? Понимаете, пока Вы не проясните эти вопросы, толку всё равно не будет.

leopatra

Абсолютно правильно я имею ввиду минимальное количество точек пересечения, а насчёт алгоритма сама не поняла что предодователь имел ввиду, завтра постараюсь его найти и уточнить. Задание изначально не ясное было, просто я сделала предположение что есть классическая задача на это минимальное пересечение точек.