ємо кількість смужок з діаграмою
суміжності code і різними закінченнями}
for i: = 1 to 3 do
answer: = answer + total [n mod 2, i, code];
writeln (answer: 0:0)
end.
Схожа задача ("Симпатичні візерунки") пропонувалася і на I-ої Всеросійської командної олімпіаді з програмування. Її умову і рішення можна прочитати в [2]. p> Задача 11 . Паркет ( Завдання VI Всеросійської олімпіади з інформатики, 1994 р. )
Кімнату розміром N ' M одиниць потрібно покрити однаковими паркетними плитками розміром 2'1 одиницю без пропусків і накладень (1 ВЈ N ВЈ 20, 1 ВЈ M ВЈ 8). Потрібно визначити кількість всіх можливих способів укладання паркету для конкретних значень N і M . p> Рішення. Нехай M - ширина кімнати, яку ми зафіксуємо. Спробуємо висловити шукану кількість укладок паркету для кімнати довжини N , через кількість укладок для кімнати довжиною N - 1. Однак очевидно, що зробити це не вдасться, так як існує ще безліч укладок, в яких частина плиток перетинає кордон між такими кімнатами. Отже нам знову доведеться вирішувати додаткове число підзадач. А саме, введемо узагальнене поняття укладання кімнати довжиною N - 1: перша частина кімнати довжиною N - 2 покладена щільно, а в ( N - 1)-й одиниці вимірювання довжини кімнати можуть знаходитися порожнечі (у N -й одиниці виміру паркету немає). Якщо наявність плитки в ( N - 1)-й одиниці виміру позначити 1, а її відсутність - 0, то кількість різних закінчень подібних укладок можна пронумерувати двійковими числами від 0 до 2 M - 1. Якщо кількість укладок для кожного з закінчень нам відомо (частина з них можуть виявитися нереалізованим, то є відповідна кількість укладок буде дорівнює 0), то ми зможемо підрахувати кількість різних укладок кімнати довжини N . При цьому доведеться перевіряти сумісність закінчень. Закінчення будемо вважати сумісними, якщо шляхом додавання цілого числа плиток до укладі довжиною N - 1 із закінченням j , таких що кожна з них збільшує довжину укладання до N , ми можемо отримати закінчення i укладання довжиною N . Якщо спосіб суміщення укладок існує, то з побудови він єдиний. Тоді для визначення кількості укладок із закінченням i довжиною N необхідно підсумувати кількості укладок довжиною N - 1 з сумісними закінченнями. Для кімнати нульової довжини будемо рахувати кількість укладок рівним 1. Формування динамічної схеми закінчено. Кількість збережених в програмі значень при цьому одно 2'2 M = 2 M +1 , тобто воно експоненціально залежить від одного з параметрів задачі і істотно його збільшити не представляється можливим. У нашому випадку воно дорівнює 512, тобто застосування табличного методу рішення виявляється реальним. Відповідь на питання завдання буде отриманий на N -му кроці алгоритму в елементі таблиці з номером 2 M - 1. При максимальному за умовою задачі розмірі кімнати для отримання відповіді знову буде потрібно "довга арифметика".
Схему програми для вирішення цього завдання, яка простіше попередньої, можна знайти, наприклад, в [3].
Після розгляду завдань 9-11 може скластися враження, що до даного класу відносяться лише завдання підрахунку кількостей тих чи інших конфігурацій, в тому числі комбінаторних. Звичайно ж це не так. Прикладом оптимізаційної завдання, вирішення якої базується на аналогічних ідеях, служить завдання "Бізнес-класики", предлагавшаяся на XIII Всеросійської олімпіаді з програмування (див. [4]).
Багато прикладні та олімпіадні задачі легко сформулювати у термінах такої структури даних як граф. Для ряду подібних завдань добре вивчені ефективні (Поліноміальні) алгоритми їх вирішення. Розглянемо в даній лекції ті з них, які використовують ідеї динамічного програмування. Але насамперед необхідно познайомитися з деякими термінами, що зустрічаються при описі цієї структури.
В
2. Основні визначення теорії графів
Графом називається пара, де V - деяке безліч, яке називають безліччю вершин графа, а E - відношення на V () - безліч ребер графа. Тобто всі ребра з безлічі E з'єднують деякі пари точок з V .
Якщо ставлення E симетричне (тобто), то граф називають неорієнтованим , в Інакше граф називають орієнтованим . Фактично для кожного з ребер орієнтованого графа вказані початок і кінець, тобто пара ( u , v ) впорядкована, а в неорієнтованому графі ( u , v ) = ( v , u ).
Якщо в графі існує ребро ( u , v ), то говорять, що вершина v суміжно з вершиною u (в орієн...
