Помогите решить задание:
есть две линии, на первой линии точки A B C D E F..., на второй линии точки 1 2 3 4 5 ... они соеденены прямыми, например А-1 А-3 С-2 С-1, надо написать программу, которая находит минимальное количество точек пересечения этих прямых. Это по теории графов.
Язык не важен, лучше JAVA.
Решение этой задачи вроди как должно быть в интернете, но я не могу найти, помогите пожалуйста, очень надо.
10 ответов в этой теме
#2
shb
-
- Постоялец
-
- 5 253 сообщений
New life, much more options
- Откуда:Таллинн
Отправлено 06 июня 2011 - 21:25
Вроде интересно, но сформулируй нормально. Лучше дай прямо как в задании звучит.
Мыслящий человек просто обязан время от времени поднимать себя за волосы © Тот самый Мюнгхаузен
Joga Bonito!
Joga Bonito!
#3
aleks2011
-
- Пользователь
-
- 21 сообщений
Отправлено 06 июня 2011 - 21:36
у меня самого задания нет, преподователь так объяснил
две линии с точками, эти точки с первой линии соединяются прямыми с точками со второй линии, естественно они пересекаются между собой, а дальше: Take in Internet "minimal crossing number" Wikipedia and you will find a full explanation. Сказал что в нете есть решение, можно готовое взять, но я не могу найти нигде
две линии с точками, эти точки с первой линии соединяются прямыми с точками со второй линии, естественно они пересекаются между собой, а дальше: Take in Internet "minimal crossing number" Wikipedia and you will find a full explanation. Сказал что в нете есть решение, можно готовое взять, но я не могу найти нигде
#4
shb
-
- Постоялец
-
- 5 253 сообщений
New life, much more options
- Откуда:Таллинн
Отправлено 06 июня 2011 - 21:41
спасибо =) задание понятно, порисую чуток )
Мыслящий человек просто обязан время от времени поднимать себя за волосы © Тот самый Мюнгхаузен
Joga Bonito!
Joga Bonito!
#5
aleks2011
-
- Пользователь
-
- 21 сообщений
Отправлено 06 июня 2011 - 22:18
shb, у меня есть надежда какая-нибудь?
Сообщение изменено: aleks2011 (06 июня 2011 - 22:19 )
#6
shb
-
- Постоялец
-
- 5 253 сообщений
New life, much more options
- Откуда:Таллинн
Отправлено 06 июня 2011 - 22:22
aleks2011, надежды мало. Интернеты пишут что нахождение минимального числа пересечений на графе это NP проблема. А вот насчет нахождения минимального пересечения на двудольном графе пока не знаю 
Мыслящий человек просто обязан время от времени поднимать себя за волосы © Тот самый Мюнгхаузен
Joga Bonito!
Joga Bonito!
#8
shb
-
- Постоялец
-
- 5 253 сообщений
New life, much more options
- Откуда:Таллинн
Отправлено 06 июня 2011 - 22:29
пм на форуме подойдет
Мыслящий человек просто обязан время от времени поднимать себя за волосы © Тот самый Мюнгхаузен
Joga Bonito!
Joga Bonito!
#10
m1ha
-
- Постоялец
-
- 752 сообщений
Отправлено 06 июня 2011 - 22:36
пм = private message, то есть через систему сообщений на форуме.
Автор тебе до какого числа это надо ?
Автор тебе до какого числа это надо ?
#11
aleks2011
-
- Пользователь
-
- 21 сообщений
Отправлено 06 июня 2011 - 22:45
в среду надо сдать
предмет не по программированию, даже плагиат можно, но где найти или как сделать...
shb,
я сейчас про нахождения минимального пересечения на двудольном графе посмотрела, это оно самое и есть. Как раз это преподователь и просит сделать
предмет не по программированию, даже плагиат можно, но где найти или как сделать...
shb,
я сейчас про нахождения минимального пересечения на двудольном графе посмотрела, это оно самое и есть. Как раз это преподователь и просит сделать
