Gennadiusisus Опубликовано 22 сентября, 2013 Жалоба Поделиться Опубликовано 22 сентября, 2013 Помогите алгоритмизировать задачу! Нужно написать программу способную определить, можно ли в заданной системе односторонних дорог проехать из города А в город В таким образом, чтобы посетить город С и не проезжать никакой дороги более одного раза.Заранее спасибо =) Ссылка на комментарий
martinges Опубликовано 23 сентября, 2013 Жалоба Поделиться Опубликовано 23 сентября, 2013 Дано матрица смежности(только модернизировать надо так как движение одностороннее)Динамическая структура или массив хранящий путь и промежуточный граф откуда постепенно будем удалять пройденные дорогиМаркер прохода через вершину С(булева)_________________________________Фиксируем вершину АПеребираем все вершины куда сможем приехать из А, допустим это будет X(первая попавшаяся ) удаляем из массива или дин структуры дорогу(ребро графа), добавляем путь в массив, хранящий путьПовторяем алгоритм для вершины X, если X это С, поднимаем маркер. Если X это B и маркер true то выводим на экран насколько мы крутые))P.S. Не оптимально наверное, но результат даст P.P.S При поиске можно создать рекурсивную процедурку или функцию, которой ты скармливаешь граф и внутри этой функции/процедуры ты будешь скармливать уже "похудевший" на одну дорогу граф Вот только при больших массивах данных тормозит зараза) Ссылка на комментарий
Innk Опубликовано 23 сентября, 2013 Жалоба Поделиться Опубликовано 23 сентября, 2013 http://e-maxx.ru/algo/вот если понимаешь найдёшь алгоритм, поменяешь маленько )1)Сначала же нам нужно дойти до С, вопрос - можно ли идя до С пройти через В, и потом по другим дорогам вернутся в В ?Или дошли до С, потом через А дошли до ВЕсли нет, то это вроде простой поиск в глубину(в ширину), до В, с хранением дополнительной метки, заходили ли мы в С - полный перебор )2)какие ограничения на задачу - количество рёбер, вершин ?3)И конечно в мире существует только один язык программирования ))Где такие задачи задают ? И много ли ? Ссылка на комментарий
martinges Опубликовано 23 сентября, 2013 Жалоба Поделиться Опубликовано 23 сентября, 2013 1)Предполагаю что в одну вершину могут вести как входящие в город так и выходящие из него) так что в каком то случае возможен вариант возвращения в города по нескольку раз 2) представляю облом если будет миллион вершин и изолированный город B, а бедная программулька все будет искать и искать))3)assembler ггХорошие задачки)) мозги так и радуются)) Ссылка на комментарий
Gennadiusisus Опубликовано 23 сентября, 2013 Автор Жалоба Поделиться Опубликовано 23 сентября, 2013 http://e-maxx.ru/algo/вот если понимаешь найдёшь алгоритм, поменяешь маленько )1)Сначала же нам нужно дойти до С, вопрос - можно ли идя до С пройти через В, и потом по другим дорогам вернутся в В ?Или дошли до С, потом через А дошли до ВЕсли нет, то это вроде простой поиск в глубину(в ширину), до В, с хранением дополнительной метки, заходили ли мы в С - полный перебор )2)какие ограничения на задачу - количество рёбер, вершин ?3)И конечно в мире существует только один язык программирования ))Где такие задачи задают ? И много ли ?Каждую дорогу можно проехать один раз, то есть, если есть несколько путей из "А" в "С", то нужно выбрать тот, который не препятствовал бы дальнейшему переходу в "В"Ограничений больше нету...вроде...=)Пишу на С++У первочей в техноложке курсачи такие...не удержался что бы не попробовать запрогать =)Добавлено спустя 24 минуты 21 секунду:1)Предполагаю что в одну вершину могут вести как входящие в город так и выходящие из него) так что в каком то случае возможен вариант возвращения в города по нескольку раз 2) представляю облом если будет миллион вершин и изолированный город B, а бедная программулька все будет искать и искать))3)assembler ггХорошие задачки)) мозги так и радуются))ассемблер зло, фу фу фу...=]а задачка и правда интересная =) и готовых алгоритмов под нее нету (не нашел по крайней мере) Ссылка на комментарий
Innk Опубликовано 23 сентября, 2013 Жалоба Поделиться Опубликовано 23 сентября, 2013 Пруд пруди таких задачек )Вот здесь если решил, то точно узнаешь правильно или нетhttp://acm.timus.ru/problemset.aspxhttp://codeforces.ru/contestshttp://acm.mipt.ru/и куча другихВот я нарешал ))http://acm.timus.ru/author.aspx?id=105123 - это к олимпиадам готовлюсь.от вуза по 3 человека в команде ездим на четверть/полу финал ACM ICPCЕсли просто интересно то вот почитать можноКормен, Лейзерсон, Ривест, Штайн. Алгоритмы. Построение и анализhttp://e-maxx.ru/bookz/ Ссылка на комментарий
Рекомендуемые сообщения
Пожалуйста, войдите, чтобы комментировать
Вы сможете оставить комментарий после входа в
Войти