ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Полное исключение рекурсий

Алгоритмы структуры данных

Полное исключение рекурсий

Описанная выше техника исключения рекурсивных вызовов полностью удаляет рекурсии только тогда, когда рекурсивные вызовы находятся в конце процедур и вызов осуществляется в форме, позволяющей его исключить. Существует более общий подход, позволяющий преобразовать любую рекурсивную процедуру (или функцию) в нерекурсивную, но этот подход вводит определяемые пользователем стеки. В общем случае этот стек хранит следующее.

1.    Текущие значения параметров процедуры.2.   Текущие значения всех локальных переменных процедуры.

3.   Адрес возврата, т.е. адрес места, куда должно перейти управление после завершения процедуры.

В случае функции knapsack положение упрощается. Во-первых, заметим, что при всех вызовах (при этом происходит вставка записи в стек) параметр candidate увеличивается на единицу. Поэтому мы можем хранить значение candidate как глобальную переменную, значение которой увеличивается на единицу при вставке записи в стек и уменьшается на единицу при извлечении записи из стека.

Во-вторых, следующее упрощение можно сделать, если в стеке хранить модифицированный адрес возврата. Отметим, что адрес возврата для этой функции может находиться или в другой процедуре, вызвавшей knapsack, или в строке (5), или в строке (8). Можно представить эти три возможности с помощью "статуса", который может принимать три значения.

1.    попе (нет). Показывает, что вызов осуществлен из внешней процедуры.

2.    included (включенный). Указывает на вызов из строки (5), которая включает вес weights[candidate] в возможное решение.

3.   excluded (исключенный). Указывает на вызов из строки (8), которая исключает вес weights[candidate] из возможного решения.

Если мы сохраним статус как адрес возврата, то сможем рассматривать target как глобальную переменную. При изменении статуса с попе на included мы вычитаем вес weights[candidate] из target и прибавляем его обратно при изменении статуса с included на excluded. Чтобы показать, что рекурсивно вызываемой knapsack найдено решение, используем глобальную переменную winflag (флаг победы). Получив один раз значение true, winflag сохраняет это значение, из стека извлекаются записи, и те веса, которые имеют статус included, распечатываются. В описанной ситуации стек можно объявить как список статусов (statuses) следующим способом:

type

statuses =   (none,   included,   excluded); STACK =  {  подходящее объявление стека  }

В листинге 2.15 приведена нерекурсивная процедура knapsack, оперирующая с массивом весов weights. Хотя эта процедура может выполняться быстрее, чем исходная рекурсивная функция knapsack, но видно, что код ее длиннее и она труднее для понимания. Поэтому исключение рекурсий следует применять только тогда, когда скорость выполнения программы является решающим фактором.

Листинг 2.15

procedure knapsack ( target: integer );

var

candidate: integer;

winflag: boolean;

S: STACK;

begin

Candidate:= 1,

winflag:= false;

MAKENULL(S)

PUSH(none, S) ;

{инициализация стека для рассмотрения weights[1]}

repeat

if winflag then begin

{ извлечение записи из стека и

печать весов, входящих в решение }

if TOP(S) = included then

writeln(weights[candidate]);

Candidate:= candidate - 1;

POP(S)

end

else if  target = 0 then begin  {  решение найдено  }.

winflag:=  true;

Candidate:=  candidate -  1;

POP(S)

end

else if   (((target < 0)   and   (TOP(S)   = none))

or   (candidate > n))   then begin  {  решения нет  }

candidates  candidate -  1;

POP(S)

end

else { решения пока нет,

рассматривается статус текущего кандидата }

if TOP(S) = none then begin

{ первая попытка включить кандидата } target:= target - weights[candidate]; candidate:= candidate + 1;

POP(S); PUSH(included, S); PUSH(none, S)

end

else if TOP(S) = included then begin

{ попытка исключить кандидата }

target:= target + weignts[Candidate];

Candidate:= candidate + 1;

POP(S); PUSH(excluded, S); PUSH(none, S)

end

else begin { TOP(S) = excluded;

отказ от текущего выбора }

POP(S);

Candidate:= candidate - 1

end

until EMPTY(S)

end; { knapsack }

 

 

 

 

 

30