Рекурсия: различия между версиями

81 байт убрано ,  10 лет назад
м
робот косметические изменения
м (робот косметические изменения)
При вычислении значения <math>F(6)</math> будут вызваны процедуры вычисления <math>F(5)</math> и <math>F(4)</math>. В свою очередь, для вычисления последних потребуется вычисление двух пар <math>F(4)</math>, <math>F(3)</math> и <math>F(3)</math>, <math>F(2)</math>. Можно нарисовать «дерево рекурсивных вызовов».
 
[[ИзображениеФайл:treerecurs.jpg]]
 
Можно заметить, что <math>F(3)</math> вычисляется три раза. Если рассмотреть вычисление <math>F(n)</math> при больших <math>n</math>, то повторных вычислений будет очень много. Это и есть основной недостаток рекурсии — повторные вычисления одних и тех же значений. Кроме того, с рекурсивными функциями связана одна серьезная ошибка: дерево рекурсивных вызовов может оказаться бесконечным и компьютер «зависнет». Важно, чтобы процесс сведения задачи к более простым когда-нибудь заканчивался.
Есть способ решить проблему повторных вычислений. Он очевиден — нужно запоминать найденные значения, чтобы не вычислять их каждый раз заново. Конечно, для этого придётся активно использовать память.
 
[[ИзображениеФайл:fibtree2.jpg]]
 
Например, рекурсивный алгоритм вычисления чисел Фибоначчи легко дополнить тремя «строчками»:
На международной олимпиаде по информатике в 1994 году в первый день среди прочих задач была дана следующая задача.
 
[[ИзображениеФайл:goldenmount.jpg]]
 
'''Формулировка задачи''': На рисунке показан пример треугольника из чисел. Написать программу, вычисляющую наибольшую сумму чисел, через которые проходит путь, начинающийся на вершине и заканчивающийся где-то на основании.
Можно заметить, что в любом месте горы начинается гора меньшего размера, будем называть такие горы ''горками''. Пусть число <math>a(i, j)</math> есть число в треугольнике, находящееся в <math>i</math>-й строчке на <math>j</math>-м месте, а число <math>(i, j)</math> есть максимальное значение суммы, которое можно получить спускаясь с горки, начиная с этого элемента. Понятно, что <math>(i, j)</math> есть число <math>a(i, j)</math> плюс максимум из двух вариантов: <math>(i + 1, j)</math> и <math>(i + 1, j + 1)</math>. Эти два варианта соответствуют тому, что мы можем спуститься вниз-вправо или вниз-влево. Получилось рекурсивное определение: <math>S(i, j) = a(i, j) + \max \Big( S(i + 1, j),\; S(i + 1, j + 1) \Big)</math>. На основе этой рекуррентной формулы можно написать рекурсивный алгоритм. Но нужно быть осторожным. Попробуем вычислить время работы нашего алгоритма при входных данных максимального размера — 100 строк. Рекурсивный алгоритм вычисления функции <math>S(i, j)</math> перебирает все возможные пути. Сколько их? На каждом шаге есть возможность выбрать один вариант из двух (направо или налево). Количество шагов равно количеству строк треугольника. Значит, количество всех путей равно <math>2^{100}</math>(Покажите, что число путей из вершины до <math>j</math>-го элемента <math>i</math>-й строчки равно биномиальному коэффициенту <math>C_i^j</math>) Это очень большое число. Столько вариантов не успеет перебрать даже самая мощная вычислительная техника. Если предположить, что машина просматривает миллиард вариантов в секунду, то понадобится <math>\frac{2^{100}}{10^9}</math> секунд. Чтобы считать было удобнее, заметим, что <math>\frac{2^{100}}{10^9} = \frac{16^{25}}{10^9} > 10^{25} / 10^9 = 10^{16}</math> секунд, что соответствует более, чем <math>10^{12}</math> часов, или более <math>10\,000\,000</math> лет. Понятно, что такая программа никому не нужна, её результаты узнать невозможно. За такое время все компьютеры, решающие эту задачу, превратятся в пыль.
 
[[ИзображениеФайл: triangles.jpg]]
 
На рисунке обозначены две горки (треугольники): одна с вершиной в числе 3, другая с вершиной в числе 8. Эти горки пересекаются, и их пересечение тоже горка с вершиной в числе 1. Можно заметить, что при вычислении самого лучшего пути по рекурсивному алгоритму горка с вершиной в числе 1 будет использоваться дважды. Для горок с вершинами в нижних строчках повторных вызовов будет ещё больше. Это и есть причина медленности работы алгоритма.
=== Задача 10 ===
 
[[ИзображениеФайл: graphpaths.jpg]]
 
Найдите число различных путей из точки <math>A</math> в точку <math>B</math> по стрелочкам. Напишите программу, которая вычисляет число этих путей для таких треугольных конфигураций (графов) со стороной <math>n</math>.
 
=== Задача 11 ===
 
Число правильных скобочных структур длины 6 равно 5: <code>()()()</code>, <code>(())()</code>, <code>()(())</code>, <code>((()))</code>, <code>(()())</code>.
[[w:Снежинка Коха|Снежинка Коха]] — это фрактальное множество точек на плоскости, которое похоже на снежинку.
 
[[ИзображениеФайл:Снежинка_Коха.png]]
 
Здесь приведена программа на языке [[w:PostScript|PostScript]]. Этот код интерпрерируется программой GSView, которую можно взять на сайте http://www.ghostscript.com.
<references/>
 
[[Категория:Информатика]] [[Категория:Журнал «Потенциал»]][[Категория:информатика в журнале «Потенциал»]]
[[Категория:Журнал «Потенциал»]]
[[Категория:Информатика в журнале «Потенциал»]]
234

правки