Форум программистов, компьютерный форум CyberForum.ru

динамическое программирование (Ship routes) - C++

Восстановить пароль Регистрация
 
asidorchenko
379 / 205 / 25
Регистрация: 09.04.2012
Сообщений: 635
27.12.2012, 01:57     динамическое программирование (Ship routes) #1
Задача на динамическое программирование:
Римский турист отправился в плавание по Средиземному морю. Он прибыл в один из городов 3 островов, которые он собирается посетить. Каждый остров имеет в точности N городов и все они являются портами. турист планирует начать путешествие с того города,в котором он находится и посетить другие 3*N - 1 городов в точности один раз и затем вернуться в начальный город, чтобы вернуться обратно домой после этого.

К сожалению на дорогах трех островов есть каннибалы. Поэтому путешествие между 2 городами одного и того же острова очень опасно и запрещено. К счастью, есть морские пути. Каждая пара городов, находящихся не на одном острове связаны таким морским путем. Морских путей между гордами,к оторые на одном острове нет.

Турист хочет знать, сколькими способами он может спланировать свое путешествие по 3 островам

Ввод

Содержит одно число N (1<=N<=30), то есть количество городов на каждом из трех островов

Вывод

Вывести одно число: количество способов, которыми турист может спланировать свое путешествие. Заметьте, что два путешествия являются идентичными если последовательности из 3*N городов идентичны ИЛИ если последовательность из 3*N городов первого путешествия идентична последовательности из 3*N городов двторого путешествия, считанной наоборот ( например, если каждый остров имеет один город, пронумерованный в соответствии с номером острова, путешествия 1-2-3-1 и 1-3-2-1 будут идентичными

Пример ввода
2
Пример вывода
16

Лимит времени
1 секунда

Лимит памяти
16 МБ

Оригинал:
Кликните здесь для просмотра всего текста
Ship Routes
A Romanian tourist went on a trip to the Mediterranean Sea. He arrived to one of the cities of the 3 islands he is going to visit. Every island has exactly N cities and they are all ports. The tourist plans to begin his journey from the city he is in, visit all the other 3*N-1cities exactly once and then return to the starting city so he may go back home after that.

Unfortunately, there are cannibals along the roads on all the 3 islands. That's why travelling on the road between 2cities on the same island is very dangerous and, consequently, prohibited. Hopefully, there are always ship routes. Every pair of cities which are not on the same island is connected by such a ship route. There are no routes between cities which are on the same island.

The tourist wants to know in how many ways he can plan his journey through the 3 islands.

Input

The input contains a single number: N (1 ≤ N ≤ 30), the number of cities on each of the 3 islands.

Output

You should output a single number: the number of ways the tourist can plan his trip. Note that 2 trips are identical if the successions of the 3*N cities are identical or if the succession of the 3*N cities of the first trip is the same as the succession of the 3*N cities of the 2nd trip, read backwards (for instance, if every island had 1 city, numbered according to the island's number, the trips 1-2-3-1 and 1-3-2-1 would be identical).

Example input
2
Example output
16

/* А это те 16 разных маршрутов:
1 3 5 2 4 6
1 3 5 2 6 4
1 3 6 2 4 5
1 3 6 2 5 4
1 4 5 2 3 6
1 4 5 3 2 6
1 4 6 2 3 5
1 4 6 3 2 5
1 5 2 4 6 3
1 5 3 2 4 6
1 5 3 6 2 4
1 5 4 6 2 3
1 6 2 4 5 3
1 6 3 2 4 5
1 6 3 5 2 4
1 6 4 5 2 3
*/


Problem information
Time Limit: 1 seconds
Memory Limit: 16 MB
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.12.2012, 01:57     динамическое программирование (Ship routes)
Посмотрите здесь:

Динамическое программирование. C++
Динамическое программирование C++
C++ ДП Динамическое программирование
C++ Динамическое программирование
C++ Динамическое программирование!
Динамическое программирование C++
C++ Динамическое программирование

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gdrt
3 / 3 / 0
Регистрация: 29.10.2011
Сообщений: 12
27.12.2012, 13:02     динамическое программирование (Ship routes) #2
Цитата Сообщение от asidorchenko Посмотреть сообщение
Перевод
спасибо, а перевод откуда и если знаете решение поделитесь пожалуйста с нами
asidorchenko
379 / 205 / 25
Регистрация: 09.04.2012
Сообщений: 635
27.12.2012, 13:50  [ТС]     динамическое программирование (Ship routes) #3
Цитата Сообщение от gdrt Посмотреть сообщение
спасибо, а перевод откуда и если знаете решение поделитесь пожалуйста с нами
Я сам перевел. Это алгоритмы на графах. Каждый порт - вершина графа. Задача заключается в поиске маршрута в графе - данная задача исследовалась Гамильтоном в XIX веке, поэтому подобные пути, которые нужно найти, названы гамильтоновыми. Нужно построить гамильтонов граф.
Есть описание в Википедии: ru.wikipedia.org/wiki/Гамильтонов_граф
Алгоритмы на графах описываются в книге "Дискретная математика для программистов" (Новиков). Смотрите учебники по дискретной математики или книги, где рассматриваются графы.
Yandex
Объявления
27.12.2012, 13:50     динамическое программирование (Ship routes)
Ответ Создать тему
Опции темы

Текущее время: 06:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru