Задание 16 ЕГЭ: рекурсия с большим шагом

Рекурсия с большим шагом: отношение значений функции. Тема номера — рекурсивные функции. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:

F(n) = 7 при n < 10;
F(n) = (n − 1) × F(n − 5), если n ≥ 10.

Чему равно значение выражения (F(270915) / 222 + F(270910) / 744) / F(270900)?

Решение

Значения F огромны, а рекурсия глубиной в десятки тысяч вызовов в Python падает. Но F(n) = (n − 1)·F(n − 5), поэтому F(270915) / F(270900) — произведение трёх множителей: 270914·270909·270904, а F(270910) / F(270900) = 270909·270904. Остаётся 270914·270909·270904 / 222 + 270909·270904 / 744.

def ratio(top, bottom):      # F(top) / F(bottom), top − bottom кратно шагу
    r = 1
    for n in range(top, bottom, -5):
        r *= n + -1
    return r

print(ratio(270915, 270900) // 222 + ratio(270910, 270900) // 744)

Ответ: 89560766804751.

Решить такую задачу — новый вариант с проверкой