PDA

Просмотр полной версии : Снова ссесия...ХЕЛП!!!(для знающих с++)


Ex-ElvenRaider
15.05.2005, 12:50
Хелп!!! Срочно нужна программа на си++.Суть следующая:

Улицы в городе,построенном в средние века оказались слишком узкими для двустороннего движения.Необходимо спланировать движение так,чтобы с любой площади можно было бы проехать до любой другой.Площадей 15,всюду движение двустороннее(в смысле на площадях).Найти все все дороги между 3-мя несмежными площадями и определить кратчайший путь межде ними.

Вроде бы она должна решаться с помощью теории граф....сам я ни в графах ни в си...
Помогите пожалуйста!!!!!!!!!!Программа нужна срочно
Sir Zak
15.05.2005, 13:58
В графах не шарю. В с++ шарю. Дай алгоритм, можно будет что нить придумать.
Ex-ElvenRaider
15.05.2005, 14:22
Да вот сам хз....млин мож кто знает пусть пишет сюда все свои сообрадения...
Eidolon
15.05.2005, 14:27
А площади соединены-то как?
MoR
15.05.2005, 15:07
...
Так это... Кнута в руки и вперед %)
Хотя конечно годится любая книга по дискре и конкретно теории графов ))))
Passimense
15.05.2005, 15:45
А к чему вот это?
Улицы в городе,построенном в средние века оказались слишком узкими для двустороннего движения.К тому, что моделью будет ориентированный граф?

Аа. Или так? Имеется неориентированный граф, нужно из него сделать ориентированный (то есть задать, по каким дорогам в какую сторону можно перемещаться) так, чтобы для каждой упорядоченной пары вершин существовала цепочка дуг, составляющих путь от первой ко второй.

Самая первая проверка, очевидно, на связность графа. Если он несвязный, задача решения не имеет :D

Вторая проверка, очевидно, на висячие вершины. Если они есть, опять решения не имеется.

Ну и в итоге, когда неразрешимые случаи отброшены, разбиваем граф на циклы. Вначале обрабатываем те циклы, которые имеют максимальное число общих ребер с другими циклами. Задаем произвольное направление. Потом исходя из направлений дуг полученного ориентированного цикла, получаем направления всех остальных циклов.
Ex-ElvenRaider
15.05.2005, 19:19
Ну всё верно токо как это выглядит в си....я в с++ дуб..прога нужна срочно!!!Иначе буду топтать в кирзовых сапогах какой-нить забытый цивилизацией остров ((((
Red Blue
15.05.2005, 19:29
А может оно и к лучшему ??? Иди в армию там тебя научат Родину любить :lol: :lol: :lol:
Ex-ElvenRaider
17.05.2005, 00:14
Нет.Это не вариант )
Ex-ElvenRaider
17.05.2005, 13:33
Неужели нет на форуме человека способного решить это дрянь???!!! Я НЕ ХОЧУ В ЭТО ВЕРИТЬ!!!!
Anonymous
17.05.2005, 14:45
Люди есть, но сидеть решать задачу, а потом ее еще и кодить никто не будет.

Сам бы уже сел и разобрался, если не хочешь идти служить.
:D :D :D
Dalamar Dword 6567614D
17.05.2005, 15:04
Яндекс рулит! :)
http://www.yandex.ru/yandsearch?text=%E3%F0%E0%F4+%EA%F0%EE%F2%F7%E0%E9 %F8%E8%E9+%EF%F3%F2%FC&stype=www

Вот первая попавшаяся прога, но, правда, на паскале:
http://recursio.narod.ru/towns.htm
Ex-ElvenRaider
20.05.2005, 19:58
Это не совсем то.....
incognito
20.05.2005, 20:06
Яндекс рулит! :)
http://www.yandex.ru/yandsearch?text=%E3%F0%E0%F4+%EA%F0%EE%F2%F7%E0%E9 %F8%E8%E9+%EF%F3%F2%
может имелось ввиду крАтчайший путь? :)
Dalamar Dword 6567614D
21.05.2005, 00:34
Поскольку, кроме меня, еще есть неграммотные люди, то стоит искать так: :)
http://www.yandex.ru/yandsearch?text=%E3%F0%E0%F4+%28%EA%F0%E0%F2%F7%E0 %E9%F8%E8%E9+%7C+%EA%F0%EE%F2%F7%E0%E9%F8%E8%E9%29 +%EF%F3%F2%FC&stype=www