ЕГЭ · ЗАДАНИЕ 16
Рекурсивные алгоритмы · №31513
Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n × F(n - 1), если n > 1.
Чему равно значение выражения (F(3038) + 5 × F(3037)) / F(3036)?
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 9241591
1. Узнаем факториал
По определению F(n) = n!, но вычислять факториал 3038 не требуется. Выразим числитель через общий множитель F(3036).
2. Сократим общий множитель
F(3038) = 3038 × 3037 × F(3036).
F(3037) = 3037 × F(3036).
После деления на F(3036) остаётся 3038 × 3037 + 5 × 3037 = 3037 × 3043 = 9 241 591.
3. Проверим коротким кодом
print(3037 * (3038 + 5)) # 9241591Такой расчёт точный, не требует рекурсии и огромных промежуточных чисел. Если считать факториалы напрямую, можно упереться в ограничение глубины рекурсии или потерять точность при делении через float.