Сторінка
1
1. Задача про розміщення ферзів Розглянемо шахівницю, що має розміри не 8´ 8, а n´ n, де n>0. Як відомо, шаховий ферзь атакує всі клітини та фігури на одній з ним вертикалі, горизонталі та діагоналі. Будь-яке розташування кількох ферзів на шахівниці будемо називати їх розміщенням. Розміщення називається допустимим, якщо ферзі не атакують одне одного. Розміщення n ферзів на шахівниці n´ n називається повним. Допустимі повні розміщення існують не при кожному значенні n. Наприклад, при n=2 або 3 їх немає. За n=4 їх лише 2 (рис.19.1), причому вони дзеркально відбивають одне одного. Задача. Написати програму побудови всіх повних допустимих розміщень n ферзів, де 4£ n£ 20. Для початку з'ясуємо деякі властивості допустимих розміщень. Очевидно, що в них кожний ферзь займає окрему вертикаль і горизонталь. Занумеруємо вертикалі й горизонталі номерами 1, … , n та позначимо через <H1, H2, ¼ , Hi> послідовність номерів горизонталей, зайнятих ферзями, що стоять у вертикалях 1, 2, ¼ , i, де 0£ i£ n. Випадок i=0 відповідає порожньому розміщенню <>. Існує n способів розмістити ферзя в першій вертикалі, тобто перейти від порожнього розміщення до непорожнього. Цей перехід позначимо стрілкою (рис. 19.2(а)). За кожного з розміщень ферзя в першій вертикалі є n варіантів розміщення ферзя в другій вертикалі, але з них слід відкинути недопустимі. Відмітимо їх знаком '*' (рис.19.2(б)). Узагалі, нехай зафіксовано розміщення ферзів у перших i-1вертикалях:
S(i-1)=<H1,¼ ,Hi-1>. Для побудови всіх допустимих розміщень із початком S(i-1) треба перебрати всі допустимі розміщення S(i)з ферзем у i-й вертикалі та для кожного побудувати всі допустимі розміщення з початком S(i). Отже, маємо рекурсивний алгоритм побудови всіх допустимих розміщень, за яким пошук усіх допустимих заповнень ферзями останніх n-i+1вертикалей зводиться до пошуку заповнень n-i вертикалей. Уточнимо цей алгоритм рекурсивною процедурою deps. Нехай розмір шахівниці не більше nm=20. Номери вертикалей та діагоналей містяться в діапазоні nums=1 nm, а розміщення зображається станом масиву H типу arh = array[ nums ] of nums. Процедура deps задає побудову розміщення, починаючи з i-ї вертикалі за фіксованих H[1], ¼ , H[i-1]. Підпрограми test та writs задають відповідно перевірку допустимості розміщення <H[1], … , H[i-1], H[i]> та друкування повного розміщення. Вони викликаються у процедурі deps: procedure deps ( var H : arh; n, i : nums); var j, k : nums; begin for k := 1 to n do begin H[i] := k; if test ( H, i) then if i = n then writs ( H, n) {друкування повного розміщення } else deps ( H, n, i+1 ) {рекурсивний виклик} end end Функція test задає перевірку допустимості розміщення <H[1], ¼ , H[i-1], H[i]> за умови, що <H[1], ¼ , H[i-1]> є допустимим: function test ( var H : arh; i : nums ) : boolean; var j : nums; flag : boolean; begin j := 1; flag := true; {перевірка, чи займається нова горизонталь і діагональ} while ( j < i ) and flag do begin flag := ( H[i] <> H[j] ) and ( abs ( H[i]-H[j] ) <> i-j ); j := j+1 end; test := flag end Розробка процедури writs друкування повного розміщення залишається вправою. Програма розв'язання задачі має такий вигляд: program Queens ( input, output ); const nm = 20; type nums = 1 nm; arh = array[ nums ] of nums; var H : arh; n : nums; procedure writs ¼ end; function test ¼ end; procedure deps ¼ end; begin writeln ('задайте розмір дошки: 4 20>'); readln ( n ); deps ( H, n, 1) end. Задачі 1.*Тура атакує фігури на одній із нею вертикалі та горизонталі. Написати програму пошуку всіх розміщень n тур на шахівниці розміром n´ n, у яких жодна тура не атакує іншу. Зазначимо, що ця задача цілком збігається з задачею побудови всіх перестановок чисел 1, 2, ¼ , n. 2. Упорядкуємо повні розміщення ферзів, уважаючи: <a1, a2, ¼ , an> < <b1, b2, ¼ , bn>, якщо існує таке i£ n, що a1=b1, ¼ , ai-1=bi-1 та ai<bi. Написати програму побудови розміщення ферзів, найменшого за таким упорядкуванням. 3.* Написати програму підрахунку загальної кількості вузлів та внутрішніх вузлів дерева розміщень ферзів, тобто числа виконань викликів підпрограм відповідно test і deps. Указати зв'язок між цими числами. 4. Оцінити складність задачі а) побудови всіх допустимих розміщень тур; б) побудови найменшого допустимого розміщення ферзів; в) побудови всіх допустимих розміщень ферзів.
2. Дерево пошуку та його обхід Розміщення ферзів на шахівниці, що будуються в процесі виконання програми Queens, можна подати вузлами кореневого орієнтованого дерева (рис.19.3). У цьому дереві кожний вузол <H[1], ¼ , H[i]>, де 0£ i<n, має синів
<H[1], ¼ , H[i], 1>, <H[1], ¼ , H[i], 2>, ¼ , <H[1], ¼ , H[i], n>. Відповідно цей вузол називається їхнім батьком. Сини вузла, сини його синів тощо називаються його нащадками, а він – їхнім попередником. Порожнє розміщення <> є коренем дерева, повні чи недопустимі розміщення – його листками, а допустимі неповні – проміжними вузлами. Кожний вузол дерева має певну глибину, або рівень у дереві. Глибиною кореня є 0, його синів – 1 тощо. Повним розміщенням відповідають листки дерева, які в даному разі мають глибину n. Зазначимо, що в даному разі глибина вузлів дерева збігається з довжиною їх як розміщень. Це дерево відбиває пошук повних допустимих розміщень, тому називається деревом пошуку. Пересування по вузлах дерева у визначеному порядку називається обходом дерева. Отже, пошук розміщень у дереві є результатом його обходу. Задамо алгоритм, реалізований процедурою deps із програми Queens, в узагальненому вигляді. Нехай A позначає вузол дерева, ОБХІД( A ) – обхід дерева з коренем А, а синами вузла A є A(1), A(2), ¼ , A(n). Тоді процедура deps із програми Queens має таку схему: for k := 1 to n do begin перехід до вузла A(k); if A(k) є допустимим then if A(k) є листком then обробка листка A(k) else ОБХІД( A(k) ) end Як бачимо, процедура deps задає обхід дерева пошуку з вузлів-розміщень ферзів. Цей обхід називається обходом дерева у глибину. Ця назва зумовлена тим, що обхід дерева з довільним коренем закінчується лише після того, як закінчено обхід усіх його нащадків. Тобто від вузла ми переходимо до його нащадків, заглиблюючися в дерево. Обхід дерева в глибину відтворюється за допомогою магазина (стека), до якого додаються та з якого вилучаються вузли дерева. З кожним вузлом дерева пов'яжемо інформацію, яка додається при переході до цього вузла. В задачі про розміщення ферзів кореневий вузол відповідає порожньому розміщенню, тому з ним ніяка інформація не пов'язана. При переході від вузла, що подає розміщення <H[1], ¼ , H[i]>, до вузла, відповідного розміщенню <H[1], ¼ , H[i], k>, збільшується номер останньої вертикалі i, в k-у клітину якої ставиться ферзь. Отже, з вузлом зв'язується пара чисел (i, k), що є номерами вертикалі й горизонталі. Саме такі пари додаються до магазина вузлів. У задачі про ферзі роль магазина відіграє масив H. Збільшення номера вертикалі i, тобто перехід до наступного компонента масиву, разом із присвоюванням H[i]:=k відтворюють додавання до магазина нового елемента – пари (i, k). Цикл із заголовком for k := 1 to n do у процедурі deps задає перебирання вузлів-"братів"
Завантажити реферат