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

3 байта убрано ,  13 лет назад
Эту задачу можно встретить и под названием «Золотая гора» — нужно спуститься с горы и собрать как можно больше золота.
 
Можно заметить, что в любом месте горы начинается гора меньшего размера, будем называть такие горы ''горками''. Пусть число 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> перебирает все возможные пути. Сколько их? На каждом шаге есть возможность выбрать один вариант из двух (направо или налево). Количество шагов равно количеству строк треугольника. Значит, количество всех путей равно <math>2^{Ref|1100}{</math>(Покажите, что число путей из вершины до 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 будет использоваться дважды. Для горок с вершинами в нижних строчках повторных вызовов будет ещё больше. Это и есть причина медленности работы алгоритма.
 
Решить эту задачу за разумное время помогает '''динамическое программирование'''. Суть динамического программирования хорошо описана в книге Р.&nbsp;Беллмана&nbsp;{{Ref|Bell}}. Есть и более современные учебники&nbsp;{{Ref|2}},{{Ref|3}}, в них можно найти много интересных алгоритмов, основанных на динамическом программировании.
 
Общая идея динамического программирования заключается в том, что мы рассматриваем вместо одной задачи целое семейство задач. Это семейство задач у нас будет таким: найти наилучший путь из вершины (i,j). Для каждой пары i,j получим одну задачу. При i=1 и j=1 получается исходная задача, которую нам нужно решить. '''Начнём решать эти задачи с простых: сначала для нижней строчки, затем второй снизу и так далее, пока не дойдём до самой верхней строчки треугольника'''.
1224

правки