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

3228
знаков
0
таблиц
2
изображения

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

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

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

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

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

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

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

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

Виконав:

Студент групи 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 <iostream>

using namespace std;

void swap (int *px, int *py)

{

int temp;

temp=*px;

*px=*py;

*py=temp;

}

int main ()

{

int n=0,k;

cout<<"Enter matrix size: ";

cin>>n;

int *pNums = new int [n] ;

cout<<"{ ";

for (int j=0; j<n; j++)

{

pNums [j] =j+1;

cout<<pNums [j] <<" ";

}

cout<<"}"<<endl;

for (int y=0; y<n-1; y++)

{

for (int i=0; i<n-1; i++) {

swap (pNums [i],pNums [i+1]);

}

cout<<"{ ";

for (k=0; k<n; k++)

{cout<<pNums [k] <<" ";

}

cout<<"}"<<endl;

}

cout<<endl;

delete pNums;

cin. get ();

cin. get ();

return 0;

}

Вхідні дані: 11 - кількість елементів

Вихідні дані: всі можливі комбінації елементів у вигляді матриці.

Після закуску програми користувачу необхідно спочатку ввести розмірність матриці N. Цей процес показано далі:

Після введення розміру програма автоматично обчислює та виводить на екран результати:

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


Информация о работе «Наведення усіх перестановок елементів множини»
Раздел: Математика
Количество знаков с пробелами: 3228
Количество таблиц: 0
Количество изображений: 2

Похожие работы

Скачать
54810
5
18

... . Поклавши у формулі (4) а = b = 1, дістанемо Нехай маємо скінченну множину, яка містить п елементів. Тоді кількість підмножин цієї множини дорівнює 2n. Наприклад, для множини {a,b,c} маємо Ø, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}.   ПОЧАТКИ ТЕОРІЇ ЙМОВІРНОСТЕЙ   § 1. Про предмет теорії ймовірностей До цього часу розглядалися задачі, в яких результат дії був однозначно ...

Скачать
43832
1
0

... сортування включенням; - сортування вибором; - сортування обміном. У курсовій роботі ми детально розглянемо швидкі алгоритми сортування елементів масиву, проведемо їх порівняльний аналіз. Крім цього, розглянемо і прямі методи сортування, їх позитиви і недоліки, що дасть змогу краще визначити ефективність і складність швидких алгоритмів сортування. Розділ І. Прямі методи сортування масивів   ...

Скачать
39362
0
15

... структуро творча одиниця діяльності (операція діяльності) КОМБІНАТОРИКА ФОРМОТВОРЕННЯ Комбінаторика — математичний термін, запозичений теорією і практикою художнього проектування. Комбінаторика в дизайні — особливий творчий підхід до формотворення, заснований на пошуку і дослідженні закономірностей варіантної зміни просторових структур, а також способів упорядкування проектування об'єктів ...

Скачать
82012
21
21

... прапорець Space Egually, то у вікні Spacing можна точно встановити відстань між компонентами, що вирівнюються, у вибраній системі одиниць. Помітимо, що вказані команди вирівнювання не діють на зафіксовані компоненти.   Рисунок. 8.1 - Розміщення на друкарскій платі 9          ТРАСУВАННЯ ПЕЧАТНИХ СПОЛУЧЕНЬ ПЕЧАТНОЇ ПЛАТИ В САПР PCAD   9.1      Установка кроку сітки В деяких випадках, ...

0 комментариев


Наверх