16 номер. Рекурсия
Вычисление рекурсивной функции
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = 3· F(n-1) - F(n-2) при n>1
Чему равно значение функции F(6)? В ответе запишите только целое число.
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Решение
Начните с F(0) = 1 и F(1) = 1. Для n от 2 до 6 сохраняйте два предыдущих значения a = F(n−2), b = F(n−1); следующее равно 3b−a. После шага пара обновляется одновременно: a, b = b, 3b−a. После шага n = 6 в b находится искомое значение.
Ответ: 89.