if есть_справа then begin {ОНЛН, есть справа}

вправо;

{ОНЛ}

вверх_до_упора_и_обработать;

end else begin

{ОЛН, не есть_справа, есть_снизу}

вниз;

обработать;

end;

end;

{ОНЛН, Робот в корне => все вершины обработаны полностью}

Доказательство правильности алгоритма.

Докажем, что приведенная программа завершает работу (на любом конечном дереве).

Доказательство. Процедура вверх_налево завершает работу (высота Робота не может увеличиваться бесконечно). Если программа работает бесконечно, то, поскольку листья не обрабатываются повторно, начиная с некоторого момента ни один лист не обрабатывается. А это возможно, только если Робот все время спускается вниз. Противоречие.

Блок-схема алгоритма.

Описание переменных и программа.

Теперь реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной k: 0 n (число ферзей) и массива c: array [1 n] of 1 n (c [i] - координаты ферзя на i-ой горизонтали; при i > k значение c [i] роли не играет). Предполагается, что все позиции допустимы (если убрать верхнего ферзя, остальные не бьют друг друга).

program queens;

const n = .;

var k: 0 n;

c: array [1 n] of 1 n;

procedure begin_work; {начать работу}

begin

k := 0;

end;

function danger: boolean; {верхний ферзь под боем}

var b: boolean;

i: integer;

begin

if k <= 1 then begin

danger := false;

end else begin

b := false; i := 1;

{b <=> верхний ферзь под боем ферзей с номерами < i}

while i <> k do begin

b := b or (c[i]=c[k]) {вертикаль}

or (abs(c[i]-c[k])=abs(i-k)); {диагональ}

i := i+ 1;

end;

danger := b;

end;

end;

function is_up: boolean {есть_сверху}

begin

is_up := (k < n) and not danger;

end;

function is_right: boolean {есть_справа}

begin

is_right := (k > 0) and (c[k] < n);

end;

{возможна ошибка: при k=0 не определено c[k]}

function is_down: boolean {есть_снизу}

begin

is_up := (k > 0);

end;

procedure up; {вверх_налево}

begin {k < n}

k := k + 1;

c [k] := 1;

end;

procedure right; {вправо}

begin {k > 0, c[k] < n}

c [k] := c [k] + 1;

end;

procedure down; {вниз}

begin {k > 0}

k := k - 1;

end;

procedure work; {обработать}

var i: integer;

begin

if (k = n) and not danger then begin

for i := 1 to n do begin

write ('<', i, ',' , c[i], '> ');

end;

writeln;

end;

end;

procedure UW; {вверх_до_упора_и_обработать}

begin

while is_up do begin

up;

end

work;

end;

begin

begin_work;

UW;

while is_down do begin

if is_right then begin

right;

UW;

end else begin

down;

end;

end;

end.

Расчёт вычислительной сложности.

Емкостная сложность:

В программе используется одномерный массив размерности n, поэтому объём входа и объём выхода совпадают и равны n. Количество пременных равно 3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.

С(n)=n+4

Временная сложность:

Если рассматривать обработку каждого листа, без проверки на пути к нему, то временная сложность T(n) = n0+n1+n2+n3+…+nn .

Но в случае, когда каждая вершина проверяется, временная сложность T(n) = o(n0+n1+n2+n3+…+nn). И это тем вернее, чем больше n. Данный вывод получен на основе приведённых ниже статистических данных: