ВУЗ:
Составители:
Рубрика:
39
'-': begin o1:=Calc0; o2:=Calc0; Result:=o1-o2; end;
'*': begin o1:=Calc0; o2:=Calc0; Result:=o1*o2; end;
'0'..'9': Result:=Ord(s[i])-Ord('0');
end;
end;
begin // Calc
i:=0;
Result:=Calc0;
end;
var res: string;
begin
res:=Prefix('(1+2)*3');
writeln(res); writeln(Calc(res));
end.
2.11 Алгоритм перебора с возвратом
Алгоритм перебора с возвратом используется, когда решение представляет
собой некоторую последовательность элементов:
n
aaa ,...,,
21
. Суть его заключает-
ся в следующем. На каждом этапе имеется некоторое частичное решение
k
aaa ,...,,
21
, к которому мы пытаемся добавить следующий элемент из множества
возможных (происходит перебор возможных продолжений). Процесс добавления
элементов завершается либо когда получено решение, либо когда не остается
элементов, которые можно добавить. Если элементов для добавления нет, а реше-
ние не получено, то последний добавленный элемент удаляется (осуществляется
возврат к предыдущему шагу),
и предпринимается попытка добавить другой эле-
мент. Алгоритм заканчивается если найдено решение либо все варианты исчерпа-
ны.
Пусть глобальная логическая переменная Success получает значение True
как только будет найдено решение. До начала работы алгоритма она должна быть
инициализирована в False. Пусть также i – переменная, характеризующая глу-
бину рекурсии и передаваемая
как параметр рекурсивной процедуре. Запишем ал-
горитм в «крупных командах».
Алгоритм перебора с возвратом для нахождения одного решения
procedure Try0(i: integer);
begin
формирование списка кандидатов
repeat
выбор очередного кандидата (перебор)
if
подходит then
begin
