Тема. КОМБІНАТОРНІ ОБ'ЄКТИ
Тема. Комбінаторні задачі
Комбінаторика - розділ математиків, в якому вивчаються найпростіші «з'єднання» чисел.
1) Формули комбінаторики
Задачі:
1. Скількома способами можна скласти розклад на день з 5 різних предметів, якщо в класі вивчається 10 предметі?
2. Скільки різних чотирицифрових чисел можна скласти з чотирьох різних заданих цифр, не повторюючи їх?
3. Скільки діагоналей має опуклий n-кутник?
1.Перестановки - з'єднання, які можна скласти з n предметів, міняючи всіма можливими способами їх порядок.
2.Розміщення - з'єднання, що містять по n предметів з числа m даних, що розрізняються або порядком предметів, або самими предметами.
3. Комбінації - з'єднання, що містять по n предметів з m, що розрізняються один від одного, принаймні, одним предметом.
Додаткові завдання:
1. Скількома способами можна розподілити n тем наукових робіт серед m учнів (тем більше, ніж учнів). Написати програму.
2. Перевірити справедливість рівності  для m<10.
3. Скількома способами можна розмістити n осіб за столом, біля якого поставлено n стільців? Написати програму.
4. Двоє хлопчиків Роман і Діма мають по N друзів (1<=N<=200). Вирішили вони позмагатися хто з них більше організує вечірок. Роман вирішив запрошувати кожен раз до себе в гості по K (1<= K<= N) друзів, а Діма - по М (1<= М<= N) друзів. Хто з хлопчиків більше організує вечірок і на скільки, якщо вони домовились, що кожен раз компанія має бути іншою.
Наприклад.
Якщо є четверо друзів (1, 2, 3, 4) і вони мають приходити в гості по троє, то таких вечірок буде чотири ( (1, 2, 3); (1, 2, 4); (1, 3, 4); (2, 3, 4) ).
5. Скількома способами можна вибрати делегацію в складі n представників з m чоловік. Написати програму.
6. Побудувати трикутник Паскаля з n рядків
Тема. Перебір з поверненням
ПОСТАВ_І_ВПРАВО - ставить туру в клітинку з заданими координатами і переміщає горизонтальний покажчик на одну позицію вправо , а вертикальний установлює на першу позицію (процедура)
ЗНІМИ_І_ВЛІВО - знімає туру з даної клітки і переміщає горизонтальний покажчик на одну позицію вліво , вертикальний покажчик встановлює в позицію тури, на яку тепер указує горизонтальний покажчик ( процедура )
ПРАВИЛЬНА_КЛІТИНКА - логічна функція. Повертає істина, якщо туру можна поставити в дану клітку, і хибно, якщо поставити в клітинку не можна.
ВЛІВО - переміщає горизонтальний покажчик на одну позицію вліво і установлює вертикальний покажчик на туру в цій вертикалі (процедура).
ВИВЕДЕННЯ - виводить на екран результат (процедура)
Тепер наш алгоритм може бути представлений так:
алг Пошук_з_поверненням
поч
П_Г:=1
П_В:=1
ПОСТАВ_І_ВПРАВО П_В:= П_В+1
поки П_Г<>0
пц поки ( не ПРАВИЛЬНА_КЛІТИНКА ) і (П_Г < n+1)
пц
П_В:=П_В+1
кц
якщо П_В < n+1
то ПОСТАВ_І_ВПРАВО
інакше ЗНІМИ_І_ВЛІВО
все
якщо П_Г =n+1
то ВИВЕДЕННЯ
ВЛІВО
все
кц
до П_Г=0
кін
Деталі
Вибiр складається з N деталей. Є N верстатiв, на кожному з яких можна виготовити будь-яку деталь. Для кожних верстату та деталей вiдомий час t[i,k] виготовлення k-ї деталi на i-му верстатi. Напишiть програму, яка визначить, на якому верстатi слiд виготовити кожну де- таль, щоб одночасно почавши виготовляти всi деталi, завершити виго- товлення всмх деталей якнайшвидше.
Технiчнi умови
1) Iмена файлiв програми, вхiдних та вихiдних даних: DETAILS.???, DETAILS.DAT, DETAILS.SOL, де ??? - PAS, BAS, C, CPP (в залежностi вiд мови програмування).
2) Перший рядок вхiдного файлу мiстить кiлькiсть текстiв. Перший рядок кожного тексту мiстить кiлькiсть верстатiв та деталей N(1<=N<=50). Кожен з наступних N рядкiв мiстить тривалостi виготов- лення деталей на вiдповiдному верстатi t[i,1], t[i,2],...,t[i,N], вiдокремленi комами. Кожне з цих чисел натуральне i не перевершує 100.
3) Коректнiсть вхiдних даних гарантується.
4) У вихiдний файл для кожного тесту треба послiдовно вивести в один рядок. Номери деталей, якi треба виготовити вiдповiдно на 1-му, 2-му,..., N-му верстатах, вiдокремивши їх пропусками. В наступний ря- док треба вивести час вiд початку до завершення виготовлення всiх де- талей.
5) Для кожного тесту досить знайти один розв'язок.
Приклад вхiдного та вихiдного файлiв
Вхiдний(DETAILS.DAT):
2
2
3,2
1,2
3
3,3,3
3,3,3
3,3,3
Вихiдний (DETAILS.SOL):
2 1
2
1 2 3
3
Греко-латинський квадрат
Греко-латинським квадратом називається квадрат N x N, в кожному рядку, в кожному стовпці і в кожній діагоналі якого містяться всі цілі числа від 1 до N. Приклад такого квадрата 4 х 4.
Написати програму, яка:
n будує хоча б один квадрат порядку N;
In.txt
4
Out.txt
1 2 3 4
4 3 2 1
2 1 4 3
3 4 1 2 |
