Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
asidorchenko
379 / 205 / 25
Регистрация: 09.04.2012
Сообщений: 635
#1

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

27.12.2012, 01:57. Просмотров 367. Ответов 2
Метки нет (Все метки)

Задача на динамическое программирование:
Римский турист отправился в плавание по Средиземному морю. Он прибыл в один из городов 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.12.2012, 01:57
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Динамическое программирование (Ship routes) (C++):

Динамическое программирование. - C++
Помогите, пожалуйста, составить алгоритм по одному из ниже представленных заданий, используя методы динамического программирования и жадных...

Динамическое программирование - C++
Не понимаю динамических структур, списков, работы с ними. Посоветуйте источник изучения. Что-то вроде того что написано здесь...

Динамическое программирование - C++
Помогите пожалуйста,кто может, со следующими задачами, так как в С++ слабо разбираюсь, а к понедельнику надо сдать... 1. Определить...

Динамическое программирование - C++
Подскажите что не так в решении. #include &lt;iostream&gt; #include &lt;stdio.h&gt; using namespace std; const int N = 5001; int...

динамическое программирование - C++
Народ помогите плиз найти алгоритм решения следующей задачи. На посвящение в студенты собрались все первокурсники. Некоторые из них знают...

ДП Динамическое программирование - C++
ограничение времени на тест: 0.5 сек. ограничение памяти на тест: 65536 KB. Рассмотрим все строки длины N, состоящие только из букв...

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

Динамическое программирование - C++
Задача: Есть n работников и n работ. Необходимо найти максимальную суммарную производительность. Каждый работник может выполнять только...

Динамическое программирование - C++
Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт У Пети есть полоска бумаги, разделенная на N клеток. Он хочет...

Динамическое программирование - C++
Есть такая задача: Дана схема стены, необходимо проверить можно ли построить данную стену заданным набором кирпичей. Кирпич высот 1, а...

Динамическое программирование - C++
Мячик прыгает по лестнице, состоящей из N ступенек, строго сверху вниз. За один прыжок он может отпрыгнуть на не более M ступенек....


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.