: integer);
var i: integer; beginfor j: = 1 to k dowrite (p [j]: 4); writelnend; {print}
procedure cnk (n, k: integer); procedure gen (m, L: integer); var i: integer; beginif m = 0 then print (k) elsefor i: = L to n-m +1 dobegin
p [k-m +1]: = a [i];
gen (m-1, i +1)
end
end; {gen}
begin {cnk} gen (k, 1) end; {cnk} begin {Main} readln (n, k); for i: = 1 to n doa [i]: = i; { заповнити масив можна і по - іншому }
cnk (n, k)
end.
Зауважимо, що власне генерація поєднань виробляється в рекурсивної підпрограмі gen. Вона має такі параметри: m - скільки елементів з безлічі нам ще залишилося вибрати і L - починаючи з якого елементу вихідного безлічі, слід вибирати ці m елементів. Зверніть увагу, що саме вкладена структура опису процедур cnk і gen дозволяє не передавати при рекурсивних викликах значення n і k а з основної програми звертатися до процедури cnk з параметрами, відповідними постановці завдання, не вдаючись у подробиці її вирішення. Такий спосіб будемо застосовувати і надалі.
Генерація всіх підмножин даної множини
При рішенні олімпіадних завдань найчастіше заздалегідь невідомо, скільки саме елементів вихідного безлічі повинно входити в шукане підмножина, тобто необхідний перебір всіх підмножин. Однак, якщо потрібно знайти мінімальне підмножина, тобто складається як можна з меншого числа елементів (або максимальне підмножина), то найефективніше організувати перебір так, щоб спочатку перевірялися всі підмножини, що складаються з одного елемента, потім з двох, трьох і т. д. елементів (для максимального підмножини - у зворотному порядку). У цьому випадку, перше ж підмножина, що задовольняє умові завдання і буде шуканим, і подальший перебір слід припинити. Для реалізації такого перебору можна скористатися, наприклад, процедурою cnk, описаної в попередньому розділі. Введемо в неї ще один параметр: логічну змінну flag, яка буде позначати, задовольняє поточне поєднання елементів умовою задачі або немає. При отриманні чергового поєднання замість його друку звернемося до процедури його перевірки check, яка і визначатиме значення прапора. Тоді початок процедури gen слід переписати так:
procedure gen ( m , L : integer );
var i: integer;
begin
if m = 0 then
begin
check (p, k, flag);
if flag then exit
end
else ...
Далі процедура дослівно збігається з попередньою версією. В основній же програмі єдине звернення до даної процедури слід замінити наступним фрагментом
k: = 0;
flag: = false;
repeat
k: = k +1;
cnk ( n , 1, flag)
until flag or (k = n),
if flag then print (k)
else writeln (' no solution ');
Очевидно також, що в основній програмі запит значення змінної k тепер не проводиться.
Існує також альтернативний підхід до перебору всіх підмножин того чи іншого безлічі. Кожна підмножина можна охарактеризувати, вказавши щодо кожного елемента вихідної безлічі, належить воно даним подмножеству чи ні. Зробити це можна, поставивши у відповідність кожному елементу множини 0 або 1. Тобто кожному підмножині відповідає n -значне число у двійковій системі числення (строго кажучи, так як числа можуть починатися з довільної кількості нулів, які значущими цифрами не рахуються, то слід зауважити, що у відповідність ставляться n - менш - значні числа). Звідси випливає, що повний перебір всіх підмножин даної множини відповідає перебору всіх чисел у двійковій системі числення. Тепер легко підрахувати і кількість різних підмножин даної множини. Воно дорівнює 2 n - 1 (або 2 n , з урахуванням порожнього множини). Таким чином, зіставляючи два способи перебору всіх підмножин даної множини, ми отримали наступну формулу:
В
br/>
Те Тобто, в рамках зробленої вище оцінки на кількість допустимих варіантів у переборі, ми можемо розглянути всі підмножини вихідного безлічі тільки при n ВЈ 20.
Перш, ніж перейти до розгляду програм, відповідних другому способу перебору, вкажемо, коли застосування цих програм доцільно. По-перше, дані програми легко використовувати, коли необхідно в будь-якому випадку перебрати всі підмножини даної множини (Наприклад, потрібно знайти всі рішення задовольняють тому чи іншому умовою). По-...
