Наведення усіх перестановок елементів множини
Перестановка як перевпорядкованість наборів елементів, об’єктів або функція, що задає таку перевпорядкованість. Всі можливі варіанти перестановок елементів множини за умови наявності трьох елементів за умови, що жоден елемент не залишається на місці.
| Рубрика | Математика |
| Вид | задача |
| Язык | украинский |
| Дата добавления | 23.06.2010 |
| Размер файла | 222,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
5
Міністерство освіти і науки України
Полтавський національний технічний університет
імені Юрія Кондратюка
Факультет інформаційних та телекомунікаційних технологій і систем
Кафедра комп'ютерних та інформаційних технологій і систем
Розрахунково-графічна робота
з дисциплін "Основи дискретної математики"
та "Основи програмування та алгоритмічні мови"
Виконав:
Студент групи 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. Цей процес показано далі:
Після введення розміру програма автоматично обчислює та виводить на екран результати:
Отже, програма виводить всі можливі комбінації - їх кількість рівна числу елементів, так як кожен з них не повинен залишатися на місці.
Подобные документы
Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
задача [112,0 K], добавлен 23.06.2010Применение леммы Бернсайда к решению комбинаторных задач. Орбиты группы перестановок. Длина орбиты группы перестановок. Лемма Бернсайда. Комбинаторные задачи. "Метод просеивания". Формула включения и исключения.
дипломная работа [163,6 K], добавлен 14.06.2007Поняття сукупності предметів, об'єднаних за певною характеристичною ознакою. Основні загальноприйняті множини (геометрична фігура, ГМТ, область визначення та значень функції). Позначення множин, їх елементи, належність об'єктів та способи задання.
презентация [517,1 K], добавлен 19.01.2011Поняття множини. Операції над множинами. Об’єднання і переріз двох множин. Різниця і доповненя множин. Множини з відношеннями. Прямий (декартів) добуток множин. Бінарні відношення. Відношення еквівалентності. Відношення порядку. Предикати.
курсовая работа [239,3 K], добавлен 10.06.2007Содержание правил суммы и произведения; их применение с целью решения комбинаторных задач. Виды комбинаторных соединений. Обозначение и свойства факториала. Формулы расчета всех возможных перестановок и размещений. Понятие и разновидности сочетаний.
реферат [22,1 K], добавлен 08.09.2014Прийняття рішень як основний компонент систем управління проектами. Методика розробки програми для знаходження множини оптимальних рішень за критерієм Байєса-Лапласа з формуванням матриці ймовірностей реалізації умов за експоненційним законом розподілу.
курсовая работа [802,8 K], добавлен 08.10.2010Вивчення існування періодичних рішень диференціальних систем і рівнянь за допомогою властивостей симетричності (парність, непарність). Основні теорії вектор-функцій, що відбивають. Побудова множини систем, парна частина загального рішення яких постійна.
курсовая работа [87,8 K], добавлен 20.01.2011Поняття про бінарні відношення, способи їх задання, існуючі операції, характерні властивості. Відношення еквівалентності, порядку, домінування й переваги. Поняття та значення R-оптимальності, найкращого, найгіршого, максимального й мінімального елементів.
реферат [1,3 M], добавлен 04.10.2015Історія виникнення лабіринту. Лабіринт крітського царя Міноса - одне із семи чудес світу. Перші здогади "Правило руки". Лабіринти і замкнені криві, розв'язування різних лабіринтних задач, застосування елементів теорії графів і теорії ймовірностей.
реферат [7,3 M], добавлен 29.09.2009Наочне представлення про об'єкт та його зображення в тривимірному просторі. Порядок тривимірний зміни масштабу фігури, її зсуву та обертання. Особливості відображення елементів у просторі, просторовий перенос та тривимірне обертання навколо довільної осі.
лабораторная работа [701,4 K], добавлен 19.03.2011
