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

Комбинаторика... Перестановки... - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Строки http://www.cyberforum.ru/cpp-beginners/thread31752.html
Ввести строчку длиной до 30 символов, заменить в ней двойные символы на одиночные, пробелы - на знак подчёркивания, сочетания ** на многоточие ...
C++ Последовательность Дана последовательность натуральных чисел. Найти наименьшее натуральное число которое отсутствует в последовательности и определить его делители http://www.cyberforum.ru/cpp-beginners/thread31751.html
C++ Работа с цифрами
Составить алгоритм определения количества 2N-значных чисел из которых сумма N первых цифр равна сумме N последних. N - произвольное натуральное число
Создать класс matrix C++
разработать класс Matrix – матрица, физически представляющая собой вектор, состоящий из заданного числа векторов. Реализовать метод сравнения двух матриц (==, !=). Помогите плизз З.Ы. Написать на...
C++ Как сохранить полученный результат в блокноте? http://www.cyberforum.ru/cpp-beginners/thread31732.html
как сохранить полученные результаты в блокноте на рабочий стол. данные прописаны к примеру в Label1->Caption (ФИО) и Label2->Caption (Зарплата) т.е. нужно чтобы ФИО и зарплата прописаны были в...
C++ Не работает ссылка на функцию. Пожалуйста,Помогите найти ошибку.Мне нужно сделать ссылку на функцию, которая является функцией класса interface. С этой ссылкой на функцию я должна работать в функциях класса newt.Проблемма в том,... подробнее

Показать сообщение отдельно
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254

Комбинаторика... Перестановки... - C++

27.04.2009, 18:55. Просмотров 7987. Ответов 0
Метки (Все метки)

Уважаемые эксперты помогите решить задачки по перестановкам...
№1
Степень перестановки
(Время: 1 сек. Память: 16 Мб)
Требуется вычислить степень заданной перестановки.
Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Количество различных перестановок порядка N равно PN = N!
Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говорит, что на i место нужно поставить ai элемент множества, где ai - i-тый элемент перестановки.
Обратной перестановкой к перестановке π называется такая перестановка π-1, что ππ-1 = π-1π = ε, где ε – тождественная перестановка.

Степенью перестановки называется минимальное натуральное число k такое, что πk = ε

Входные данные
В первой строке входного файла INPUT.TXT записано число 0 < N <= 100 - порядок перестановки. Во второй строке записана сама перестановка.

Выходные данные
В выходной файл OUTPUT.TXT выведите степень данной перестановки. Гарантируется, что ответ не превышает 10^9.

INPUT.TXT OUTPUT.TXT
3
2 3 1 3

№2
Восстановление перестановки
(Время: 1 сек. Память: 16 Мб)
Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N.
Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говорит, что на i место нужно поставить ai элемент множества, где ai - i-тый элемент перестановки.
Пусть дана перестановка π. Обозначим φ[i] - количество таких j, что π[j] > π[i], а j < i. φ называется таблицей инверсий перестановки π.
Требуется по данной таблице инверсий восстановить перестановку.

Входные данные
В первой строке входного файла INPUT.TXT записано число 0 < N <= 2000 - порядок перестановки. Во второй строке записана таблица инверсий.

Выходные данные
В выходной файл OUTPUT.TXT выведите искомую перестановку.
INPUT.TXT OUTPUT.TXT
1 3
0 0 2 2 3 1

№3
Перестановка по номеру
(Время: 1 сек. Память: 16 Мб)
Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Количество всех перестановок порядка N равно PN = N!
Требуется найти перестановку по ее номеру в лексикографическом порядке (по алфавиту). Например, для N=3 лексикографический порядок перестановок выглядит следующим образом:
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
Таким образом, перестановка (2,3,1) имеет номер 4 в этой последовательности.

Входные данные
В первой строке входного файла INPUT.TXT записано число N (1 <= N <= 12) - количество элементов в перестановке, во второй - число K (1 <= K <= N!) - номер перестановки.

Выходные данные
В выходной файл OUTPUT.TXT выведите через пробел N чисел - искомую перестановку.

Примеры
INPUT.TXT OUTPUT.TXT
1
1 1
INPUT.TXT OUTPUT.TXT
3
2 1 3 2



№4
Следующая перестановка ...
(Время: 1 сек. Память: 16 Мб)
Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N.
Найдите по заданной перестановке следующую в лексикографическом порядке (будем считать, что за перестановкой (N, N-1, ... , 3, 2, 1) следует тождественная перестановка, то есть (1, 2, 3, ... , N)).

Входные данные
В первой строке входного файла INPUT.TXT содержится число N (1 <= N <= 10^4). Во второй строке содержится перестановка (последовательность натуральных чисел от 1 до N, разделенных пробелами).

Выходные данные
Выходной файл OUTPUT.TXT должен содержать искомую перестановку.
Примеры
INPUT.TXT OUTPUT.TXT
1
1 1
INPUT.TXT OUTPUT.TXT
5
2 4 5 3 1 2 5 1 3 4

Добавлено через 32 минуты 37 секунд
Никто что ли комбинаторику не знает????

Добавлено через 32 секунды
Как и я....ыы
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru