Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Теория графов] Олимпиадная задача 
:(
    Опции темы
g1pn0z
Дата 29.4.2007, 16:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
Нашел интересную задачку, а решить не получается;( Стока над ней думал, выпил три чашки кофе
а потом уснул,...  smile  Пожалуйста помогите,  а то кофе меня скоро убьет...
Суть задачи
Цитата
На плане города, в котором Николай Николаевич работает таксистом, есть   площадей, пронумерованных от 1 до N(N принадлежит отрезку от 1 до 1000) . Некоторые площади соединены дорогами. Дороги эти настолько узкие, что на них введено одностороннее движение. По своему опыту Николай Николаевич знает, что, выехав с какой-нибудь площади и проехав несколько дорог, невозможно приехать опять на эту же площадь. Нет двух дорог, соединяющих одну и ту же пару площадей. Дороги пересекаются только на площадях.
Один раз на площади A Николай Николаевич подобрал пассажира, который попросил довезти его до площади B, причем по дороге остановиться на площадях C1, C2, …, Ck (на них пассажира будут ждать знакомые). Порядок посещения промежуточных площадей для пассажира не важен. «Сколько же денег взять с него?» – задумался Николай Николаевич. Он решил взять с пассажира столько рублей, сколько существует различных маршрутов от площади A до площади B, проходящих через C1, C2, …, Ck.
Требуется написать программу, которая определит, сколько существует маршрутов от площади A до площади B, проходящих через C1, C2, …, Ck.
Формат входных данных
Первая строка входного содержит числа  – количество площадей и  – количество дорог. В следующих   строках находятся описания дорог. Каждая из этих строк содержит по два числа – начальную и конечную площадь для дороги. Обратите внимание, что проехать по дороге в обратном направлении (от конечной площади к начальной) нельзя: движение одностороннее. В следующей строке числа A – начальная площадь, B – конечная площадь и K – количество промежуточных площадей. И, наконец, следующие K строк содержат числа C1, C2, …, Ck по одному в строке. Среди чисел A, B, C1, C2, …, Ck нет одинаковых.

P.S. Сильно не бейте, заранее спасибо!
P.S2. Кому действительно понравилась задача пишите в асю(9631828)


Это сообщение отредактировал(а) g1pn0z - 1.5.2007, 21:39
PM MAIL ICQ   Вверх
g1pn0z
Дата 1.5.2007, 10:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
Нашел направление в котором надо двигаться, задача решается через графы, но эту тему я пока не изучал.... 

Это сообщение отредактировал(а) g1pn0z - 1.5.2007, 21:40
PM MAIL ICQ   Вверх
g1pn0z
Дата 1.5.2007, 21:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
Ну подскажите хотя бы где можно про графы почитать, а то толкового ничего совсем ни нашел, кроме как алгоритмов вот здесь http://progs-maker.narod.ru/algor.html ...
PM MAIL ICQ   Вверх
sergejzr
Дата 1.5.2007, 21:42 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 11
Всего: 360
И задирать темы нельзя! smile 


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
sergejzr
Дата 1.5.2007, 21:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 11
Всего: 360
Для домашних заданий, курсовых, существует "Центр Помощи"

Тема перенесена! 


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
Shadowlord
Дата 1.5.2007, 21:52 (ссылка) | (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 275
Регистрация: 28.11.2006

Репутация: 2
Всего: 5
Google тебе в помощьsmile
PM MAIL   Вверх
XupyprMV
Дата 1.5.2007, 22:07 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 50
Регистрация: 16.10.2006
Где: Сыктывкар, Россия

Репутация: нет
Всего: нет
Почитай книжки по графам... 

Например Ф. Харари, О. Оре, Уилсон Р., Татт У....

А если прямо в точку зрить, то задача вроде как построение покрытия в ориентированном графе без циклов... (исправил, было неверно: в транзитивно-замкнутом)

Поскольку N не так велико можно решить задачу полным перебором... Ищи: алгоритм поиска в глубину...

Это сообщение отредактировал(а) XupyprMV - 1.5.2007, 22:12
PM MAIL WWW ICQ   Вверх
esperant0
Дата 1.5.2007, 22:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 1
Всего: 14
топологическая сортировка + динамическое программирование


--------------------
 
 Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer 

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором  а затем стерто и которое он - пользователь не мог видеть. 
PM MAIL   Вверх
g1pn0z
Дата 2.5.2007, 09:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
да, за гугль особое спасибо)))
PM MAIL ICQ   Вверх
Promitheus
Дата 3.5.2007, 13:57 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 73
Регистрация: 28.3.2007

Репутация: нет
Всего: 1
Я бы не сказал, что задача новая, это из разряда 8 ферзей, кенигсбергских мостах и тэдэ. Обычная задача теории графов/дискретной математики.  

Новиков "Дискретная Математика для программистов", там есть примеры на псевдокоде почти ко всей теории. ИМХО: Но сама книга тэк себе.

Вообще я думаю вам троим надо объединиться 

http://forum.vingrad.ru/forum/topic-148014.html
http://forum.vingrad.ru/forum/topic-149273...компоненты.html
http://forum.vingrad.ru/forum/topic-148770...рта-города.html (текущая тема)


Это сообщение отредактировал(а) Promitheus - 3.5.2007, 14:05
PM MAIL ICQ   Вверх
esperant0
Дата 3.5.2007, 14:03 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 1
Всего: 14
Цитата(Promitheus @ 3.5.2007,  13:57)
Я бы не сказал, что задача новая, это из разряда 8 ферзей, кенигсбергских мостах и тэдэ. Обычная задача теории графов/дискретной математики. 

 

А я повторю, вами сказанное не имеет прямого отношения к задаче.


Задача решается топологической сортировкой+динамическим программированием. 



ПРичем тут ферзи и мосты не ясно. 



--------------------
 
 Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer 

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором  а затем стерто и которое он - пользователь не мог видеть. 
PM MAIL   Вверх
Promitheus
Дата 3.5.2007, 14:19 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 73
Регистрация: 28.3.2007

Репутация: нет
Всего: 1
esperant0: Вы слышали о подобных задачах или нет ? А о задаче комивояжера ?

Хотелось бы конкретной пример вашей топологической сортировки и динамического программирования + ликбез что вы вкладываете в эти понятия.
PM MAIL ICQ   Вверх
esperant0
Дата 3.5.2007, 14:34 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 1
Всего: 14
Цитата(Promitheus @ 3.5.2007,  14:19)
esperant0: Вы слышали о подобных задачах или нет ? А о задаче комивояжера ?

Хотелось бы конкретной пример вашей топологической сортировки и динамического программирования + ликбез что вы вкладываете в эти понятия.

Я слышал.


Прочти те внимательно условие задачи, из него следует,что задан ациклический направленный граф.


Для таких графов можно применить алгоритм топологической сортировки, и получить порядок на вершинах при котором все стрелки идут слева на право.

Дальше автор просит определить количество дорог обладающих определенным свойством.

Это делается с помощью применения правила суммы + динамическое программирование.

Правило суммы вы найдете в учебнике по комбинаторике.

А с динамическим программированием можете ознакомиться например в книге Вентцель Елены или по статьям Бельмана.


А вот задача комивояжера тут, ну ни причем.

с уважением, 

пс: мы такие задачи дает студентам после изучения темы топол.сортировак





--------------------
 
 Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer 

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором  а затем стерто и которое он - пользователь не мог видеть. 
PM MAIL   Вверх
g1pn0z
Дата 5.5.2007, 10:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 29
Регистрация: 29.4.2007

Репутация: нет
Всего: нет
Цитата
esperant0:
Для таких графов можно применить алгоритм топологической сортировки, и получить порядок на вершинах при котором все стрелки идут слева на право.

можешь показать как это будет на паскале, или  где есть примеры...
PM MAIL ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0778 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.