ПЕРЕБИРАННЯ ВАРІАНТІВ В ПРОГРАМУВАННІ

procedure deps  end;

begin

writeln ('задайте розмір дошки: 4..20>'); readln ( n );

deps ( H, n, 1)

end.

Задачі

1.* Тура атакує фігури на одній із нею вертикалі та горизонталі. Написати програму пошуку всіх розміщень n тур на шахівниці розміром n n, у яких жодна тура не атакує іншу. Зазначимо, що ця задача цілком збігається з задачею побудови всіх перестановок чисел 1, 2,  , n.

2. Упорядкуємо повні розміщення ферзів, уважаючи:

< ,

якщо існує таке i n, що a1=b1,  , ai-1=bi-1 та ai
3.* Написати програму підрахунку загальної кількості вузлів та внутрішніх вузлів дерева розміщень ферзів, тобто числа виконань викликів підпрограм відповідно test і deps. Указати зв'язок між цими числами.

4. Оцінити складність задачі

а) побудови всіх допустимих розміщень тур;

б) побудови найменшого допустимого розміщення ферзів;

в) побудови всіх допустимих розміщень ферзів.

2. Дерево пошуку та його обхід

Розміщення ферзів на шахівниці, що будуються в процесі виконання програми Queens, можна подати вузлами кореневого орієнтованого дерева (рис.19.3).

У цьому дереві кожний вузол , де 0 i
, ,  , .Відповідно цей вузол називається їхнім батьком. Сини вузла, сини його синів тощо називаються його нащадками, а він – їхнім попередником. Порожнє розміщення <> є коренем дерева, повні чи недопустимі розміщення – його листками, а допустимі неповні – проміжними вузлами. Кожний вузол дерева має певну глибину, або рівень у дереві. Глибиною кореня є 0, його синів – 1 тощо. Повним розміщенням відповідають листки дерева, які в даному разі мають глибину n. Зазначимо, що в даному разі глибина вузлів дерева збігається з довжиною їх як розміщень.

Це дерево відбиває пошук повних допустимих розміщень, тому називається деревом пошуку. Пересування по вузлах дерева у визначеному порядку називається обходом дерева. Отже, пошук розміщень у дереві є результатом його обходу.

Задамо алгоритм, реалізований процедурою deps із програми Queens, в узагальненому вигляді. Нехай A позначає вузол дерева, ОБХІД( A ) – обхід дерева з коренем А, а синами вузла A є A(1), A(2),  , A(n). Тоді процедура deps із програми Queens має таку схему: