16 номер. Рекурсия
Вычисление рекурсивной функции
(М. Попков) Алгоритм вычисления функций F(n) и G(n) задан следующими соотношениями:
F(n)=G(n)=1 при n=3
F(n)=5× F(n-1)+6× G(n-1)-3n+8 при n>3
G(n)=6× F(n-1)+5× G(n-1)+3 при n>3
Определите число, которое получится, если в обе функции передать аргумент n=9 и сложить получившиеся значения.
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Решение
Искомая величина: Определите число, которое получится, если в обе функции передать аргумент n=9 и сложить получившиеся значения.
Выпишите базовые значения и границы каждой ветви. Для конкретного аргумента сначала выберите применимое условие, затем подставляйте рекуррентную формулу этой ветви; базовый случай имеет приоритет перед дальнейшим раскрытием.
Если переходы используют меньшие аргументы, заполняйте значения по возрастанию от базовой области. При повторных обращениях используйте сохранённый результат: это позволяет избежать многократного обхода одних и тех же ветвей рекурсии.
Значения F и G храните раздельно. При взаимных вызовах состоянием является и имя функции, и аргумент: F(n) и G(n) не взаимозаменяемы. Вложенный аргумент сначала вычисляется, затем передаётся внешнему вызову.
После получения нужных значений подставьте их именно в выражение из вопроса, сохранив коэффициенты, знаки и скобки. Значение одной функции может быть лишь промежуточной величиной, а не окончательным ответом.
Ответ: 3312821.