Преимущества и недостатки рекурсивных алгоритмов

End.

Solution(n, b)

End

End

Then begin

End

Then begin

End

Then begin

Begin

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

End

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

Else begin

Then Step(I, J)

Begin

If N = 1

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

Step(I, J);

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;

If b = 0

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

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

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

else If n > 1

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

For i:= 0 to y do begin

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

End;

Program AllSolutions;

Const n = 4;

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

Var a, X: Vector; b: Integer; i: Integer;

{Procedure WriteSolution печатает решение X[1..n]}

{Procedure Solution}

Begin {раздел операторов основной программы}

{Ввод массива a[1..n] и св. члена b}

Рассмотренные примеры показывают, что применение рекурсивных определений само по себе не приводит к хорошим решениям задач.

Так, задачи примеров 2, 3, 6, 7 допускают более эффективные и достаточно простые итеративные решения. В примере 6 это продемон­стри­ровано особенно наглядно.

В примерах 2, 3, 7 рекурсия моделирует простой цикл, тратя время на вычисления, связанные с управлением рекурсивными вызо­вами и память на динами­ческое хранение данных. Сложнее реали­зовать итеративную версию алгоритма примера 4.

Несомненным достоинством алгоритмов из примеров 3, 5, 8 является их простота и обоснованность. При програм­ми­ро­ва­нии мы по существу одновременно обосновывали прави­ль­ность алгоритма. В примерах 5, 8, 9 рассматриваются комбинаторные задачи, решение кото­рых не сводится к простому применению цикла, а требует перебора вариантов, естест­венным образом управляемого рекурсивно. Итеративные версии решений этих задач сложнее по управлению. Можно сказать, что основная вычислительная сложность комбинаторной задачи заключена не в реализации алгоритма ее решения, а в самом методе решения.

Позже мы увидим, как рекурсия в сочетании с другими метода­ми используется для построения эффективных алгоритмов.

Дата добавления: 2014-01-06