Техника рекурсивных описаний

Несколько примеров рекурсивных процедур, рассмот­­рен­ных в этом пункте, помогут лучшему усвоению техники примене­ния рекурсии. Мы также увидим преимущества и недостатки рекурсивных описаний.

Пример 7. Ханойские башни.

Классический пример применения рекурсии для описания эффективного алгоритма - зада­ча о ханойских башнях.

Анализ и неформальное описание алгоритма. Пусть N - количество колец на стержне, I - номер кольца, с которого осуществляется перестановка и J - номер кольца, на которое кольца требуется пере­ставить.

HanojTower( N, I, J) - процедура, переставляющая N колец с I-того стержня на J-тый.

Step(I, J) - процедура, переставляющая одно кольцо с I-того стержня на J-тый.

(Если I и J - номера 2-стержней, то 6-I-J - номер третьего стержня.)

Предположим, что мы переместили N-1 кольцо с I-того стержня на 6-I-J стержень. Тогда можно переместить кольцо со стержня I на J.

На стержне J лежит кольцо с наибольшим диаметром, т.е. этот стержень можно использовать без нарушения ограничений, связанных с величинами диаметров. Поэтому можно теперь переставить всю пирамиду из N-1 кольца со стержня 6-I-J на J, и задача решена!

При N = 1 задача решается за один шаг - процедурой Step(I, J). Тем самым установлен базис рекурсии. Опишем теперь процедуру HanojTower(N, I, J):

Procedure HanojTower(N, I, J: Integer);

Begin

If N = 1

then Step(I, J)

else begin

HanojTower(N-1, I, 6-I-J);

Step(I, J);

HanojTower(N-1, 6-I-J, J)

end

End;

Определим сложность алгоритма по времени T(n) в терминах количества шагов (вызовов Step), выписав рекур­рент­ное соотношение:

T(n) = 2T(n-1) + 1

Легко показать, что

T(n) = 2ⁿ - 1.

Пример 8. Линейные диофантовы уравнения. Перечислить все неотрицательные целые решения линейного уравнения

a₁x₁ + a₂x₂ + ... + a_nx_n = b

c целыми положительными коэф­фи­циентами.

Перепишем исходное уравнение в виде:

a₁ x₁ + a₂ x ₂ + ... + a _n-1 x _n-1 = b - a _n x _n

Организуем перебор всевозможных значений x_n, при которых правая часть b-a _n x _n > 0. x_n = 0, 1, ... y, где y = b div a_n. Тогда первые n-1 компонент решения (x₁, ... , x _n-1, x _n) исходного уравнения - решение уравнения

a₁ x₁ + a₂ x₂ + ... + a _n-1 x _n-1 = b - a _n x _n .

Таким образом, мы свели решение исходного уравнения к решению y+1 уравнения с n-1 неизвестным, и, следовательно, можем реализовать алгоритм рекурсивно. Определим условия выхода из рекурсии:

при b = 0 существует единственное решение - (0, 0, ..., 0)

при n = 1 если b mod a₁ = 0

то x₁ = b div a₁

иначе решений нет.

Таким образом, выходить из рекурсивных вычислений нуж­но в двух (крайних) случаях. Мы установили и параметры проце­дуры: n и b, базис рекурсии, шаг рекурсии и условия рекурсии.

Procedure Solution(n, b : integer);

Var I, j, y, z : Integer;

Begin

If b = 0

then begin

For j := 1 to n do X[j] := 0; WriteSolution

end

else If (n = 1) and (b mod a[1] = 0)

then begin

X[1]:= b div a[1]; WriteSolution

end

else If n > 1

then begin

z := a[n]; y := b div z;

For i := 0 to y do begin

X[n] := i; Solution(n - 1, b - z*i)

end

end

End;

Program AllSolutions;

Const n = 4;

Type Vector = array[1..n] of Integer;