16 номер. Рекурсия
Отношение значений рекурсивной функции
(О. Лысенков) Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(1) = 3
F(n) = 5 * F(n-1), если n > 1
Найдите значение выражения (f({10}^{12}+10)) / ({25}^{5 · 10 ^ {11}}), при его записи в десятеричной системе счисления.
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Решение
Перебор в данном случае не принесёт результата, поэтому будем анализировать работу функции. Рассмотрим на примере f(5)
f(5) = 5 * f(4), f(4) = 5 * f(3), f(3) = 5 * f(2), f(2) = 5 * f(1)
f(2) = 5 * 3 = 15, f(3) = 5 * 15 = 75, f(4) = 5 * 75 = 375, F(5) = 5 * 375 = 1875
То есть f(n) = 3 * 5 ^{n-1}.
Тогда, f({10}^{12} + 10) = 3 * {5}^{10^{12} + 10 -1} = 3 * {5}^{10^{12} + 9}
В таком случае (f({10}^{12}+ 10)) / ({25}^{ 5 · {10}^{11}}) = (3*{5}^{10^{12}+9}) / (5^{{10}^{12}})=3 * {5}^{{10}^{12} + 9 - {10}^{12}} = 3 * {5} ^{9} = 5859375