Нахождение минимальных пересечений
Вложений: 1
помогите решить задачу, есть две параллельные линии (параллельные или нет это не столь важно), на первой линии точки A B C D E F..., на второй линии точки 1 2 3 4 5 ... они соеденены прямыми, например А-1 А-3 С-2 С-1, надо написать программу, которая находит минимальное пересечение этих прямых. Решение этой задачи вроди как должно быть в интернете, но я не могу найти, помогите пожалуйста, очень надо.
|
Какой язык и сроки?
|
срок среда, язык всё равно какой, лучше Java, можно С.
|
Что понимается под минимальным пересечением? Вы пробовали решать самостоятельно?
|
когда проводишь прямые через все буквы и точки, они пересекаются, на рисунке прикреплённом это хорошо видно, так вот необходимо создать такую программу, чтобы при проведении этих прямых было минимальное пересечение. Преподователь обяснил так, хотя задание я тоже до конца не понимаю, думаю может есть какое-то классическое аналогичное задание, т.к. он сказал что такую программу можно в нете найти, но я ничего не могу найти
|
Преподователь сказал также что эту задачу можно решать через матрицу, но это сложнее
|
Я пока плохо себе представляю, что требуется. Уточните, какие данные на входе.
|
Вложений: 1
Суть задания заключается в том, что надо соединить прямыми линиями точки на одной прямой с точками на другой таким образом, чтобы пересечение между линиями было бы минимальным
|
Цитата:
1. "Пересечение между линиями" не может быть ни минимальным, ни максимальным - оно либо есть, либо нет. Возможно, речь идет о минимальном количестве точек пересечения отрезков? Тогда так и надо писать. 2. Если так, то по какому алгоритму происходит соединение точек? Поясню. Если Вы соедините попарно точки А - 1 B - 2 C - 3 и т.п., то никаких точек пересечения вообще не будет. Но, очевидно, так нельзя. А как можно? Со сколькими точками нижней горизонтальной прямой должна соединяться каждая точка верхней и наоборот? Чем это регламентируется? Каков алгоритм? Понимаете, пока Вы не проясните эти вопросы, толку всё равно не будет. |
Абсолютно правильно я имею ввиду минимальное количество точек пересечения, а насчёт алгоритма сама не поняла что предодователь имел ввиду, завтра постараюсь его найти и уточнить. Задание изначально не ясное было, просто я сделала предположение что есть классическая задача на это минимальное пересечение точек.
|
Часовой пояс GMT +4, время: 06:21. |
Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.