Сайт підготовки до олімпіади з інформатики

Тема. КОМБІНАТОРНІ ОБ'ЄКТИ

Тема. Комбінаторні задачі

Комбінаторика - розділ математиків, в якому вивчаються найпростіші «з'єднання» чисел.

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