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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Нарисовать эллипс http://www.cyberforum.ru/cpp-beginners/thread747522.html
Нарисуйте, пожалуйста, эллипс.Срочно нужно!!!
C++ Цикл бесконечно повторяется попытался решить вот эту задачку http://acm.timus.ru/problem.aspx?space=1&num=1404 но, почему-то, второй цикл бесконечно повторяется... помогите плиз) #include <iostream> using namespace std; int main() { int a, i, i1; char code; http://www.cyberforum.ru/cpp-beginners/thread747521.html
Cгенерировать одномерный массив из 10 чисел,отсортировать его по возрастанию или убыванию C++
Суть собственно в чем, я полный чайник и задача мне нужна написанная самым простым языком, помогите кто-нибудь если сможете, а то я совсем блондинка) 1.сгенерировать одномерный массив из 10 чисел,отсортировать его по возрастанию или убыванию 2.найти наименьшеее и наибольшее и вывести на экран ну и тоже самое только в двумерном массиве
Заменить в каждом массиве максимальный элемент средним арифметическим положительных элементов (если оно существует) соответствующего массива C++
Здравствуйте, помогите пожалуйста: Ввести одномерные массивы X1(N1) , X2(N2) и X3(N3) . Заменить в каждом из них максимальный элемент средним арифметическим положительных элементов (если оно существует) соответствующего массива. Вывести массивы до преобразования и после. (При решении реализовать процедуры ввода и вывода массивов Vvod1m и Vivod1m, а также функции IndMax – поиск индекса...
C++ характеристика и операции обработки файлов с позиции ОС http://www.cyberforum.ru/cpp-beginners/thread747488.html
Кто знает, распишите пожалуйста по пунктам или кинье ссылку где это написано(гуглил - ничего толкового). Добавлено через 1 минуту Во-первых, нужно найти данные файла и его атрибуты по его символьному имени, во-вторых, считать необходимые атрибуты файла в отведенную область оперативной памяти и проанализировать права пользователя на выполнение требуемой операции. Затем выполнить операцию,...
C++ В тексте слова разделены запятыми,напечатать все слова в алфавитном порядке. Написал программу, она не запускаеться, я понимаю что чтото не так, но что незнаю. В чём я ошибся? Вот само задание: Дана строка s, содержащая от 1 до 30 слов, в каждом из которых от 1 до 5 строчных латинских букв. Между соседними словами стоит запятая, за последним словом - точка. Напечатать все слова в алфавитном порядке. Текст программы: #include<stdio.h> подробнее

Показать сообщение отдельно
asidorchenko
379 / 205 / 25
Регистрация: 09.04.2012
Сообщений: 635
27.12.2012, 01:57     динамическое программирование (Ship routes)
Задача на динамическое программирование:
Римский турист отправился в плавание по Средиземному морю. Он прибыл в один из городов 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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 21:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru