Задача про розміщення ферзів. Дерево пошуку та його обхід, Детальна інформація
Задача про розміщення ферзів. Дерево пошуку та його обхід
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 \xF0BC end;
function test \xF0BC end;
procedure deps \xF0BC end;
begin
writeln ('задайте розмір дошки: 4..20>'); readln ( n );
deps ( H, n, 1)
end.
2. Дерево пошуку та його обхід
Розміщення ферзів на шахівниці, що будуються в процесі виконання програми Queens, можна подати вузлами кореневого орієнтованого дерева (рис.19.3).
У цьому дереві кожний вузол, де 0\xF0A3 i
, , \xF0BC , .
Відповідно цей вузол називається їхнім батьком. Сини вузла, сини його синів тощо називаються його нащадками, а він – їхнім попередником. Порожнє розміщення <> є коренем дерева, повні чи недопустимі розміщення – його листками, а допустимі неповні – проміжними вузлами. Кожний вузол дерева має певну глибину, або рівень у дереві. Глибиною кореня є 0, його синів – 1 тощо. Повним розміщенням відповідають листки дерева, які в даному разі мають глибину n. Зазначимо, що в даному разі глибина вузлів дерева збігається з довжиною їх як розміщень.
Це дерево відбиває пошук повних допустимих розміщень, тому називається деревом пошуку. Пересування по вузлах дерева у визначеному порядку називається обходом дерева. Отже, пошук розміщень у дереві є результатом його обходу.
Задамо алгоритм, реалізований процедурою deps із програми Queens, в узагальненому вигляді. Нехай A позначає вузол дерева, ОБХІД( A ) – обхід дерева з коренем А, а синами вузла A є A(1), A(2), \xF0BC , A(n). Тоді процедура deps із програми Queens має таку схему:
for k := 1 to n do
begin
перехід до вузла A(k);
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 \xF0BC end;
function test \xF0BC end;
procedure deps \xF0BC end;
begin
writeln ('задайте розмір дошки: 4..20>'); readln ( n );
deps ( H, n, 1)
end.
2. Дерево пошуку та його обхід
Розміщення ферзів на шахівниці, що будуються в процесі виконання програми Queens, можна подати вузлами кореневого орієнтованого дерева (рис.19.3).
У цьому дереві кожний вузол
Відповідно цей вузол називається їхнім батьком. Сини вузла, сини його синів тощо називаються його нащадками, а він – їхнім попередником. Порожнє розміщення <> є коренем дерева, повні чи недопустимі розміщення – його листками, а допустимі неповні – проміжними вузлами. Кожний вузол дерева має певну глибину, або рівень у дереві. Глибиною кореня є 0, його синів – 1 тощо. Повним розміщенням відповідають листки дерева, які в даному разі мають глибину n. Зазначимо, що в даному разі глибина вузлів дерева збігається з довжиною їх як розміщень.
Це дерево відбиває пошук повних допустимих розміщень, тому називається деревом пошуку. Пересування по вузлах дерева у визначеному порядку називається обходом дерева. Отже, пошук розміщень у дереві є результатом його обходу.
Задамо алгоритм, реалізований процедурою deps із програми Queens, в узагальненому вигляді. Нехай A позначає вузол дерева, ОБХІД( A ) – обхід дерева з коренем А, а синами вузла A є A(1), A(2), \xF0BC , A(n). Тоді процедура deps із програми Queens має таку схему:
for k := 1 to n do
begin
перехід до вузла A(k);
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021