Міністерство освіти і науки України
Полтавський національний технічний університет
імені Юрія Кондратюка
Факультет інформаційних та телекомунікаційних технологій і систем
Кафедра комп’ютерних та інформаційних технологій і систем
Розрахунково-графічна робота
з дисциплін "Основи дискретної математики"
та "Основи програмування та алгоритмічні мови"
Виконав:
Студент групи 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. Цей процес показано далі:
Після введення розміру програма автоматично обчислює та виводить на екран результати:
Отже, програма виводить всі можливі комбінації - їх кількість рівна числу елементів, так як кожен з них не повинен залишатися на місці.
Другие работы по теме:
Основи ремонту електричних машин побутового призначення
Визначення і характеристика складових основ ремонту електричних машин побутового призначення, як комплексу робота по ліквідації несправностей метою якого є відновлення їх працездатності. Конструктивне, технологічне вдосконалення і теорія старіння машин.
Основи конструювання батарейного циклону
Особливості використання та влаштування батарейних циклонів, оцінка його аеродинамічного опору. Методика визначення загальної кількості батарейних елементів та довжини вихлопної трубки циклонного елементу. Аналіз руху газу в корпусі батарейного циклону.
Балотны агонь
Кароткі змест: Бярозка, заціснутая з усіх бакоў старымі дрэвамі, не ба-чыла сонца, рэдка калі патыхаў на яе свежы ветрык. Была ў яе адзіная ўцеха: ноччу глядзець на далёкі бледны агонь.
Перестановки
Описываются понятия r-перестановок множества, r-сочетания, перестановки с повторениями.
Алгебра 10 класс Мерзляк академ
А. Г. Мерзляк, Д. А. Номіровський, В. Б. Полонський, М. С. Якір АлгебрА і почАтки АнАлізу Підручник для загальноосвітніх навчальних закладів Академічний рівень
Дослідження топологічного визначення верхніх напівґрат
Визначення та властивості упорядкованих множин, приклади діаграм. Дистрибутивні ґрати як один з основних алгебраїчних об'єктів. Поняття нижньої і точної грані, їх властивості та приклади, доказ лем. Застосування та суть топологічних стоунових просторів.
Дослідження лінійно впорядкованого простору ординальних чисел
Джерела теорії впорядкованих і частково впорядкованих алгебраїчних систем. Лінійно впорядкований простір ординальних чисел. Цілком упорядковані множини і їхні властивості. Кінцеві ланцюги і їхні порядкові типи. Загальні властивості ординальних чисел.
Напрямки теорії ймовірностей та математичні дії над ними
Основні напрямки теорії ймовірностей. Сутність понять "подія", "ймовірність події". Перестановки, розміщення та сполучення. Безпосередній підрахунок ймовірностей. Основні теореми додавання та множення ймовірностей. Формула повної ймовірності та Байєса.
Побудова скінченних множин
Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
Знаходження кусково-постійних конфігурацій множин
Основні засади комбінаторики та теорії множин на основі аксіоматики Цермело-Френкеля і використання правила суми й добутку. Знаходження кусково-постійних конфігурацій множин засобами мови програмування IDE C++ Builder з допомогою вбудованого GUI.
Випадкові події
Вивчення поняття випадкових подій. Ознайомлення із класичним, статистичним, геометричним, аксіоматичним означеннями, предметом та методами аналізу (комбінаторний), основними співвідношеннями теорії ймовірності. Розгляд залежності та сумісністю подій.
Дослiдження цифрових iнтегральних мiкросхем
Принципи роботи основних логiчних функцiй цифрової технiки на прикладi базових елементiв серii К155. До найпростіших логічних елементів відносяться такі, як "АБО", "I-НЕ", "НЕ" а також їх комбінації. Основні принципі роботи цих елементів, їх схеми.
Теорія множин. Операції над множинами та їх властивості
Теоретичні основи теорії множин. Основні операції над множинами та їх властивості. Складання програми для обчислення результуючої множини за вихідним і спрощеним виразами. Виконання операцій над множинами, застосування їх властивостей, спрощення виразів.
Способи зберігання графів. Пошук в графі
Програмна робота з графами: операції їх зчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість. Основи пошуку в графі в різних напрямках. Розбиття множини вершин на класи еквівалентності за відношенням зв'язності графу.
Програмування масивів
Тема. . 1. Поняття масиву. До цих під для опрацювання даних використовувались скалярні типи. Однак при обробці великих наборів даних використання скалярних величин стає громіздким. Тому для вирішення таких завдань використовуються структуровані величини. Одним зі структурованих типів є регулярний тип даних, або масив.
Операції над множинами
Міністерство освіти і науки України Херсонський національний технічний університет Кафедра економічної кібернетики Контрольна робота з дисципліни:
Множини: Математичні операції з множинами
Створення програмного модуля "Множина" та організація його правильної структури, визначення методів та властивостей цього модуля (елементами множини є цілі числа). Реалізація математичних операцій з множинами з забезпеченням використання цього класу.
Лісп мова функціонального програмування
Реферат на тему: Лісп – мова функціонального програмування 1. Місце Ліспу у класифікації мов програмування За однією з класифікацій мови програмування діляться на
Уява
Тема: Уява Функція уяви: створення нових образів – випереджуючі відображення реальності. Механізми уяви : дисоціація вражень і елементів у новій комбінації. У
Внутрішнє подання даних стандартних типів
Реферат на тему: Внутрішнє подання даних стандартних типів 1. Біт, байт та інші У комп'ютері числа зберiгаються та обробляються в двiйковiй системі числення. Двійкова цифра 0 або 1 відображається станом елемента пам'яті, який вважається неподільним і називається
Початки комбінаторики
Реферат на тему: 1. Принцип добутку і принцип суми. Розміщення з повтореннями Двома основними правилами комбінаторики є: Принцип суми . Якщо множина A містить m елементів, а множина B – n елементів, і ці множини не перетинаються, то AB містить m+n елементів.
Контекстно-вільні та LA-граматики
Реферат на тему: Контекстно-вільні та LA(1)-граматики 1. Контекстно-вільні граматики Контекстно-вільною , або КВ-граматикою , називається граматика, в якій ліві частини всіх продукцій є нетерміналами. Зміст терміну "контекстно-вільна" полягає в тім, що застосування продукції A w до ланцюжка uAv не залежить, тобто є
Елементи комбінаторики 2
ЕЛЕМЕНТИ КОМБІНАТОРИКИ § 1. Поняття множини. Операції над множинами Поняття множини належить до первісних понять математики, якому не дається означення Множину можна уявити собі як сукупність деяких предметів, об'єднаних за довільною характеристичною ознакою Наприклад, множина учнів класу, множина цифр десяткової нумерації (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), множина натуральних чисел, множина зернин у даному колосі, множина букв українського алфавіту, множина точок на прямій
Множини 3
Практичні заняття Множини Paskal дозволяє оперувати трьома множинами, як трьома типами даних. Для визначення типу множина використовується вираз:
Бульові функції
Реферат на тему: 1. Алгебри бульових виразів і бульових функцій 7.1.1. Основні поняття Множину {0, 1} позначимо літерою B. Множину всіх можливих послідовностей з 0 і 1 – Bn. Такі послідовності за традицією будемо називати наборами або векторами довжини n. Очевидно, Bn містить 2n елементів. Значення 0 і 1 називаються протилежними одне до одного.
Опуклі множини
У курсі “Математичне програмування” та в деяких економічних дослідження використовуються поняття опуклої лінійної комбінації векторів та опуклої множини.
Поняття функції 5
Поняття функції Вивчаючи те чи інше явище, ми, як правило, оперуємо кількома величинами, які пов'язані між собою так, що зміна деяких з них приводить до зміни інших.