Контрольная работа: Наведення усіх перестановок елементів множини

Міністерство освіти і науки України

Полтавський національний технічний університет

імені Юрія Кондратюка

Факультет інформаційних та телекомунікаційних технологій і систем

Кафедра комп’ютерних та інформаційних технологій і систем

Розрахунково-графічна робота

з дисциплін "Основи дискретної математики"

та "Основи програмування та алгоритмічні мови"

Виконав:

Студент групи 101-ТН

Селін Ігор

Керівник:

д.т.н. Ляхов Олександр Логвинович

Полтава 2010

Постановка задачі

УМОВА ЗАДАЧІ:

Задано натуральне число n. Навести всі перестановки елементів множини , у яких жоден елемент не залишається на місці.

Перестановка - це перевпорядкованість наборів елементів, об’єктів або функція, що задає таку перевпорядкованість.

Множина - це деяка визначена сукупність елементів чи об’єктів.

Розв’ язання задачі

Для більш наглядного представлення даної задачі розглянемо приклад на якому розглянемо всі можливі варіанти перестановок при 3 елементах.

G={1,2,3}

(1,2,3) - Так

(1,3,2) - ͳ

(2,1,3) - Так

(2,3,1) - ͳ

(3,1,2) - Так

(3,2,1) - ͳ

З них відповідають умові задачі лише 3 перестановки. Цього методу можна добитися послідовним здвигом вправо чисел послідовності. Перше стає на місце другого, друге на третє, останнє на перше.

Наприклад:

(1,2,3) → (3,1,2) → (2,3,1)

Алгоритм задачі

Необхідно визначити яка вхідні та проміжні дані будуть використовуватися.

Насамперед, n-розмірність множини, тобто факторіал. Також потрібно динамічний масив для перестановки елементів. Для прорахунку всіх можливих елементів використаємо цикл із лічильником.

Перший цикл виводить початкову комбінацію елементів {1…n}.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--