Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n × F(n − 1), если n > 1.
Чему равно значение выражения (F(3038) + 5 × F(3037)) / F(3036)?
Ответ:
Демонстрационный вариант ЕГЭ 2027 по информатике – задание №16
Решение:
Решение —
Функция задана рекуррентно:
F(1) = 1
F(n) = n · F(n − 1), если n > 1.
Это обычный факториал:
F(n) = n!
Можно вычислить значение с помощью программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
from functools import * @lru_cache(None) def f(n): if n == 1: return 1 if n > 1: return n * f(n - 1) for i in range(1, 3100): f(i) print((f(3038) + 5 * f(3037)) / f(3036)) |
Но выражение удобно упростить и без вычисления огромных факториалов.
Так как
F(3038) = 3038 · 3037 · F(3036)
и
F(3037) = 3037 · F(3036),
то:
(F(3038) + 5 · F(3037)) / F(3036)
= (3038 · 3037 · F(3036) + 5 · 3037 · F(3036)) / F(3036)
Сокращаем на F(3036):
3038 · 3037 + 5 · 3037
Выносим 3037 за скобки:
3037 · (3038 + 5) = 3037 · 3043
3037 · 3043 = 9 241 591
Ответ: 9241591