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


Полнотекстовый поиск по базе:

Главная >> Контрольная работа >> Математика


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




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

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

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

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

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

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

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

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

Виконав:

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

Селін Ігор

Керівник:

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

ППрямоугольник 2олтава 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. Цей процес показано далі:

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

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

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

  • Елементи комбінаторики. Початки теорії ймовірностей

    Учебное пособие >> Математика
    ... оскільки в множині В за умовою т елементів. Цим усі елементи множини A U В ... елементів множини А = {1, 2, 3} можна утворити шість перестановок: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). Число перестановок у множині з п елемент ... наведене ...
  • Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів

    Курсовая работа >> Информатика, программирование
    ... полегшити наступний пошук елементів в такій відсортованій множині. Вибір алгоритму ... ів; M - кількість перестановок елементів. Очевидно, що ці числа ... порядку O(N*ln(N)). Всі наведені викладки справедливі для ... масив B і усі входження цього елемента в дереві зам ...
  • Особливості розробки дизайну меблів

    Курсовая работа >> Остальные работы
    ... необхідно з усіх п !перестановок вибрати лише ті, які містять т неповторювальних елементів. Таким випадок ... дають змогу розкласти множину А, що складається з п елементів, на суму пі ... проміжків між блоками. Наведені способи застосування комбінаторного анал ...
  • Захист данних

    Учебное пособие >> Информатика, программирование
    ... випромінювань і наведень. 2. Локальні ... множина, використовувана для кодування інформаційних знаків. Текст - впорядкований набір з елемент ... застосування бітових перестановок, що ефективно ... жорстко структуровані і регламентують усі етапи проектування, створення ...
  • Менеджмент

    Учебное пособие >> Менеджмент
    ... ітністю, відбиваючи множинність, різну складність ... ться відмітними особливостями, що наведені у табл. 3.3. Таблиця ... ональні повноваження. Між усіма названими вище елементами ОСУ існують складн ... з резерву. Серед планових перестановок особливе місце займає ротац ...
  • Застосування симетричних многочленів

    Курсовая работа >> Математика
    ... Наслідок. Множина всіх симетричних многочлен ... насамперед такі зауваження. Усіх членів певного степеня ... з цим Але тоді елемент поля Р як результат ви ... отримані за допомогою перестановок змінних x, y, ... через при умові (результати наведені в таблиці 2.2), введено ...