Перебирання варіантів в програмуванні, Детальна інформація

Перебирання варіантів в програмуванні
Тип документу: Реферат
Сторінок: 10
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 26.4
Скачувань: 908
{перевірка, чи займається нова горизонталь і діагональ}

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