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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 64, средняя оценка - 4.69
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
#1

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

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

Перестановки: чтобы любые две соседние перестановки отличались только порядком двух соседних элементов - C++
Вводится число n &lt;= 8. Вывести все перестановки чисел 1,2..,n, так, чтобы две любые две соседние перестановки отличались только порядком...

комбинаторика - C++
Здравствуйте! Я решаю задачи по дискретной математике на языке С.В интернете масса примеров задач на тему комбинаторики, но на языке...

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

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

Комбинаторика - C++
Здравствуйте все. В данный момент дпополнительно решил заняться комбинаторикой, столкнулся с задачей, и никак не могу её решить.Суть...

Комбинаторика на С++ - C++
Нужно составить программу, или скорее функцию, которая для заданного натурального числа k выводит все возможные произведения k чисел с...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.04.2009, 18:55
Привет! Вот еще темы с ответами:

Комбинаторика - C++
От пользователя требуется ввести n. Результат должен быть таким:

Перестановка.(Комбинаторика) - C++
Прошу помощи. Объясните пожалуйста тугодуму этот код. Какой день его пытаюсь понять. Не как не могу в нём разобраться. Вроде знаю как...

Комбинаторика style - C++
Здравствуйте, помогите разобраться с задачей по комбинаторике. Условие: http://codeforces.com/problemset/problem/630/F Решение: ...

Комбинаторика. Сочетания - C++
Добрый день! Прошу помочь со следующей задачкой: генерация сочетания по номеру(порядок лексикографический). Толковое объяснение нашел...


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

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

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