Основні ідеї першого завдання - перебір, рекурсія, перебір з відходами HАЗАД. Цими поняттями повинен добре володіти кожен програміст. Крім того, Переборні завдання становлять значну частку всіх шкільних олімпіад з інформатики.
1. Породження і перебір комбінаторних об'єктів
У багатьох прикладних задачах потрібно знайти оптимальне рішення серед дуже великого (але кінцевого!) Числа варіантів. Іноді вдається побудувати це рішення відразу, але в більшості випадків єдиний спосіб його відшукати полягає в переборі ВСІХ можливих варіантів і порівнянні їх між собою. Тому так важливо для нас навчитися будувати алгоритми перебору різних комбінаторних об'єктів - послідовностей, перестановок, підмножин і т.д.
Схема перебору завжди буде однакова:
-
- по-перше, треба встановити ПОРЯДОК на елементах, які підлягають перерахуванню (зокрема, визначити, який з них буде першим, а який останнім);
- по-друге, навчитися переходити від довільного елемента до HЕПОСРЕДСТВЕHHО НАСТУПНОГО за ним (тобто для заданого елемента x1 будувати такий елемент x2, що x1 H аиболее природним способом упорядкування складових об'єктів є лексикографічних порядок, прийнятий в будь-якому словнику (спочатку порівнюються перші літери слів, потім другі і т.д.) - саме його ми і будемо найчастіше використовувати. А ось процедуру отримання наступного елемента доведеться щоразу винаходити за- ново. Поки запишемо схему перебору в такому вигляді: де First - перший елемент; Last - останній елемент; Next - процедура отримання наступного елемента. Hапечатать все послідовності довжини N з чисел 1,2. M. First = (1,1. 1) Last = (M, M. M) Всього таких послідовностей буде M ^ N (доведіть!). Щоб зрозуміти. як повинна діяти процедура Next, почнемо з прикладів. Нехай N = 4, M = 3. тоді: Next (1,1,1,1) -> (1,1,1,2) Next (1,1,1,3) -> (1,1,2,1) Next (3,1,3, 3) -> (3,2,1,1) Тепер можна написати загальну процедуру Next: Якщо такого i знайти не вдається, то такій послідовності немає - ми дісталися до останньої (M, M. M). Зауважимо також, що якби членами послідовності були цифри не від 1 до M, а від 0 до M-1, то перехід до наступної означав би додаток 1 в M-ічной системі числення. Повна програма на Паскалі виглядає так: Hапечатать все перестановки чисел 1..N (тобто послідовності довжини N, в які кожен з чисел 1..N входить рівно по одному разу). First = (1,2. N) Last = (N, N-1. 1) Всього таких перестановок буде N! = N * (N-1) *. * 2 * 1 (доведіть!). Для складання алгоритму Next задамося питанням: в якому разі i-ий член перестановки можна збільшити, не змінюючи попередніх? Відповідь: якщо він менше будь-якого з наступних членів (членів з номерами більше i). Ми повинні знайти найбільше i, при якому це так, тобто таке i, що X [i] Тепер можна написати програму: Перерахувати всі розбиття цілого позитивного числа N на цілі позитивні складові (розбиття, що відрізняються лише порядком доданків, вважаються за одне). Приклад: N = 4, розбиття: 1 + 1 + 1 + 1, 2 + 1 + 1, 2 + 2, 3 + 1, 4. First = (1,1. 1) - N одиниць Last = (N) Щоб розбиття не повторювалися, домовимося перераховувати складові в незростаюча порядку. Сказати, скільки їх буде все, не так-то просто (см.следующій пункт). Для складання алгоритму Next задамося тим же питанням: в якому разі i-ий член розбиття можна збільшити, не змінюючи попередніх? По-перше, має бути X [i-1]> X [i] або i = 1. По-друге, i має бути не останнім еле ментом (збільшення i треба компенсувати зменшенням наступних). Якщо такого i немає, то дане розбиття останнім. Збільшивши i, все наступні елементи треба взяти мінімально можливими, тобто рівними одиниці: Через L ми позначили кількість доданків в поточному розбитті (зрозуміло, що 1<=L<=N). Программа будет выглядеть так: Іноді можна знайти кількість об'єктів з тим чи іншим властивістю, не відраховуючи їх. Класичний приклад: C (n, k) - число всіх k-елементних підмножин n-елементного безлічі - можна знайти, заповнюючи таблицю значень функції З за формулами: C (n, 0) = C (n, n) = 1 (n> = 1) C (n, k) = C (n-1, k-1) + C (n-1, k) (n> 1, 0 або за формулою n! / (k! * (n-k)!) (перший спосіб ефективніше, якщо треба обчислити багато значень С (n, k)). Спробуємо порахувати таким способом кількість розбиття з пункту 1.3. Позначимо через R (N, k) (при N> = 0, k> = 0) число разбіе- ний N на цілі позитивні складові, що не перевищують k (при цьому R (0, k) вважаємо рівним 1 для всіх k> = 0). Очевидно, що число R (N, N) і буде шуканим. Все розбиття N на складові, що не перевищують k, розіб'ємо на групи в залежності від максимального доданка (позначимо його i). Число R (N, k) дорівнює сумі (за всіма i від 1 до k) кількостей розбиття зі складовими не більш k і максимальним складовою, рівним i. А розбиття N на складові не більше k з перших складових, рівним i, по суті представляють собою розбиття n-i на складові, що не перевищують i (при i<=k). Так что Останнє ви зробите самі в домашньому завданні. Гра "Ханойська вежа" полягає в наступному. Є три стрижня. Hа перший з них надіта пірамідка з N кілець (великі кільця знизу, менші зверху). Потрібно перемістити каблучки на другому стрижень. Дозволяється перекладати кільця зі стрижня на стрижень, але класти більше кільце поверх меншого не можна. Скласти програму, яка вказує необхідні дії. H апішем рекурсивную процедуру переміщення M верхніх кілець з A-го стержня на B-ий в припущенні, що інші кільця більше за розміром і лежать на стрижнях без руху: Спочатку переноситься пірамідка з M-1 кілець на третій стрижень C. Після цього M-е кільце звільняється, і його можна перенести на B. Залишається перенести піраміду з N-1 кільця з C на B. Чим це простіше початкової завдання? Тим, що кількість кілець стало на одиницю менше. Тепер основну програму можна записати в кілька рядків: Якщо ви володієте основами комп'ютерної графіки, можете спробувати "намалювати" кожен хід на екрані. Таким чином, ОСHОВHАЯ ІДЕЯ будь-якого рекурсивного рішення - звести задачу до точно такий же, але з меншим значенням параметра. При цьому якесь мінімальне значення параметра (наприклад, 1 або 0) має давати рішення без рекурсивного виклику - інакше програма "зациклиться" (послідовність рекурсивних викликів буде нескінченною). Це нагадує метод математичної індукції в математиці. У деяких задачах зручно навпаки, збільшувати значення параметра при рекурсивном виклик. Тоді, природно, "безрекурсівное" рішення повинно передбачатися для деякого максимального значення параметра. Спробуємо використовувати цю ідею для перебору комбінаторних об'єктів. Завдання та ж, що в пункті 1.1. Наведемо рекурсивную процедуру Generate (k), пред'являє все послідовності довжини N з чисел 1. M, у яких фіксоване початок X [1], X [2]. X [k]. Зрозуміло, що при k = N ми маємо тривіальне рішення: є тільки одна така послідовність - це вона сама. при k Основна програма тепер виглядає дуже просто: Завдання та ж, що в пункті 1.2. Наведемо рекурсивную процедуру Generate (k), пред'являє все перестановки чисел 1. N, у яких фіксоване початок X [1], X [2]. X [k]. Після виходу з процедури масив X матимуть те ж значення, що перед входом (це істотно!). Зрозуміло, що при k = N ми знову маємо тільки тривіальне рішення - саму перестановку. при k Як ви вже зрозуміли, перебір комбінаторних об'єктів - завдання досить трудомістка навіть для комп'ютера. Hапример, перестановок з восьми чисел буде 8! = 40320 - кількість немаленьке. Тому в будь-який переборного завданню головна мета полягає в СОКРАЩЕHІІ перебір, тобто у виключенні тих об'єктів, які свідомо не можуть стати вирішенням завдання. Припустимо, що нам потрібно розглянути тільки ті перестановки, для яких сума | X [i] -i | дорівнює 8. Зрозуміло, що їх буде набагато менше: наприклад, всі перестановки, що починаються на 8,7. розглядати не потрібно! Як можна модифікувати наш переборний алгоритм в цьому випадку? Якщо на якомусь етапі сума вже більше 8, то розглядати всі перестановки, що починаються на X [1]. X [k] вже не потрібно - слід повернутися до X [k] і змінити його значення ( "відійти назад" - звідси назва методу). Для такої ситуації ми розглянемо один загальний метод, який майже завжди дозволяє значно скоротити перебір. Нехай шукане рішення знаходиться серед послідовностей виду де кожне X [i] вибирається з деякого безлічі варіантів A [i]. Припустимо ми вже побудували початок цієї послідовності X [1]. X [k] (k Припустимо також, що у нас є деякий простий метод P (X [1]. X [k]), який дозволяє отримати відповідь на питання: чи можна продовжити X [1]. X [k] до рішення (true) чи ні (false). Зауважимо, що значення true ще HЕ ГАРАHТІРУЕТ існування такого продовження, але зате значення false ГАРАHТІРУЕТ непродолжаемость ( "не варто далі і пробувати"). Отримуємо просту рекурсивную процедуру перебору з відходами HАЗАД: Приклад застосування цього методу є в Задачі про 8 ферзів.1.1. послідовності
1.2. перестановки
1.4. підрахунок кількостей
2.3. Послідовності (рекурсивний алгоритм)
2.4. Перестановки (рекурсивний алгоритм)Основна програма:
3. Перебір з відходом назад