Перебирання варіантів в програмуванні, Детальна інформація
Перебирання варіантів в програмуванні
{перевірка, чи займається нова горизонталь і діагональ}
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.
Задачі
1.* Тура атакує фігури на одній із нею вертикалі та горизонталі. Написати програму пошуку всіх розміщень n тур на шахівниці розміром n\xF0B4 n, у яких жодна тура не атакує іншу. Зазначимо, що ця задача цілком збігається з задачею побудови всіх перестановок чисел 1, 2, \xF0BC , n.
2. Упорядкуємо повні розміщення ферзів, уважаючи:
< ,
якщо існує таке i\xF0A3 n, що a1=b1, \xF0BC , ai-1=bi-1 та ai
3.* Написати програму підрахунку загальної кількості вузлів та внутрішніх вузлів дерева розміщень ферзів, тобто числа виконань викликів підпрограм відповідно test і deps. Указати зв'язок між цими числами.
4. Оцінити складність задачі
а) побудови всіх допустимих розміщень тур;
б) побудови найменшого допустимого розміщення ферзів;
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.
Задачі
1.* Тура атакує фігури на одній із нею вертикалі та горизонталі. Написати програму пошуку всіх розміщень n тур на шахівниці розміром n\xF0B4 n, у яких жодна тура не атакує іншу. Зазначимо, що ця задача цілком збігається з задачею побудови всіх перестановок чисел 1, 2, \xF0BC , n.
2. Упорядкуємо повні розміщення ферзів, уважаючи:
якщо існує таке i\xF0A3 n, що a1=b1, \xF0BC , ai-1=bi-1 та ai
3.* Написати програму підрахунку загальної кількості вузлів та внутрішніх вузлів дерева розміщень ферзів, тобто числа виконань викликів підпрограм відповідно test і deps. Указати зв'язок між цими числами.
4. Оцінити складність задачі
а) побудови всіх допустимих розміщень тур;
б) побудови найменшого допустимого розміщення ферзів;
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021