Название: Наведення усіх перестановок елементів множини
Вид работы: контрольная работа
Рубрика: Математика
Размер файла: 68.48 Kb
Скачать файл: referat.me-215762.docx
Краткое описание работы: Перестановка як перевпорядкованість наборів елементів, об’єктів або функція, що задає таку перевпорядкованість. Всі можливі варіанти перестановок елементів множини за умови наявності трьох елементів за умови, що жоден елемент не залишається на місці.
Наведення усіх перестановок елементів множини
Міністерство освіти і науки України
Полтавський національний технічний університет
імені Юрія Кондратюка
Факультет інформаційних та телекомунікаційних технологій і систем
Кафедра комп’ютерних та інформаційних технологій і систем
Розрахунково-графічна робота
з дисциплін "Основи дискретної математики"
та "Основи програмування та алгоритмічні мови"
Виконав:
Студент групи 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 , i nt * 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. Цей процес показано далі:
Після введення розміру програма автоматично обчислює та виводить на екран результати:
Отже, програма виводить всі можливі комбінації - їх кількість рівна числу елементів, так як кожен з них не повинен залишатися на місці.
Похожие работы
-
Алгебра 10 класс Мерзляк академ
А. Г. Мерзляк, Д. А. Номіровський, В. Б. Полонський, М. С. Якір АлгебрА і почАтки АнАлізу Підручник для загальноосвітніх навчальних закладів Академічний рівень
-
Комбінаторика
Розділ . Елементи теорії множин §1.1. Поняття множини Поняття множини є одним з фундаментальних у математиці. Воно належить до понять яким не можна дати строге означення, тобто до так званих первісних, які не можна визначити через простіші поняття. Інтуєтивно множину розуміють як сукупність (сімейство, набір, зібрання, клас) деяких, обєктів об’єднаних за певною ознакою чи властивістю.
-
Дослідження топологічного визначення верхніх напівґрат
Визначення та властивості упорядкованих множин, приклади діаграм. Дистрибутивні ґрати як один з основних алгебраїчних об'єктів. Поняття нижньої і точної грані, їх властивості та приклади, доказ лем. Застосування та суть топологічних стоунових просторів.
-
Дослідження лінійно впорядкованого простору ординальних чисел
Джерела теорії впорядкованих і частково впорядкованих алгебраїчних систем. Лінійно впорядкований простір ординальних чисел. Цілком упорядковані множини і їхні властивості. Кінцеві ланцюги і їхні порядкові типи. Загальні властивості ординальних чисел.
-
Напрямки теорії ймовірностей та математичні дії над ними
Основні напрямки теорії ймовірностей. Сутність понять "подія", "ймовірність події". Перестановки, розміщення та сполучення. Безпосередній підрахунок ймовірностей. Основні теореми додавання та множення ймовірностей. Формула повної ймовірності та Байєса.
-
Теорія і практика обчислення визначників
Основні поняття і теореми. Обчислення визначників методом зміни елементів, представлення їх у вигляді суми, виділення лінійних множників, методом рекурентних співвідношень, знижуючи їхній порядок за допомогою розкладання за елементами рядка або стовпця.
-
Побудова скінченних множин
Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
-
Знаходження кусково-постійних конфігурацій множин
Основні засади комбінаторики та теорії множин на основі аксіоматики Цермело-Френкеля і використання правила суми й добутку. Знаходження кусково-постійних конфігурацій множин засобами мови програмування IDE C++ Builder з допомогою вбудованого GUI.
-
Елементи комбінаторики. Початки теорії ймовірностей
Основні принципи і елементи комбінаторики. Теорія ймовірностей: закономірності масових випадкових подій, дослідження і узагальнення статистичних даних, здійснення математичного і статистичного аналізу. Постановка і вирішення задач економічного характеру.
-
Випадкові події
Вивчення поняття випадкових подій. Ознайомлення із класичним, статистичним, геометричним, аксіоматичним означеннями, предметом та методами аналізу (комбінаторний), основними співвідношеннями теорії ймовірності. Розгляд залежності та сумісністю подій.