Міністерство освіти Республіки Білорусь
Установа освіти
«Гомельський державний університет ім. Ф. Скорини »
Математичний факультет
Кафедра МПУ
Реферат
Комбінаторні задачі
Виконавець:
Студентка групи М-42 Макарченко А.Ю.
Науковий керівник: Долинський М.С.
Гомель 2005
Зміст
Введення
Генерація k-елементних підмножин
Генерація всіх підмножин даної множини
Генерація всіх перестановок n-елементної множини
Розбиття множини
Висновок
Література
Введення
Завдання дискретної математики, до яких належить більшість олімпіадних завдань з інформатики, часто зводяться до перебору різних комбінаторних конфігурацій об'єктів та вибору серед них найкращого, з точки зору умови тієї або іншої задачі. Тому знання алгоритмів генерації найбільш поширених комбінаторних конфігурацій є необхідною умовою успішного вирішення олімпіадних завдань в цілому. Важливо також знати кількість різних варіантів для кожного типу комбінаторних конфігурацій, так як це дозволяє реально оцінити обчислювальну трудомісткість вибраного алгоритму розв'язання того чи іншого завдання на перебір варіантів і, відповідно, його прийнятність для вирішення даної задачі, з урахуванням її розмірності. Крім того, при вирішенні завдань корисним виявляється вміння для кожної з комбінаторних конфігурацій виконувати наступні операції: за наявною конфігурації одержувати наступну за нею в лексикографічному порядку; визначати номер даної конфігурації в лексикографічній нумерації всіх конфігурацій, і, навпаки, за порядковим номером виписувати відповідну йому конфігурацію .
У комбінаториці такі підмножини називають сполученнями із n елементів по k елементів і позначають C n k. Їх кількість виражається наступною формулою:
Однак при програмуванні набагато зручніше використовувати наступні рекурентні співвідношення:
Пояснюється це тим, що у формулі (1) чисельник і знаменник ростуть дуже швидко, тому в силу особливостей комп'ютерної арифметики не завжди можливо точно обчислити значення C n k, навіть коли останнє не перевершує максимально представимое ціле число.
При фіксованому значенні n максимального значення число сполучень досягає при k = n / 2 (вірніше, для парного n максимум один і він зазначений, а для непарного - максимум досягається на двох сусідніх значеннях k: [n / 2] і
[N / 2] +1). Тому особливо корисною виявляється наступна оцінка для парних n [4] (очевидно, що при непарних n відмінності будуть мінімальними), заснована на формулі Стірлінга:
Якщо допустити, що за час, відведений для виконання завдання, ми можемо перебрати близько 10 6 варіантів, то з формули (3) випливає, що генерацію всіх сполучень з n елементів для будь-якого фіксованого k можна проводити для n £ 24.
Зазвичай генерацію всіх k-елементних підмножин проводять в лексикографічному порядку, тим паче що в даному випадку це не призводить ні до ускладнення алгоритму, ні до збільшення його обчислювальної трудомісткості. Нагадаємо, що порядок підмножин називається лексикографічним, якщо для будь-яких двох підмножин справедливо, що раннє повинно бути згенеровано то з них, з індексів елементів якого можна скласти менше k-значне число в n-річної системі числення (або в десятковій, для n <10 ). Так, для n = 6 і k = 3 поєднання з третього, першого і п'ятого елемента має бути створене раніше, ніж з другого, третього і четвертого, так як 135 <234.
Розглянемо рекурсивний алгоритм вирішення даної задачі. Ідея відомості даної задачі до задачі меншої розмірності наступна. Першим елементом підмножини може бути будь-який елемент, починаючи з першого і закінчуючи (n - k + 1)-м елементом. Після того, як індекс першого елемента підмножини зафіксовано, залишилося вибрати k - 1 елемент з елементів з індексами, більшими, ніж у першого. Далі поступаємо аналогічно. Коли обраний останній елемент, то ми досягли кінцевого рівня рекурсії і вибране підмножина можна обробити (проаналізувати або роздрукувати). У пропонованій нижче програмі масив a містить значення елементів вихідної множини і може бути заповнений довільним чином. У масиві p будемо формувати чергове поєднання з k елементів.
const nmax = 24;
type list = array [1 .. nmax] of integer; var k, i, j, n, q: integer; a, p: list; procedure print (k: 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 з параметрами, що відповідають постановці завдання, не вдаючись у подробиці її рішення. Такий спосіб будемо застосовувати і надалі.
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, з урахуванням порожнього множини). Таким чином, зіставляючи два способи перебору всіх підмножин даної множини, ми отримали наступну формулу:
Тобто, в рамках зробленої вище оцінки на кількість допустимих варіантів у переборі, ми можемо розглянути всі підмножини вихідного безлічі тільки при n £ 20.
Перш, ніж перейти до розгляду програм, відповідних другим способом перебору, зазначимо, коли застосування цих програм доцільно. По-перше, дані програми легко використовувати, коли необхідно в будь-якому випадку перебрати всі підмножини даної множини (наприклад, потрібно знайти всі рішення задовольняють того чи іншого положення). По-друге, коли з точки зору умови задачі не має значення, скільки саме елементів повинно входити в шукане підмножина. На прикладі такого завдання ми і напишемо програму генерації всіх підмножин вихідного безлічі в лексикографічному порядку. Завдання взята з книги [5].
Умова. Дан цілочисельний масив a [1 .. N] (N £ 20) і число M. Знайти підмножина елементів масиву a [i1], a [i2], ... a [ik] таке, що 1 £ i1 <i2 <i3 <... <Ik £ N і a [i1] + a [i2] + ... + A [ik] = M.
Рішення. В якості вирішення наведемо процедуру генерації всіх підмножин, які можна скласти з елементів масиву і функцію перевірки конкретного підмножини на відповідність умові завдання.
function check (j: longint): boolean;
var k: integer; s: longint;
begin
s: = 0;
for k: = 1 to n do
if ((j shr (k -1)) and 1) = 1 {дана умова означає, що в
k-й праворуч позиції числа j, в 2-й системі, коштує 1}
then s: = s + a [k];
if s = m then
begin
for k: = 1 to n do
if ((j shr (k-1)) and 1) = 1 then write (a [k]: 4);
writeln
end
end;
procedure subsets (n: integer);
var q, j: longint;
begin
q: = 1 shl n; {таким чином ми поміщаємо в q число 2 ^ n}
for j: = 1 to q -1 do {цикл по всіх підмножини}
if check (j) then exit
end;
Зауважимо, що якщо всі елементи в масиві позитивні, то, змінивши порядок розгляду підмножин, рішення наведеної вище завдання можна зробити більш ефективним. Так, якщо сума елементів будь-якого підмножини вже більше, ніж M, то розглядати підмножини, які включають їх у себе вже не має сенсу. Перерахунок ж сум можна оптимізувати, якщо кожне наступне сгенерированное підмножина буде відрізнятися від попереднього не більш, ніж на один елемент (такий спосіб перерахування підмножин показаний в [2]). Наведена ж програма надзвичайно проста, але володіє одним недоліком: ми не можемо ні в якому випадку з її допомогою перебирати всі підмножини множин, що складаються з більш, ніж 30 елементів, що обумовлено максимальним числом бітів, що відводяться на представлення цілих чисел в Турбо Паскалі (32 біта). Але, як вже було сказано вище, насправді, перебір всіх підмножин у множин більшої розмірності навряд чи можливий за час, відведений для вирішення того чи іншого завдання.
Розглянемо рекурсивний алгоритм, який реалізує генерацію всіх перестановок в лексикографічному порядку. Такий порядок часто наімболее зручний при вирішенні олімпіадних завдань, так як спрощує застосування методу гілок і меж, який буде описаний нижче. Позначимо масив індексів елементів - p. Спочатку він заповнений числами 1, 2, ..., n, які в подальшому будуть мінятися місцями. Параметром i рекурсивної процедури Perm служить місце в масиві p, починаючи з якого мають бути, отримані всі перестановки правій частині цього масиву. Ідея рекурсії, у даному випадку наступна: на i-му місці повинні побувати всі елементи масиву p з i-го по n-й і для кожного з цих елементів повинні бути отримані всі перестановки інших елементів, починаючи з (i +1)-го місця, в лексикографічному порядку. Після отримання останньої з перестановок, починаючи з (i +1)-го місця, вихідний порядок елементів повинен бути відновлений.
{Опис змінних збігається з наведеним вище}
procedure Permutations (n: integer);
procedure Perm (i: integer);
var j, k: integer;
begin
if i = n then
begin for j: = 1 to n do write (a [p [j]], ''); writeln end
else
begin
for j: = i +1 to n do
begin
Perm (i +1);
k: = p [i]; p [i]: = p [j]; p [j]: = k
end;
Perm (i +1);
{Циклічний зсув елементів i .. n вліво}
k: = p [i];
for j: = i to n-1 do p [j]: = p [j +1];
p [n]: = k
end
end; {Perm}
begin {Permutations}
Perm (1)
end;
begin {Main}
readln (n);
for i: = 1 to n do p [i]: = i;
a: = p; {масив a може бути заповнений довільно}
Permutations (n)
end.
Зауважимо, що в даній програмі масив p можна було й не використовувати, а переставляти безпосередньо елементи масиву a.
Для довільного k можна міркувати так. Останній елемент або буде представляти із себе окремий блок у разі необхідності розділення і тоді залишилися елементи можна розбити вже на k - 1 частин S (n - 1, k - 1) способами, або поміщаємо його в непорожній блок. В останньому випадку мається kS (n - 1, k) можливих варіантів, оскільки останній елемент ми можемо додавати в кожен блок розбиття перший n - 1 елементів на k частин. Таким чином
S (n, k) = S (n - 1, k - 1) + kS (n - 1, k), n> 0. (5)
Корисними можуть виявитися також формули, що зв'язують числа Стірлінга з біноміальними коефіцієнтами, що визначають кількість сполучень:
Якщо ж значення k тепер не фіксувати і розглянути всі розбиття n-елементної множини, то їх кількість виражається числом Белла
За формулами (7) можна підрахувати, що в рамках прийнятих вище припущень можна побудувати все розбиття множини, що складається не більше ніж з 15 елементів (B 15 = 1382958545).
Перейдемо тепер до розгляду способу генерації всіх розбиття вихідної множини. Перш за все, слід домовитися про те, як позначати поточний розбивка. Так як у кожному з розбиття беруть участь всі елементи вихідної безлічі, будемо в масиві індексів p записувати в який блок потрапляє кожен з елементів у поточному розбивці. Параметр i в рекурсивної процедури part означає, що на поточному кроці ми саме i-ий елемент буде розміщувати в кожному з допустимих для нього блоків, а j якраз і визначає максимальний номер допустимого блоку. Після того, як i-ий елемент поміщений в один з блоків, рекурсивно вирішується таке ж завдання вже для наступного елемента (в даному випадку фактично працює універсальна схема перебору з поверненням [8]).
procedure partition (n: integer; var p: list);
procedure part (i, j: integer);
var l: integer;
begin
if i> n then print (n, p) else
for l: = 1 to j do
begin
p [i]: = l;
if l = j then part (i +1, j +1)
else part (i +1, j)
end
end; {part}
begin {partition}
part (1,1)
end;
Як не дивно, в даному випадку процедура print виявляється зовсім не тривіальною, якщо потрібно друкувати (або аналізувати) елементи кожного з блоків розбиття окремо. Тому наведемо можливий варіант її реалізації (як і раніше, розподіляли по блоках ми індекси, а друкуємо або аналізуруем самі елементи вихідного масиву a):
Установа освіти
«Гомельський державний університет ім. Ф. Скорини »
Математичний факультет
Кафедра МПУ
Реферат
Комбінаторні задачі
Виконавець:
Студентка групи М-42 Макарченко А.Ю.
Науковий керівник: Долинський М.С.
Гомель 2005
Зміст
Введення
Генерація k-елементних підмножин
Генерація всіх підмножин даної множини
Генерація всіх перестановок n-елементної множини
Розбиття множини
Висновок
Література
Введення
Завдання дискретної математики, до яких належить більшість олімпіадних завдань з інформатики, часто зводяться до перебору різних комбінаторних конфігурацій об'єктів та вибору серед них найкращого, з точки зору умови тієї або іншої задачі. Тому знання алгоритмів генерації найбільш поширених комбінаторних конфігурацій є необхідною умовою успішного вирішення олімпіадних завдань в цілому. Важливо також знати кількість різних варіантів для кожного типу комбінаторних конфігурацій, так як це дозволяє реально оцінити обчислювальну трудомісткість вибраного алгоритму розв'язання того чи іншого завдання на перебір варіантів і, відповідно, його прийнятність для вирішення даної задачі, з урахуванням її розмірності. Крім того, при вирішенні завдань корисним виявляється вміння для кожної з комбінаторних конфігурацій виконувати наступні операції: за наявною конфігурації одержувати наступну за нею в лексикографічному порядку; визначати номер даної конфігурації в лексикографічній нумерації всіх конфігурацій, і, навпаки, за порядковим номером виписувати відповідну йому конфігурацію .
Генерація k-елементних підмножин
У комбінаториці такі підмножини називають сполученнями із n елементів по k елементів і позначають C n k. Їх кількість виражається наступною формулою:
Однак при програмуванні набагато зручніше використовувати наступні рекурентні співвідношення:
Пояснюється це тим, що у формулі (1) чисельник і знаменник ростуть дуже швидко, тому в силу особливостей комп'ютерної арифметики не завжди можливо точно обчислити значення C n k, навіть коли останнє не перевершує максимально представимое ціле число.
При фіксованому значенні n максимального значення число сполучень досягає при k = n / 2 (вірніше, для парного n максимум один і він зазначений, а для непарного - максимум досягається на двох сусідніх значеннях k: [n / 2] і
[N / 2] +1). Тому особливо корисною виявляється наступна оцінка для парних n [4] (очевидно, що при непарних n відмінності будуть мінімальними), заснована на формулі Стірлінга:
Якщо допустити, що за час, відведений для виконання завдання, ми можемо перебрати близько 10 6 варіантів, то з формули (3) випливає, що генерацію всіх сполучень з n елементів для будь-якого фіксованого k можна проводити для n £ 24.
Зазвичай генерацію всіх k-елементних підмножин проводять в лексикографічному порядку, тим паче що в даному випадку це не призводить ні до ускладнення алгоритму, ні до збільшення його обчислювальної трудомісткості. Нагадаємо, що порядок підмножин називається лексикографічним, якщо для будь-яких двох підмножин справедливо, що раннє повинно бути згенеровано то з них, з індексів елементів якого можна скласти менше k-значне число в n-річної системі числення (або в десятковій, для n <10 ). Так, для n = 6 і k = 3 поєднання з третього, першого і п'ятого елемента має бути створене раніше, ніж з другого, третього і четвертого, так як 135 <234.
Розглянемо рекурсивний алгоритм вирішення даної задачі. Ідея відомості даної задачі до задачі меншої розмірності наступна. Першим елементом підмножини може бути будь-який елемент, починаючи з першого і закінчуючи (n - k + 1)-м елементом. Після того, як індекс першого елемента підмножини зафіксовано, залишилося вибрати k - 1 елемент з елементів з індексами, більшими, ніж у першого. Далі поступаємо аналогічно. Коли обраний останній елемент, то ми досягли кінцевого рівня рекурсії і вибране підмножина можна обробити (проаналізувати або роздрукувати). У пропонованій нижче програмі масив a містить значення елементів вихідної множини і може бути заповнений довільним чином. У масиві p будемо формувати чергове поєднання з k елементів.
const nmax = 24;
type list = array [1 .. nmax] of integer; var k, i, j, n, q: integer; a, p: list; procedure print (k: 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, з урахуванням порожнього множини). Таким чином, зіставляючи два способи перебору всіх підмножин даної множини, ми отримали наступну формулу:
Тобто, в рамках зробленої вище оцінки на кількість допустимих варіантів у переборі, ми можемо розглянути всі підмножини вихідного безлічі тільки при n £ 20.
Перш, ніж перейти до розгляду програм, відповідних другим способом перебору, зазначимо, коли застосування цих програм доцільно. По-перше, дані програми легко використовувати, коли необхідно в будь-якому випадку перебрати всі підмножини даної множини (наприклад, потрібно знайти всі рішення задовольняють того чи іншого положення). По-друге, коли з точки зору умови задачі не має значення, скільки саме елементів повинно входити в шукане підмножина. На прикладі такого завдання ми і напишемо програму генерації всіх підмножин вихідного безлічі в лексикографічному порядку. Завдання взята з книги [5].
Умова. Дан цілочисельний масив a [1 .. N] (N £ 20) і число M. Знайти підмножина елементів масиву a [i1], a [i2], ... a [ik] таке, що 1 £ i1 <i2 <i3 <... <Ik £ N і a [i1] + a [i2] + ... + A [ik] = M.
Рішення. В якості вирішення наведемо процедуру генерації всіх підмножин, які можна скласти з елементів масиву і функцію перевірки конкретного підмножини на відповідність умові завдання.
function check (j: longint): boolean;
var k: integer; s: longint;
begin
s: = 0;
for k: = 1 to n do
if ((j shr (k -1)) and 1) = 1 {дана умова означає, що в
k-й праворуч позиції числа j, в 2-й системі, коштує 1}
then s: = s + a [k];
if s = m then
begin
for k: = 1 to n do
if ((j shr (k-1)) and 1) = 1 then write (a [k]: 4);
writeln
end
end;
procedure subsets (n: integer);
var q, j: longint;
begin
q: = 1 shl n; {таким чином ми поміщаємо в q число 2 ^ n}
for j: = 1 to q -1 do {цикл по всіх підмножини}
if check (j) then exit
end;
Зауважимо, що якщо всі елементи в масиві позитивні, то, змінивши порядок розгляду підмножин, рішення наведеної вище завдання можна зробити більш ефективним. Так, якщо сума елементів будь-якого підмножини вже більше, ніж M, то розглядати підмножини, які включають їх у себе вже не має сенсу. Перерахунок ж сум можна оптимізувати, якщо кожне наступне сгенерированное підмножина буде відрізнятися від попереднього не більш, ніж на один елемент (такий спосіб перерахування підмножин показаний в [2]). Наведена ж програма надзвичайно проста, але володіє одним недоліком: ми не можемо ні в якому випадку з її допомогою перебирати всі підмножини множин, що складаються з більш, ніж 30 елементів, що обумовлено максимальним числом бітів, що відводяться на представлення цілих чисел в Турбо Паскалі (32 біта). Але, як вже було сказано вище, насправді, перебір всіх підмножин у множин більшої розмірності навряд чи можливий за час, відведений для вирішення того чи іншого завдання.
Генерація всіх перестановок n-елементної множини
Кількість різних перестановок множини, що складається з n елементів, дорівнює n!. У цьому неважко переконатися: на першому місці в перестановці може стояти будь-який з n елементів множини, після того, як ми на першому місці зафіксували який-небудь елемент, на другому місці може стояти будь-який з n - 1 залишився елемента і т.д. Таким чином, загальна кількість варіантів одно n (n - 1) (n - 2) ... 3 × 2 × 1 = n!. Тобто розглядати абсолютно всі перестановки ми можемо тільки у множест, що складаються з не більш, ніж 10 елементів.Розглянемо рекурсивний алгоритм, який реалізує генерацію всіх перестановок в лексикографічному порядку. Такий порядок часто наімболее зручний при вирішенні олімпіадних завдань, так як спрощує застосування методу гілок і меж, який буде описаний нижче. Позначимо масив індексів елементів - p. Спочатку він заповнений числами 1, 2, ..., n, які в подальшому будуть мінятися місцями. Параметром i рекурсивної процедури Perm служить місце в масиві p, починаючи з якого мають бути, отримані всі перестановки правій частині цього масиву. Ідея рекурсії, у даному випадку наступна: на i-му місці повинні побувати всі елементи масиву p з i-го по n-й і для кожного з цих елементів повинні бути отримані всі перестановки інших елементів, починаючи з (i +1)-го місця, в лексикографічному порядку. Після отримання останньої з перестановок, починаючи з (i +1)-го місця, вихідний порядок елементів повинен бути відновлений.
{Опис змінних збігається з наведеним вище}
procedure Permutations (n: integer);
procedure Perm (i: integer);
var j, k: integer;
begin
if i = n then
begin for j: = 1 to n do write (a [p [j]], ''); writeln end
else
begin
for j: = i +1 to n do
begin
Perm (i +1);
k: = p [i]; p [i]: = p [j]; p [j]: = k
end;
Perm (i +1);
{Циклічний зсув елементів i .. n вліво}
k: = p [i];
for j: = i to n-1 do p [j]: = p [j +1];
p [n]: = k
end
end; {Perm}
begin {Permutations}
Perm (1)
end;
begin {Main}
readln (n);
for i: = 1 to n do p [i]: = i;
a: = p; {масив a може бути заповнений довільно}
Permutations (n)
end.
Зауважимо, що в даній програмі масив p можна було й не використовувати, а переставляти безпосередньо елементи масиву a.
Розбиття множини
Число розбиттів n-елементної множини на k блоків довільного розміру, але таких, що кожен елемент множини виявляється "приписаний" до одного з блоків, виражається числом Стірлінга другого роду S (n, k) [6,7]. Очевидно, що S (n, k) = 0 для k > N. Якщо погодитися, що існує тільки один спосіб розбиття порожньої множини на нульове число непустих частин, то S (0,0) = 1 (саме така домовленість, як і у випадку з факторіалом, приводить надалі до універсальних формулами). Тому що при розбитті непорожньої безлічі потрібна, принаймні, одна частина, S (n, 0) = 0 при n > 0. Окремо цікаво також розглянути випадок k = 2. Якщо непорожнє безліч розділили на дві непорожні частини, то в першій частині може виявитися будь-яка підмножина вихідної безлічі, за винятком підмножин, що включають в себе останній елемент множини, а що залишилися елементи автоматично потрапляють у другу частину. Такі підмножини можна вибрати 2 n -1 - 1 способами, що і відповідає S (n, 2) при n> 0.Для довільного k можна міркувати так. Останній елемент або буде представляти із себе окремий блок у разі необхідності розділення і тоді залишилися елементи можна розбити вже на k - 1 частин S (n - 1, k - 1) способами, або поміщаємо його в непорожній блок. В останньому випадку мається kS (n - 1, k) можливих варіантів, оскільки останній елемент ми можемо додавати в кожен блок розбиття перший n - 1 елементів на k частин. Таким чином
S (n, k) = S (n - 1, k - 1) + kS (n - 1, k), n> 0. (5)
Корисними можуть виявитися також формули, що зв'язують числа Стірлінга з біноміальними коефіцієнтами, що визначають кількість сполучень:
Якщо ж значення k тепер не фіксувати і розглянути всі розбиття n-елементної множини, то їх кількість виражається числом Белла
За формулами (7) можна підрахувати, що в рамках прийнятих вище припущень можна побудувати все розбиття множини, що складається не більше ніж з 15 елементів (B 15 = 1382958545).
Перейдемо тепер до розгляду способу генерації всіх розбиття вихідної множини. Перш за все, слід домовитися про те, як позначати поточний розбивка. Так як у кожному з розбиття беруть участь всі елементи вихідної безлічі, будемо в масиві індексів p записувати в який блок потрапляє кожен з елементів у поточному розбивці. Параметр i в рекурсивної процедури part означає, що на поточному кроці ми саме i-ий елемент буде розміщувати в кожному з допустимих для нього блоків, а j якраз і визначає максимальний номер допустимого блоку. Після того, як i-ий елемент поміщений в один з блоків, рекурсивно вирішується таке ж завдання вже для наступного елемента (в даному випадку фактично працює універсальна схема перебору з поверненням [8]).
procedure partition (n: integer; var p: list);
procedure part (i, j: integer);
var l: integer;
begin
if i> n then print (n, p) else
for l: = 1 to j do
begin
p [i]: = l;
if l = j then part (i +1, j +1)
else part (i +1, j)
end
end; {part}
begin {partition}
part (1,1)
end;
Як не дивно, в даному випадку процедура print виявляється зовсім не тривіальною, якщо потрібно друкувати (або аналізувати) елементи кожного з блоків розбиття окремо. Тому наведемо можливий варіант її реалізації (як і раніше, розподіляли по блоках ми індекси, а друкуємо або аналізуруем самі елементи вихідного масиву a):
procedure print (n: integer; var p: list);
var i, j, imax: integer;
begin
imax: = 1; {визначаємо кількість блоків у розбитті}
for i: = 2 to n do
if p [i]> imax then imax: = p [i];
for i: = 1 to imax do {цикл по блокам}
begin
for j: = 1 to n do
if p [j] = i then write (a [j]: 4);
write ('|') {блок надрукований}
end;
writeln {розбиття надруковано}
end;
Вкладеного циклу можна уникнути, якщо потрібно, наприклад, підрахувати суму елементів у кожному з блоків. Тоді, використовуючи додатковий масив, ми, переглядаючи елементи масиву a послідовно, будемо збільшувати значення суми для блоку, відповідного розглядався елементу (аналогічно операції, що здійснюється в алгоритмі сортування підрахунком).
Якщо при цьому розглядати масив p як n-значне число n-річної системі числення, то можна ввести поняття лексикографічного порядку для розбиття множини і ставити завдання визначення номера розбиття і зворотну їй. Як і раніше (див. [1-3]), вони вирішуються методом динамічного програмування і не використовують безпосередню генерацію всіх розбиття.
Для повноти розгляду даної теми самостійно змініть процедуру partition так, щоб вона генерувала всі розбиття, які складаються не більш ніж з k блоків. Після цього напишіть процедуру розбиття множини вже на рівно k непустих частин.
Вихідні дані: кожна партія і, відповідно, її президент мають однаковий порядковий номер від 1 до N (4 £ N £ 150). Вам дані списки всіх N партій Острови Нової Демократії. Виведіть пропонований Вами парламент у вигляді списку номерів його членів. (Олімпіада країн СНД, м. Могильов, 1992 р.)
Рішення: з теоретичної точки зору, це завдання збігається із завданням генерації всіх підмножин з безлічі жителів острова нової демократії. Причому найбільш підходящим здається перший підхід до вирішення даного завдання, пов'язаний з генерацій різних сполучень, починаючи з одного мешканця. Для повноти викладу цього підходу, опишемо функцію сheck, яку слід застосувати в даному завданні. Вихідні дані слід записати в масив s: array [1 .. 150] of set of 1 .. 150, заповнивши кожен з n перших елементів цього масиву безліччю тих партій, до яких належить той або інший житель. Тоді функція перевірки поєднання з елементів цього масиву прийме наступний вигляд:
function check (var p: list; k: integer): boolean;
var i: integer; ss: set of 1 .. 150;
begin
ss :=[];
for i: = 1 to k do ss: = ss + s [p [i]];
check: = (ss = [1 .. n])
end;
Як видно з опису функції, використання типу "безліч", дозволяє не тільки спростити цю програму, але й істотно прискорити її виконання, в порівнянні з роботою з масивами. Однак велика розмірність даного завдання не дозволяє вважати наведене рішення задовільним у всіх випадках. Так, вже для n = 100, перебір всіх сполучень з 4-х і менше жителів призводить до розгляду близько 4-х мільйонів варіантів. Для побудови коду, придатного для вирішення даного завдання за будь-яких вхідних даних, дещо змінимо опис масиву s:
s: array [1 .. 150] of
record name, number: integer;
partys: set of 1 .. 150
end;
Тут поле partys збігається за змістом з первісним описом масиву s, поле name Відповідне номером (тобто фактично імені) жителя і спочатку дане поле слід заповнити числами від 1 до n згідно зі індексом елемента в масиві записів, і поле number відповідає кількості елементів у безлічі з поля partys, тобто має сенс відразу підрахувати, в якій кількості партій полягає той або інший житель. Тепер слід відсортувати масив s за спаданням значень поля number. Верхню оцінку для числа членів парламенту (kmax) підрахуємо, побудувавши наближене рішення даного завдання наступним чином: по-перше, включимо до парламенту жителя, який складається в максимальній кількості партій, потім виключимо ці партії з інших множин і заново знайдемо в останньому масиві елемент з максимальним значенням поля number (вже переліченого) і включимо його до парламенту, і так далі, до тих пір, поки сума значень перелічених полів number у жителів, включених до парламенту, не буде дорівнює n. Знайдене кількість членів парламенту і буде kmax.
Тепер слід розглядати поєднання з (kmax - 1) елемента, потім з (kmax - 2) і т. д. елементів. Якщо для сполучень з якогось розглянутого кількості елементів k, рішення знайдено не буде, то це означає, що точним є рішення з кількістю членів парламенту k +1. Так як масив s впорядкований, то, якщо рішення для того чи іншого значення k існує, то, швидше за все, воно буде знайдено при розгляді в лексикографічному порядку перших же сполучень за k елементів. Тому тимчасова трудомісткість в переборі виникає, тільки якщо рішення c даними значенням k не існує. У такій ситуації можна скористатися наступним "ненауковим" прийомом: на пошук рішення для кожного k, меншого, ніж kmax відведемо фіксовану кількість часу, скажімо, 2-3 секунди (точніше даний час варто визначити експериментальним шляхом). Якщо за відведений час рішення не знайдено, то слід вважати повний перебір неможливим і закінчити виконання програми. У будь-якому випадку, ми будемо мати будь-яке рішення вихідної задачі: точне або наближене, тобто, можливо, яке має більше членів парламенту, ніж мінімально можливо. Однак, на практиці такий підхід майже завжди призводить до точного розв'язання, в силу перебору "з перевагою", проведеного для кожного k (неможливість проведення повного перебору для будь-якого k на практиці відповідає відсутності рішення для даного k).
Приклад 2. Дан автобусний квиток з номером, що складається з N цифр. Розставити між цифрами знаки арифметичних операцій '+', '-', '*', '/' (цілочисельне розподіл) і дужки таким чином, щоб значення отриманого виразу було рівне 100. Можна утворювати багатозначні числа з стоять поруч цифр. Вираз повинен бути коректним з точки зору арифметики. Допустимі зайві дужки, що не порушують коректності висловлювання. При обчисленнях використовується стандартний пріоритет операцій, число цифр N в номері квитка не більше 6. (5-ая Всеросійська олімпіада з інформатики, м. Троїцьк, 1993 р.)
Рішення. для побудови універсального алгоритму розв'язання даної задачі будемо вважати злиття двох сусідніх цифр однієї з операцій. Тоді між кожною парою сусідніх цифр може стояти одна з 5 операцій. Для N цифр отримуємо 5 N -1 різних варіантів розстановки операцій. Перебирати всі варіанти розстановки операцій зручніше за все за допомогою розгляду всіх чисел у 5-річної системі числення, що складаються не більше ніж з N - 1 цифри, тобто для N = 6 від 00000 до 44444. Для перебору таких чисел необхідно написати процедуру додатки 1 у 5-річної системі числення. Для кожного з варіантів розстановки операцій перейдемо від вихідного масиву з N цифр квитка, до масиву з К чисел, де K = (N - кількість операцій злиття цифр у розглянутому варіанті). Тепер ми повинні розглянути всі перестановки з K - 1 арифметичної операції в даному варіанті. Кожна перестановка відповідає одному з порядків виконання арифметичних операцій. Так, для 4-х чисел, перестановка номерів операцій 3, 1, 2 означає, що спочатку потрібно виконати арифметичну дію між 3-м і 4-м числом, потім між 1-м і 2-м і потім решту. Якщо результат виконання дій даного варіанту в порядку, відповідному поточної перестановці, дорівнює шуканого числа 100, то завдання виконане і можна перейти до друку результату. Для даної задачі можливі й більш ефективні рішення, але через її невеликий розмірності, комбінаторний перебір виявляється цілком прийнятною.
Приклад 3. Губернатор однієї з областей уклав з фірмою "HerNet" контракт на підключення всіх міст області до комп'ютерної мережі. Мережа створюється наступним чином: в області встановлюється декілька станцій супутникового зв'язку, і потім від кожного міста прокладається кабель до однієї із станцій. Технологія, що використовується компанією вимагає при збільшенні відстані збільшення товщини кабеля. Таким чином, вартість кабелю, що з'єднує місто зі станцією, при використовуваної компанією технології буде дорівнює kL 2, де L - відстань від міста до станції, а k - деякий коефіцієнт. Вам потрібно написати програму, що визначає мінімальні витрати компанії на встановлення мережі.
Вхідні дані. У вхідному файлі записано число n (1 ≤ n ≤ 10) - кількість міст в області. Потім йдуть позитивні речові числа: k - коефіцієнт вартості кабелю і P - вартість будівлі однієї станції. Далі слід n пара дійсних чисел, що задають координати міст на площині.
Вихідні дані. У перший рядок вихідного файлу потрібно вивести мінімальні витрати на установку мережі (з трьома знаками після десяткової точки), в другу - кількість встановлюваних станцій. Далі вивести координати станцій (з трьома знаками після десяткового дробу), а потім - список з n цілих чисел, в якому i-е число задає номер станції, до якої буде підключений i-ий місто. (Кіровський командний турнір з програмування, 2000 р.)
Рішення. У силу невеликої розмірності ми можемо розглянути всі можливі варіанти розбиття міст на групи, маючи на увазі що для кожної групи буде встановлена своя станція, причому оптимальним чином (знайти оптимальне місцезнаходження станції для однієї групи міст можна за формулою, аналогічною формулою знаходження центру мас). Потім потрібно з усіх розбиття вибрати те, для якого загальна сума витрат на установку мережі буде мінімальною.
Більшість зазначених конфігурацій були детально розглянуті в [1-3]. Однак при генерації різних конфігурацій використовувалися в основному нерекурсівние алгоритми. Досвідчені ж учасники олімпіад у подібних випадках при програмуванні використовують в основному саме рекурсію, за допомогою якої рішення розглянутих завдань часто можна записати більш коротко і прозоро. Тому для повноти викладу даної теми наведемо низку рекурсивних комбінаторних алгоритмів і розглянемо особливості застосування рекурсії в комбінаториці.
Література
1. Окулов С. М. Перестановки. "Інформатика", № 7, 2000.
2. Окулов С. M. Комбінаторні задачі. "Інформатика", № 10, 13, 2000.
3. Усов Б. Б. Комбінаторні задачі. "Інформатика", № 39, 2000.
4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритми. Побудова та аналіз. М. МЦНМО, 2000.
5. Брудно A. Л., Каплан Л. І. Московські олімпіади з програмування. М.: Наука, 1990.
6. Кнут Д. Конкретна математика. Підстава інформатики. М.: "Мир", 1998.
7. Липський В. Комбінаторика для програмістів. М.: "Мир", 1988.
8. Андреєва О. В. Ще раз про завдання на повний перебір варіантів. "Інформатика", № 45, 2000.
var i, j, imax: integer;
begin
imax: = 1; {визначаємо кількість блоків у розбитті}
for i: = 2 to n do
if p [i]> imax then imax: = p [i];
for i: = 1 to imax do {цикл по блокам}
begin
for j: = 1 to n do
if p [j] = i then write (a [j]: 4);
write ('|') {блок надрукований}
end;
writeln {розбиття надруковано}
end;
Вкладеного циклу можна уникнути, якщо потрібно, наприклад, підрахувати суму елементів у кожному з блоків. Тоді, використовуючи додатковий масив, ми, переглядаючи елементи масиву a послідовно, будемо збільшувати значення суми для блоку, відповідного розглядався елементу (аналогічно операції, що здійснюється в алгоритмі сортування підрахунком).
Якщо при цьому розглядати масив p як n-значне число n-річної системі числення, то можна ввести поняття лексикографічного порядку для розбиття множини і ставити завдання визначення номера розбиття і зворотну їй. Як і раніше (див. [1-3]), вони вирішуються методом динамічного програмування і не використовують безпосередню генерацію всіх розбиття.
Для повноти розгляду даної теми самостійно змініть процедуру partition так, щоб вона генерувала всі розбиття, які складаються не більш ніж з k блоків. Після цього напишіть процедуру розбиття множини вже на рівно k непустих частин.
Олімпіадні завдання, використовують комбінаторні конфігурації
Приклад 1. На одному острові Нової Демократії кожен з його жителів організував партію, яку сам і очолив. Відзначимо, що до загального здивування навіть у найменш численною партії виявилося не менше двох осіб. На жаль, фінансові труднощі не дозволили створити парламент, куди увійшли б, як Предпологалось за Конституцією острова, президенти всіх партій. Порадившись, Остров'яни вирішили, що буде достатньо, якщо в парламенті буде хоча б один член кожної партії. Допоможіть остров'янам організувати такий, як можна більш малочисельний парламент, в якому будуть представлені члени всіх партій.Вихідні дані: кожна партія і, відповідно, її президент мають однаковий порядковий номер від 1 до N (4 £ N £ 150). Вам дані списки всіх N партій Острови Нової Демократії. Виведіть пропонований Вами парламент у вигляді списку номерів його членів. (Олімпіада країн СНД, м. Могильов, 1992 р.)
Рішення: з теоретичної точки зору, це завдання збігається із завданням генерації всіх підмножин з безлічі жителів острова нової демократії. Причому найбільш підходящим здається перший підхід до вирішення даного завдання, пов'язаний з генерацій різних сполучень, починаючи з одного мешканця. Для повноти викладу цього підходу, опишемо функцію сheck, яку слід застосувати в даному завданні. Вихідні дані слід записати в масив s: array [1 .. 150] of set of 1 .. 150, заповнивши кожен з n перших елементів цього масиву безліччю тих партій, до яких належить той або інший житель. Тоді функція перевірки поєднання з елементів цього масиву прийме наступний вигляд:
function check (var p: list; k: integer): boolean;
var i: integer; ss: set of 1 .. 150;
begin
ss :=[];
for i: = 1 to k do ss: = ss + s [p [i]];
check: = (ss = [1 .. n])
end;
Як видно з опису функції, використання типу "безліч", дозволяє не тільки спростити цю програму, але й істотно прискорити її виконання, в порівнянні з роботою з масивами. Однак велика розмірність даного завдання не дозволяє вважати наведене рішення задовільним у всіх випадках. Так, вже для n = 100, перебір всіх сполучень з 4-х і менше жителів призводить до розгляду близько 4-х мільйонів варіантів. Для побудови коду, придатного для вирішення даного завдання за будь-яких вхідних даних, дещо змінимо опис масиву s:
s: array [1 .. 150] of
record name, number: integer;
partys: set of 1 .. 150
end;
Тут поле partys збігається за змістом з первісним описом масиву s, поле name Відповідне номером (тобто фактично імені) жителя і спочатку дане поле слід заповнити числами від 1 до n згідно зі індексом елемента в масиві записів, і поле number відповідає кількості елементів у безлічі з поля partys, тобто має сенс відразу підрахувати, в якій кількості партій полягає той або інший житель. Тепер слід відсортувати масив s за спаданням значень поля number. Верхню оцінку для числа членів парламенту (kmax) підрахуємо, побудувавши наближене рішення даного завдання наступним чином: по-перше, включимо до парламенту жителя, який складається в максимальній кількості партій, потім виключимо ці партії з інших множин і заново знайдемо в останньому масиві елемент з максимальним значенням поля number (вже переліченого) і включимо його до парламенту, і так далі, до тих пір, поки сума значень перелічених полів number у жителів, включених до парламенту, не буде дорівнює n. Знайдене кількість членів парламенту і буде kmax.
Тепер слід розглядати поєднання з (kmax - 1) елемента, потім з (kmax - 2) і т. д. елементів. Якщо для сполучень з якогось розглянутого кількості елементів k, рішення знайдено не буде, то це означає, що точним є рішення з кількістю членів парламенту k +1. Так як масив s впорядкований, то, якщо рішення для того чи іншого значення k існує, то, швидше за все, воно буде знайдено при розгляді в лексикографічному порядку перших же сполучень за k елементів. Тому тимчасова трудомісткість в переборі виникає, тільки якщо рішення c даними значенням k не існує. У такій ситуації можна скористатися наступним "ненауковим" прийомом: на пошук рішення для кожного k, меншого, ніж kmax відведемо фіксовану кількість часу, скажімо, 2-3 секунди (точніше даний час варто визначити експериментальним шляхом). Якщо за відведений час рішення не знайдено, то слід вважати повний перебір неможливим і закінчити виконання програми. У будь-якому випадку, ми будемо мати будь-яке рішення вихідної задачі: точне або наближене, тобто, можливо, яке має більше членів парламенту, ніж мінімально можливо. Однак, на практиці такий підхід майже завжди призводить до точного розв'язання, в силу перебору "з перевагою", проведеного для кожного k (неможливість проведення повного перебору для будь-якого k на практиці відповідає відсутності рішення для даного k).
Приклад 2. Дан автобусний квиток з номером, що складається з N цифр. Розставити між цифрами знаки арифметичних операцій '+', '-', '*', '/' (цілочисельне розподіл) і дужки таким чином, щоб значення отриманого виразу було рівне 100. Можна утворювати багатозначні числа з стоять поруч цифр. Вираз повинен бути коректним з точки зору арифметики. Допустимі зайві дужки, що не порушують коректності висловлювання. При обчисленнях використовується стандартний пріоритет операцій, число цифр N в номері квитка не більше 6. (5-ая Всеросійська олімпіада з інформатики, м. Троїцьк, 1993 р.)
Рішення. для побудови універсального алгоритму розв'язання даної задачі будемо вважати злиття двох сусідніх цифр однієї з операцій. Тоді між кожною парою сусідніх цифр може стояти одна з 5 операцій. Для N цифр отримуємо 5 N -1 різних варіантів розстановки операцій. Перебирати всі варіанти розстановки операцій зручніше за все за допомогою розгляду всіх чисел у 5-річної системі числення, що складаються не більше ніж з N - 1 цифри, тобто для N = 6 від 00000 до 44444. Для перебору таких чисел необхідно написати процедуру додатки 1 у 5-річної системі числення. Для кожного з варіантів розстановки операцій перейдемо від вихідного масиву з N цифр квитка, до масиву з К чисел, де K = (N - кількість операцій злиття цифр у розглянутому варіанті). Тепер ми повинні розглянути всі перестановки з K - 1 арифметичної операції в даному варіанті. Кожна перестановка відповідає одному з порядків виконання арифметичних операцій. Так, для 4-х чисел, перестановка номерів операцій 3, 1, 2 означає, що спочатку потрібно виконати арифметичну дію між 3-м і 4-м числом, потім між 1-м і 2-м і потім решту. Якщо результат виконання дій даного варіанту в порядку, відповідному поточної перестановці, дорівнює шуканого числа 100, то завдання виконане і можна перейти до друку результату. Для даної задачі можливі й більш ефективні рішення, але через її невеликий розмірності, комбінаторний перебір виявляється цілком прийнятною.
Приклад 3. Губернатор однієї з областей уклав з фірмою "HerNet" контракт на підключення всіх міст області до комп'ютерної мережі. Мережа створюється наступним чином: в області встановлюється декілька станцій супутникового зв'язку, і потім від кожного міста прокладається кабель до однієї із станцій. Технологія, що використовується компанією вимагає при збільшенні відстані збільшення товщини кабеля. Таким чином, вартість кабелю, що з'єднує місто зі станцією, при використовуваної компанією технології буде дорівнює kL 2, де L - відстань від міста до станції, а k - деякий коефіцієнт. Вам потрібно написати програму, що визначає мінімальні витрати компанії на встановлення мережі.
Вхідні дані. У вхідному файлі записано число n (1 ≤ n ≤ 10) - кількість міст в області. Потім йдуть позитивні речові числа: k - коефіцієнт вартості кабелю і P - вартість будівлі однієї станції. Далі слід n пара дійсних чисел, що задають координати міст на площині.
Вихідні дані. У перший рядок вихідного файлу потрібно вивести мінімальні витрати на установку мережі (з трьома знаками після десяткової точки), в другу - кількість встановлюваних станцій. Далі вивести координати станцій (з трьома знаками після десяткового дробу), а потім - список з n цілих чисел, в якому i-е число задає номер станції, до якої буде підключений i-ий місто. (Кіровський командний турнір з програмування, 2000 р.)
Рішення. У силу невеликої розмірності ми можемо розглянути всі можливі варіанти розбиття міст на групи, маючи на увазі що для кожної групи буде встановлена своя станція, причому оптимальним чином (знайти оптимальне місцезнаходження станції для однієї групи міст можна за формулою, аналогічною формулою знаходження центру мас). Потім потрібно з усіх розбиття вибрати те, для якого загальна сума витрат на установку мережі буде мінімальною.
Висновок
Перераховані підзадачі в програмуванні зазвичай розглядають для наступних комбінаторних конфігурацій: перестановки елементів множини, підмножини множини, поєднання з n елементів множини за k елементів (k-елементні підмножини множини, що складається з n ³ k елементів), розміщення (впорядковані підмножини множини, тобто відрізняються не тільки складом елементів, але і порядком елементів в них), розбиття множини (безліч розбивається на підмножини довільного розміру так, що кожен елемент вихідної безлічі міститься рівно в одному підмножині), розбиття натуральних чисел на складові, правильні дужкові послідовності (різні правильні взаємні розташування n пар відкриваються і закриваються дужок).Більшість зазначених конфігурацій були детально розглянуті в [1-3]. Однак при генерації різних конфігурацій використовувалися в основному нерекурсівние алгоритми. Досвідчені ж учасники олімпіад у подібних випадках при програмуванні використовують в основному саме рекурсію, за допомогою якої рішення розглянутих завдань часто можна записати більш коротко і прозоро. Тому для повноти викладу даної теми наведемо низку рекурсивних комбінаторних алгоритмів і розглянемо особливості застосування рекурсії в комбінаториці.
Література
1. Окулов С. М. Перестановки. "Інформатика", № 7, 2000.
2. Окулов С. M. Комбінаторні задачі. "Інформатика", № 10, 13, 2000.
3. Усов Б. Б. Комбінаторні задачі. "Інформатика", № 39, 2000.
4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритми. Побудова та аналіз. М. МЦНМО, 2000.
5. Брудно A. Л., Каплан Л. І. Московські олімпіади з програмування. М.: Наука, 1990.
6. Кнут Д. Конкретна математика. Підстава інформатики. М.: "Мир", 1998.
7. Липський В. Комбінаторика для програмістів. М.: "Мир", 1988.
8. Андреєва О. В. Ще раз про завдання на повний перебір варіантів. "Інформатика", № 45, 2000.