Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Комбінаторика.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Лабораторна робота №1. Тема: Комбінаторика
(Розміщення, перестановки, комбінації, біном Ньютона)
Комбінаторика – це галузь математики, предметом якої є теорія скінченних множин. Значна кількість теорем і формул комбінаторики ґрунтується на двох елементарних правилах, які називаються правилами суми і добутку.
Правило суми - якщо деякий об’єкт a можна вибрати m способами, а об’єкт b – n способами, причому ніякий вибір a не збігається з жодним з виборів b, то один з об’єктів a або b можна вибрати m+n способами.
Правило добутку – якщо деякий об’єкт a можна вибрати m способами і при кожному виборі об’єкта a об’єкт b можна вибрати n способами, то вибір пари (a, b) можна здійснити mn способами.
Правило суми та добутку можна узагальнити на будь-яку більшу кількість об’єктів.
У комбінаториці розглядають три типи сполук – розміщення, перестановки та комбінації.
Розміщення з n елементів по m називають сполуки, що складаються з m елементів, взятих з n, і відрізняються або складом елементів, або їх порядком. Кількість всіх можливих розміщень розраховують за формулою:
без повторень - з повтореннями
EMBED Equation.3 EMBED Equation.3
Перестановками n елементів називають сполуки, що відрізняються тільки порядком елементів. Кількість всіх можливих перестановок розраховують за формулою:
без повторень - з повтореннями
EMBED Equation.3 EMBED Equation.3
Комбінаціями з n елементів по m називають сполуки, що складаються з m елементів, взятих з n, і відрізняються тільки складом (порядок не має значеня). Кількість всіх можливих комбінацій розраховують за формулою:
без повторень - з повтореннями
EMBED Equation.3 EMBED Equation.3
Алгоритм генерування лексикографічно наступної перестановки
Алгоритм генерування лексикографічно наступної сполуки n-елементної множини X={1,2,…,n} по r елементів.
Біном Ньютона (n - додатнє ціле):
Завдання
Запрограмувати за варіантом обчислення кількості комбінацій розміщення (перестановок, комбінацій, алгоритму визначення наступної лексикографічної сполуки, перестановки) та формулу бінома Ньютона і побудувати за допомогою неї розклад за варіантом.
Варіант 1.
Задане додатне ціле число n. Розташувати у лексикографічному порядку всі перестановки множини {1,2,…,n}.
Побудувати розклад (x+y)5.
Варіант 2.
Задане додатне ціле число n і невід’ємне ціле число r, (r<=n). Розташувати у лексикографічному порядку всі сполуки без повторень із r елементів множини {1,2,…,n}.
Побудувати розклад (x-y)5.
Варіант 3.
Задане додатне ціле число n і невід’ємне ціле число r, (r<=n). Розташувати у лексикографічному порядку всі розміщення без повторень із r елементів множини {1,2,…,n}.
Побудувати розклад (x+y)6.
Варіант 4.
Задане додатне ціле число n. Побудувати всі сполуки без повторень елементів множини {1,2,…,n}.
Побудувати розклад (x-y)6.
Варіант 5.
Задане додатні цілі числа n та r. Побудувати у лексикографічному порядку всі розміщення з повтореннями із r елементів множини {1,2,…,n}.
Побудувати розклад (x+y)7.
Варіант 6.
Задане додатні цілі числа n та r. Побудувати у лексикографічному порядку всі сполуки з повтореннями із r елементів множини {1,2,…,n}.
Побудувати розклад (x-y)7.
Варіант 7.
Визначити лексикографічно наступну перестановку для кожної з перестановок: 1432, 54123, 12453, 45231, 6714235, 31528764.
Побудувати розклад (x-y)8.
Варіант 8.
Розташувати наведені перестановки елементів множити {1,2,3,4,5,6} у лексикографічному порядку: 234561, 231456, 165432, 156423, 543216, 541236, 231465, 314562, 432561, 654321, 654312, 435612.
Побудувати розклад (x+y)8.
Варіант 9.
Використовуючи алгоритм побудови лексикографічно наступної перестановки, записати перші 12 перестановок елементів множини {1,2,3,4,5,6}.
Побудувати розклад (x-y)9.
Варіант 10.
Використовуючи алгоритм побудови лексикографічно наступної сполуки, виписати всі сполуки по 4 елементи множини {1,2,3,4,5,6}.
Побудувати розклад (x+y)9.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора