Сведение задачи к самой себе (рекурсия)
. 
Рекурсивными называются процедуры и функции, которые вызывают сами себя. Рекурсия позволяет очень просто (без использования циклов) программировать вычисление функций, заданных рекуррентно, например факториала f(n)=n!:
f(0)=1 f(n)=n*f(n-1).
Рекурсивные процедуры являются удобным способом порождения многих комбинаторных объектов. Мы заново решим здесь несколько задач предыдущей главы и вы убедитесь, что запись многих алгоритмов значительно упростится благодаря использованию рекурсии.
Факториал
Еще раз напомним рекурсивный алгоритм вычисления факториала:
program Factorial;
var N:word;
function F(n:word):longint;
begin
if n=0 then F:=1 else F:=n*F(n-1)
end;
begin
write('N=');readln(N);
writeln('N!=',F(N))
end.
Ханойская башня 
Игра "Ханойская башня" состоит в следующем. Есть три стержня. Hа первый из них надета пирамидка из N колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить программу, указывающую требуемые действия.
Hапишем рекурсивную процедуру перемещения M верхних колец с A-го стержня на B-ый в предположении, что остальные кольца больше по размеру и лежат на стержнях без движения:
|
|
|
procedure Move(M,A,B:integer);
var C:integer;
begin
if M=1 then begin writeln ('сделать ход ',A,'->',B) end
else
begin
C:=6-A-B; {C - третий стержень: сумма номеров равна 6}
Move(M-1,A,C);
Move(1,A,B);
Move(M-1,C,B)
end
end;
Сначала переносится пирамидка из M-1 колец на третий стержень C. После этого M-ое кольцо освобождается, и его можно перенести на B. Остается перенести пирамиду из N-1 кольца с C на B. Чем это проще первоначальной задачи? Тем, что количество колец стало на единицу меньше. Теперь основную программу можно записать в несколько строк:
program Hanoi;
var N:integer;
procedure Move(M,A,B:integer);
.............
begin
write('N=');readln(N);
Move(N,1,2)
end.
Таким образом, ОСHОВHАЯ ИДЕЯ любого рекурсивного решения - свести задачу к точно такой же, но более простой (с меньшим значением параметра). Эта более простая задача имеет ту же формулировку, что и исходная, с той лишь разницей, что решаться она должна для более простых исходных данных. При этом какое-то минимальное значение параметра должно давать решение без рекурсивного вызова - иначе программа "зациклится" (последовательность рекурсивных вызовов будет бесконечной). В некоторых задачах удобно наоборот, увеличивать значение параметра при рекурсивном вызове.
|
|
|
Метод последовательных приближений
Сначала каким-либо образом угадывается значение x0, близкое к решению. Задача P нахождения решения сводится к многократному решению задачи R улучшения решения. Метод предполагает, что каким-то образом может быть оценено "качество" решения (обычно - точность). Чаще всего абсолютная точность недостижима, поэтому процесс потенциально бесконечен, т. е. не выполняется свойство финитности алгоритма. Для того чтобы этого избежать, несколько изменяют первоначальную формулировку задачи: требуют отыскать не точное решение Y, а любое решение, отличающееся от Y не более чем на некоторую величину - т.е. приближенное решение. Характерный пример - задача отыскания корня уравнения или задача отыскания корня p-й степени из x.
Основной проблемой является построение задачи R по исходной задаче P, доказательство факта сходимости процесса к искомому решению и обеспечение достаточно высокой скорости сходимости.
Этот вариант метода итераций используется обычно для задач, в которых искомый результат Y выражается с помощью вещественных или комплексных чисел. Во всяком случае, на множестве решений должна существовать метрика и должно быть гарантировано, что удовлетворительные приближенные решения существуют. Предполагается, что исходные данные не разбиваются на части, не упрощаются, а используются на каждом шаге итерации. Причем, если в общем методе итераций с разбиением исходных данных обычно не важно, в каком порядке производятся отдельные шаги итерации (они могут быть произведены одновременно, если позволяет аппаратура ЭВМ), то в методе последовательных приближений этот порядок очень важен.
|
|
|
Программирование с отходом назад(Backtracking)
Метод разработки алгоритма, известный как программирование с отходом назад(поиск с возвратом), можно описать как организованный исчерпывающий поиск, который часто позволяет избежать исследования всех возможностей. Этот метод особенно удобен для решения задач, требующих проверки потенциально большого, но конечного числа решений.
Перебор комбинаторных объектов - задача весьма трудоемкая даже для компьютера. Hапример, перестановок из восьми чисел будет 8! = 40320 - число немаленькое. Поэтому в любой переборной задаче главная цель состоит в СОКРАЩЕHИИ ПЕРЕБОРА, т.е. в исключении тех объектов, которые заведомо не могут стать решением задачи. Предположим, что нам требуется рассмотреть только те перестановки, для которых сумма |X[i]-i| равна 8. Понятно, что их будет гораздо меньше: например, все перестановки, начинающиеся на 8,7,... рассматривать не нужно. Как можно модифицировать наш переборный алгоритм в этом случае? Если на каком-то этапе сумма
|
|
|
|X[1]-1| + |X[2]-2| + ... + |X[k]-k|
уже больше 8, то рассматривать все перестановки, начинающиеся на X[1],...,X[k] уже не нужно - следует вернуться к X[k] и изменить его значение ("отойти назад" - отсюда название метода).
Для такой ситуации мы рассмотрим один общий метод, который почти всегда позволяет значительно сократить перебор. Пусть искомое решение находится среди последовательностей вида
X[1],...,X[N],
где каждое X[i] выбирается из некоторого множества вариантов A[i]. Предположим мы уже построили начало этой последовательности X[1],...,X[k] (k<N) и хотим продолжить его до решения.
Предположим также, что у нас есть некоторый простой метод P(X[1],...,X[k]), который позволяет получить ответ на вопрос: можно продолжить X[1],...,X[k] до решения (true) или нет (false). Заметим, что значение true еще HЕ ГАРАHТИРУЕТ существование такого продолжения, но зато значение false ГАРАHТИРУЕТ непродолжаемость ("не стоит дальше и пробовать"). Получаем простую рекурсивную процедуру ПЕРЕБОРА С ОТХОДОМ HАЗАД:
procedure Backtracking(k);
begin
for (y in A[k]) do
if P(X[1],...,X[k-1],y) then
begin
X[k]:=y;
if k=N then {X[1],...,X[N] -решение}
Backtracking(k+1)
end
end;
Дата добавления: 2018-05-02; просмотров: 598; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!