Задание №16. Рекурсивные функции: когда перебор не влезает
Что от тебя хотят
Функция F задана по правилам: «если n больше миллиона, то F(n) = n, иначе F(n) = 3n + F(5n)». Просят значение для конкретного n или количество чисел из огромного диапазона, для которых что-то выполняется. Тут два пути, и важно понять, какой нужен.
Путь 1: рекурсия с кэшем
Если надо просто вычислить F(2026) или близкое к нему, пиши функцию прямо по условию и подвесь на неё @lru_cache(None), чтобы она не пересчитывала одно и то же. Для глубокой рекурсии добавь sys.setrecursionlimit(100000).
lru_cache рекурсия зависает. Если функция вызывает саму себя дважды (например, F(n-1) + F(n-2)), число вызовов растёт как степень, и программа не закончит работу.
Путь 2: огромный диапазон
Если надо проверить 400 миллионов чисел, перебирать их все бессмысленно, это минуты. Смотри, от чего на самом деле зависит ответ. Обычно это либо остаток по маленькому модулю, либо число шагов рекурсии.
Разбор 1: число шагов
F(n) = n при n > 1 000 000; F(n) = 3n + F(5n) при n ≤ 1 000 000. G(n) = F(n) / n. Сколько существует натуральных n (включая n = 3000), для которых G(n) = G(3000)?
- Каждое применение правила умножает аргумент на 5, пока он не станет больше миллиона. Пусть k это число таких шагов.
- Значение G(n) полностью определяется числом k: для k шагов оно растёт вместе с k. Значит G(n) = G(3000) тогда и только тогда, когда у n столько же шагов.
- Для 3000 шагов k = 4: 3000 → 15 000 → 75 000 → 375 000 → 1 875 000.
- Остаётся посчитать, у скольких n ровно 4 шага. Первое окно делает это циклом по n до миллиона.
Ответ: 6400. То же получается рассуждением: n должны удовлетворять 1600 < n ≤ 8000.
Разбор 2: остатки вместо перебора
F(0) = 0, F(n) = F(n − 1) + 5n. Найдите количество чисел n от 189 456 678 до 567 654 321, для которых F(n) не делится на 7.
- Раскрываем: F(n) = 5 · (1 + 2 + ... + n) = 5n(n + 1) / 2.
- Делится ли это число на 7, зависит только от остатка n при делении на 7, потому что 7 простое и множители 5 и 2 на 7 не влияют.
- Для каждого остатка 0, 1, ..., 6 проверяем, делится ли F на 7, например, на числе 700 + остаток. Подходят остатки 1, 2, 3, 4, 5.
- Остаётся посчитать, сколько чисел в диапазоне имеют каждый нужный остаток. Это арифметическая прогрессия с шагом 7.
Ответ: 270141174. Второе окно считает это за мгновение.
Разновидности и прототипы задания на экзамене
Код решения на Python
Запустить код в онлайн-песочницеn = 3000
steps_3000 = 0
while n <= 1000000:
n = n * 5
steps_3000 += 1
count = 0
for start in range(1, 1000001):
n = start
steps = 0
while n <= 1000000:
n = n * 5
steps += 1
if steps == steps_3000:
count += 1
print(count)a = 189456678
b = 567654321
total = 0
for r in range(7):
n = 700 + r
if 5 * n * (n + 1) // 2 % 7 != 0:
first = a + (r - a) % 7
total += (b - first) // 7 + 1
print(total)Типичные ошибки
F(n-1) + F(n-2) программа зависнет.@lru_cache(None) на каждую рекурсивную функцию.ГРОБ №16: Значение функции огромное
Значение F(n) состоит из тысяч знаков, и кажется, что его не удержать в памяти и не использовать.
Лайфхаки на экзамене
- Для глубокой рекурсии заранее вызови
sys.setrecursionlimit(100000), иначе Python остановит её около тысячи вызовов. - Когда значение функции растёт огромным, не пытайся его печатать целиком: нужны остатки, делимость или длина записи.
- Если функция заполняет таблицу по возрастанию, можно обойтись без рекурсии: простой цикл с массивом работает быстрее.