Нахождение минимальных пересечений
Вложений: 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 и т.п., то никаких точек пересечения вообще не будет. Но, очевидно, так нельзя. А как можно? Со сколькими точками нижней горизонтальной прямой должна соединяться каждая точка верхней и наоборот? Чем это регламентируется? Каков алгоритм? Понимаете, пока Вы не проясните эти вопросы, толку всё равно не будет. |
Абсолютно правильно я имею ввиду минимальное количество точек пересечения, а насчёт алгоритма сама не поняла что предодователь имел ввиду, завтра постараюсь его найти и уточнить. Задание изначально не ясное было, просто я сделала предположение что есть классическая задача на это минимальное пересечение точек.
|
Я так подозреваю, что на входе еще есть количество прямых, которые нужно провести. Так вот, если таких прямых больше чем точек...
Да, с точки зрения математики, фраза "минимальное пересечение точек" - бредятина. |
вот что преподователь написал: Take in Internet "minimal crossing number" Wikipedia and you will find a full explanation
|
это вообще кошмар какой-то... ничего не понятно...
|
Так я и думал - теория графов. Жаль, что у меня нет свободного времени, было бы интересно решить.
|
Long Cat
сложно решается? |
Сложно-понятие относительное. Если честно, мне как-то в лом в хорошую погоду тратить свое время за "спасибо".
|
Long Cat
давай договоримся не за спасибо. во сколько ты свою работу оцениваешь? |
Обращайтесь в ЛС или ICQ
|
Long Cat
объясни как в лс писать, не могу найти |
Если щелкнуть по моему профилю, выезжает меню, в меню есть пункт про ЛС. При этом ЛС должно быть включено в настройках приватности.
|
Long Cat
в ICQ написала |
Long Cat
ты мне напишешь в ICQ? |
может ты лучше mail дашь свой?
|
кто-нибудь может помоч с решением этой задачи?
|
Часовой пояс GMT +4, время: 02:57. |
Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.