Кратко о задачах...
Функция Аккермана: определяется рекурсивно для целых чисел m и
n следующим образом:
Может показаться неочевидным, что рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение m, или значение m сохраняется, но уменьшается значение n. Это означает, что каждый раз пара (m; n) уменьшается с точки зрения лексикографического порядка, значит, значение m в итоге достигнет нуля: для одного значение m существует конечное число возможных значений n (так как первый вызов с данным m был произведён с каким-то определённым значением n, а в дальнейшем, если значение m сохраняется, значение n может только уменьшаться), а количество возможных значений m, в свою очередь, тоже конечно. Однако, при уменьшении m значение, на которое увеличивается n, неограничено и обычно очень велико.
Золотые горки: На рисунке показан пример треугольника из чисел. Написать программу, вычисляющую наибольшую сумму чисел, через которые проходит путь, начинающийся на вершине и заканчивающийся где-то на основании.
Пусть число a(i,j) есть число в треугольнике, находящееся в i-й строчке на j-м месте, а число (i,j) есть максимальное значение суммы, которое можно получить спускаясь с горки, начиная с этого элемента. Понятно, что (i,j) есть число a(i,j) плюс максимум из двух вариантов: (i + 1,j) и (i + 1,j + 1). Эти два варианта соответствуют тому, что мы можем спуститься вниз-вправо или вниз-влево. Получилось рекурсивное определение: S(i,j) = a(i; j) + max(S(i+1 ; j), S(i+1 ; j+1))