Реферат: Математическая логика и теория алгоритмов

вправо;

{ОНЛ}

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

end else begin

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

вниз;

end;

end;

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

Приведенная только что программа обрабатывает вершину до того, как обработан любой из ее потомков. Теперь изменим ее, чтобы каждая вершина, не являющаяся листом, обрабатывалась дважды: один раз до, а другой раз после всех своих потомков. Листья по-прежнему обрабатываются по разу:

Под "обработано ниже и левее" будем понимать "ниже обработано по разу, слева обработано полностью (листья по разу, остальные по два)". Под "обработано ниже, левее и над" будем понимать "ниже обработано по разу, левее и над - полностью".

Программа будет такой:

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

{дано: (ОНЛ), надо: (ОНЛН)}

begin

{инвариант: ОНЛ}

while есть_сверху do begin

обработать

вверх_налево

end

{ОНЛ, Робот в листе}

обработать;

{ОНЛН}

end;

Основной алгоритм:

дано: Робот в корне, ничего не обработано

надо: Робот в корне, все вершины обработаны

{ОНЛ}

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