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

 

Можно заметить, что в любом месте горы начинается гора меньшего размера, будем называть такие горы ''горками''. Пусть число a(i,j) есть число в треугольнике, находящееся в i-й строчке на j-м месте, а число (i,j) есть максимальное значение суммы, которое можно получить спускаясь с горки, начиная с этого элемента. Понятно, что (i,j) есть число a(i,j) плюс максимум из двух вариантов: (i+1,j) и (i+1,j+1). Эти два варианта соответствуют тому, что мы можем спуститься вниз-вправо или вниз-влево. Получилось рекурсивное определение: <math>S(i,j)=a(i,j)+\max(S(i+1,j),\;S(i+1, j+1)).</math> На основе этой рекуррентной формулы можно написать рекурсивный алгоритм. Но нужно быть осторожным. Попробуем вычислить время работы нашего алгоритма при входных данных максимального размера&nbsp;— 100 строк. Рекурсивный алгоритм вычисления функции <math>(.,.)</math> перебирает все возможные пути. Сколько их? На каждом шаге есть возможность выбрать один вариант из двух (направо или налево). Количество шагов равно количеству строк треугольника. Значит, количество всех путей равно {Ref|1}{Покажите, что число путей из вершины до j-го элемента i-й строчки равно биномиальному коэффициенту <math>C_i^j</math>. <math>2^{100}</math>. Это очень большое число. Столько вариантов не успеет перебрать даже самая мощная вычислительная техника. Если предположить, что машина просматривает миллиард вариантов в секунду, то понадобится <math>2^{100} / 10^9</math> секунд. Чтобы считать было удобнее, заметим, что <math>2^{100} / 10^9 = 16^{25} / 10^9</math> > <math>10^{25} / 10^9 = 10^{16}</math>&nbsp;секунд, что соответствует более, чем <math>10^{12}</math> часов, или более <math>10\,000\,000</math>&nbsp;лет. Понятно, что такая программа никому не нужна, её результаты узнать невозможно. За такое время все компьютеры, решающие эту задачу, превратятся в пыль.

 

На рисунке обозначены две горки (треугольники): одна с вершиной в числе&nbsp;3, другая с вершиной в числе&nbsp;8. Эти горки пересекаются, и их пересечение тоже горка с вершиной в числе&nbsp;1. Можно заметить, что при вычислении самого лучшего пути по рекурсивному алгоритму горка с вершиной в числе&nbsp;1 будет использоваться дважды. Для горок с вершинами в нижних строчках повторных вызовов будет ещё больше. Это и есть причина медленности работы алгоритма.