4. способы повышения эффективности алгоритмов

procedure try (i)
begin k  0; (* инициировать выборку возможных шагов*)
repeat k  k+1; выбрать k-й возможный путь;
if приемлемо then
begin записать его;
if i< n then (* решение неполно*)
begin try (I+1); (*попробовать очередной шаг*)
if неудачно then стереть запись
end
end
until удачно  (k=m)
end.
Алгоритмы нумерации узлов дерева в соответствии
с внутренним порядком


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


PROCEDURE INOR (ND)
begin
1. if LES[ND]0 then;
2. NUM[ND]  COT;
3. COT  COT+1
4. if RIS[ND]0 then INOR (RIS[ND])
end
2. Алгоритм без использования рекурсии ( но с использованием
стека)
PROCEDURE INOR (ND)
begin
COT  1
ND  RT
STK  0
L (left): while LES[ND]0 do
begin
PUSH ( *затолкнуть узел в стек* )
ND  LES[ND]
end;
C(centre): NUM[ND]  COT;
COT  COT+1;
if RIS[ND]0 then
begin
ND  RIS[ND]
goto L
end
if STK0 then
begin
ND  ETS ( * присвоить узлу номер элемента, находящегося в вершине стека*)
POP ( *вытолкнуть узел из стека*)
goto C
end
end
NUM (NUMber - номер) - массив, такой, что NUM[i] - номер узла во внутреннем порядке
COT (COunt - счет ) глобальная переменная с начальным значением 1
ND (NoDe - узел) - параметр, вначале равный корню RT (RooT)
INOR - internal order - внутренний порядок
STK - стек ( STacK)
ETS - элемент в вершине стека ( Element in the top of Stack)


МАТЕМАТИЧЕСКАЯ МУДРОСТЬ : Общего вида задачу решать проще, чем частную задачу!
[Пойа]

Рассмотрим процедуру INOR из алгоритма 4.1. Когда, например, она вызывает себя с фактическим параметром LES[ND], она запоминает в стеке адрес нового значения параметра ND вместе с адресом возврата, который указывает, что по окончании работы этого вызова выполнение программы продолжается со строки 2. Таким образом, переменная ND эффективно заменяется на LES[ND], где бы не входил ND в это определение процедуры.

В алгоритме 4.2. сделано так, что окончание выполнения вызова INOR с фактическим параметром RIS[ND] завершает выполнение и самой вызывающей процедуры. Поэтому нам не обязательно теперь хранить адрес возврата или узел(ND) в стеке если фактическим параметром является RIS[ND].