Міністерство освіти і науки України
Полтавський національний технічний університет
імені Юрія Кондратюка
Факультет інформаційних та телекомунікаційних технологій і систем
Кафедра комп’ютерних та інформаційних технологій і систем
Розрахунково-графічна робота
з дисциплін «Основи дискретної математики»
та «Основи програмування та алгоритмічні мови»
Виконав:
Студент групи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}.
Другий циклвиконує nразів перестановку, якаявляється циклом.
Третій цикл — робить перестановку всіх елементів крім останнього, так як він міняється зпершим. Це робиться «вручну».
Четвертий цикл — виводить на дисплей результат роботи третього.
Функція swap(int*pointer, int*pointer) має два параметри — вказівники на змінні,які треба поміняти місцями. Це реалізується через третю змінну. Власне функція ніякогозначення не повертає (void).
Програмазакінчується вивільненням пам’яті та поверненнямповідомлення ОС про правильне закінчення роботи.
Реалізаціяпрограми
#include
using namespacestd;
void swap (int *px,int *py)
{
int temp;
temp=*px;
*px=*py;
*py=temp;
}
int main ()
{
int n=0,k;
cout
cin>>n;
int *pNums = newint [n] ;
cout
for (int j=0; j
{
pNums [j] =j+1;
cout
}
cout
for (int y=0; y
{
for (int i=0; i
swap (pNums [i],pNums[i+1]);
}
cout
for (k=0; k
{cout
}
cout
}
cout
delete pNums;
cin. get ();
cin. get ();
return 0;
}
Вхідні дані: 11 — кількість елементів
Вихідні дані: всіможливі комбінації елементів у вигляді матриці.
Після закускупрограми користувачу необхідно спочатку ввести розмірність матриці N. Цей процес показано далі:
/>
Після введеннярозміру програма автоматично обчислює та виводить на екран результати:
/>
Отже, програмавиводить всі можливі комбінації — їх кількість рівна числу елементів, так яккожен з них не повинен залишатися на місці.