Перейти к содержимому

Фото
- - - - -

помогите решить задание


  • Вы не можете создать новую тему
  • Please log in to reply
10 ответов в этой теме

#1 aleks2011

aleks2011
  • Пользователь
  • 21 сообщений

Отправлено 06 Июнь 2011 - 21:10

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

#2 shb

shb

    New life, much more options

  • Постоялец
  • 5 253 сообщений
  • Откуда:Таллинн

Отправлено 06 Июнь 2011 - 21:25

Вроде интересно, но сформулируй нормально. Лучше дай прямо как в задании звучит.
  • 0
Мыслящий человек просто обязан время от времени поднимать себя за волосы © Тот самый Мюнгхаузен

Joga Bonito!

#3 aleks2011

aleks2011
  • Пользователь
  • 21 сообщений

Отправлено 06 Июнь 2011 - 21:36

у меня самого задания нет, преподователь так объяснил

две линии с точками, эти точки с первой линии соединяются прямыми с точками со второй линии, естественно они пересекаются между собой, а дальше: Take in Internet "minimal crossing number" Wikipedia and you will find a full explanation. Сказал что в нете есть решение, можно готовое взять, но я не могу найти нигде
  • 0

#4 shb

shb

    New life, much more options

  • Постоялец
  • 5 253 сообщений
  • Откуда:Таллинн

Отправлено 06 Июнь 2011 - 21:41

спасибо =) задание понятно, порисую чуток )
  • 0
Мыслящий человек просто обязан время от времени поднимать себя за волосы © Тот самый Мюнгхаузен

Joga Bonito!

#5 aleks2011

aleks2011
  • Пользователь
  • 21 сообщений

Отправлено 06 Июнь 2011 - 22:18

shb, у меня есть надежда какая-нибудь?

Сообщение изменено: aleks2011 (06 Июнь 2011 - 22:19 )

  • 0

#6 shb

shb

    New life, much more options

  • Постоялец
  • 5 253 сообщений
  • Откуда:Таллинн

Отправлено 06 Июнь 2011 - 22:22

aleks2011, надежды мало. Интернеты пишут что нахождение минимального числа пересечений на графе это NP проблема. А вот насчет нахождения минимального пересечения на двудольном графе пока не знаю :lol:
  • 0
Мыслящий человек просто обязан время от времени поднимать себя за волосы © Тот самый Мюнгхаузен

Joga Bonito!

#7 aleks2011

aleks2011
  • Пользователь
  • 21 сообщений

Отправлено 06 Июнь 2011 - 22:27

дай пожалуйста свой майл.
  • 0

#8 shb

shb

    New life, much more options

  • Постоялец
  • 5 253 сообщений
  • Откуда:Таллинн

Отправлено 06 Июнь 2011 - 22:29

пм на форуме подойдет
  • 0
Мыслящий человек просто обязан время от времени поднимать себя за волосы © Тот самый Мюнгхаузен

Joga Bonito!

#9 aleks2011

aleks2011
  • Пользователь
  • 21 сообщений

Отправлено 06 Июнь 2011 - 22:30

что такое пм?
  • 0

#10 mi1ha

mi1ha
  • Пользователь
  • 500 сообщений

Отправлено 06 Июнь 2011 - 22:36

пм = private message, то есть через систему сообщений на форуме.

Автор тебе до какого числа это надо ?
  • 0

#11 aleks2011

aleks2011
  • Пользователь
  • 21 сообщений

Отправлено 06 Июнь 2011 - 22:45

в среду надо сдать

предмет не по программированию, даже плагиат можно, но где найти или как сделать...

shb,
я сейчас про нахождения минимального пересечения на двудольном графе посмотрела, это оно самое и есть. Как раз это преподователь и просит сделать
  • 0