Форум программистов, компьютерный форум 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 - произвольное натуральное число
C++ Создать абстрактный тип данных - класс вектор
Доброго времени суток! Тут задачку такую не хилую подогнали. Нужна помощь опытных программистов. Создать абстрактный тип данных - класс вектор, который имеет указатель на float, число элементов и переменную состояния. Определить конструктор без параметров, конструктор с двумя параметрами. Конструктор без параметров выделяет место для одного элемента и инициализирует его в ноль, конструктор с...
C++ Работа с массивом строк http://www.cyberforum.ru/cpp-beginners/thread31682.html
Ввести массив строк символов (текст). В каждой строке найти длину самого ко-роткого слова. Словами считать группы символов, разделённые одним или несколь-кими пробелами.
C++ Факториал Даны натуральные числа N и M. Вычислить (M!+N!)/(M+N)! нужное преобразовать формулу, чтобы не было переполнения. подробнее

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

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

27.04.2009, 18:55. Просмотров 7850. Ответов 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 секунды
Как и я....ыы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 05:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru