Задание 16 · Рекуррентные выражения
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — (F(2026) + 3 · F(2025)) / F(2024) для F(n) = n · F(n − 1) — прошла через подтемы, и каждая решала её новым способом. Пролистай версии: точками отмечены строки, которых не было в предыдущей.
- Подтема 1, «Функция через себя»: база и шаг: от базы вверх. Точками отмечены новые строки.
- Подтема 2, «Функция на Python»: определение как есть.
- Подтема 3, «Повторы и таблица»: таблица значений циклом от базы.
- Подтема 4, «Раскрыть и сократить»: без программы: общий множитель. Ответ задачи темы — 4 108 725.
Три способа — рекурсия, таблица и сокращение — дали одно число и проверяют друг друга. Подтема 5 добавляет цепочки с шагом больше единицы и поиск n, а дополнительный урок — функции, которые что-то считают, например сумму цифр.
Карта темы
Каждая подтема дала один приём, и любое решение собирается из них. Сверху — путь от определения к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Правилабаза, шаг, ветви
- Способпрограмма или раскрыть и сократить
- Ответзначение, выражение или n
1Функция, заданная через себя
- базазначение, известное сразу
- F(n − 1)значение для аргумента n − 1, не F(n) − 1
- ветвивыбирают в каждом вызове
2Рекурсивная функция на Python
return n * F(n - 1)определение как естьsys.setrecursionlimitдля аргументов в тысячи//деление нацело — ответ целым числом
3Повторные вызовы и таблица
@cacheкаждое значение считается один раз- таблицаf[n] = F(n) циклом от базы
4Раскрыть и сократить
- отношениераскрыть до общего множителя
- разностьостаются прибавки
5Цепочки до базы и перебор n
- шаг kсвоя цепочка и свой конец по остатку
- поиск nперебор со счётчиком или while
6Что считает функциядополнительный урок
F(n // b) + n % bсумма цифр в системе b
Как решать
Любое задание 16 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Частые ошибки
Восемь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- F(n) − 1
- вместо F(n − 1) посчитали F(n) − 1 → скобки после F — аргумент. Спроси себя: что стоит в скобках?подтема 1
- одна ветвь
- ветвь выбрали один раз по первому аргументу → ветвь — в каждом вызове. Спроси себя: какой аргумент у этого вызова?подтема 1
- n == 1 в базе
if n == 1→if n <= 1. Спроси себя: база в условии — равенство или неравенство?подтема 2- RecursionError
- F(2026) без поднятого предела → sys.setrecursionlimit или прогрев кеша. Спроси себя: сколько вызовов в цепочке до базы?подтема 2
- 4108725.0
… / F(2024)→… // F(2024). Спроси себя: ответ должен быть целым?подтема 2- считает минуты
- функция с двумя вызовами себя без кеша → @cache над функцией. Спроси себя: не считается ли одно значение много раз?подтема 3
- IndexError
f = [0] * 2026→f = [0] * 2027. Спроси себя: есть ли в списке элемент f[2026]?подтема 3- конец цепочки
- цепочку с шагом 3 довели до той же базы → конец зависит от остатка — пройти цепочку. Спроси себя: в какое число упрётся эта цепочка?подтема 5
Итог
Тема пройдена: задача темы решена тремя способами — ответ 4 108 725. Вот что взять с собой.
- ПорядокПравила, способ, программа или сокращение, проверка.
- ПрограммаОпределение как есть, // и предел глубины.
- Скорость@cache, прогрев или таблица циклом от базы.
- СокращениеРаскрыть до общего множителя или прибавок.
- Задача темы(2026 + 3) · 2025 = 4 108 725.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Для функции задачи темы найди F(2026) / F(2024).
ОтветСкрыть ответ
2026 · 2025 = 4 102 650: F(2024) сокращается.
Почему программа с вызовами F(n − 1) и F(n − 2) считает F(40) долго?
ОтветСкрыть ответ
Одни и те же значения считаются снова и снова — вызовов экспоненциально много. @cache считает каждое один раз.
Функцию с @cache сразу вызвали для n = 10 000 — и получили RecursionError. Что сделать?
ОтветСкрыть ответ
Поднять предел глубины или прогреть кеш: вызвать F(n) по очереди от маленьких n, тогда каждый вызов уходит вглубь на один шаг.
F(n) = F(n − 3) + 2 при n > 3, F(n) = n при n ≤ 3. Чему равно F(10)?
ОтветСкрыть ответ
Цепочка 10 → 7 → 4 → 1: F(1) = 1, плюс три прибавки по 2 — F(10) = 7.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Ветвь для каждого вызова: F(21)
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 2 при n = 1; F(n) = F(n − 1) + n, если n чётно; F(n) = 2 · F(n − 2) + n, если n > 1 и при этом n нечётно. Чему равно значение функции F(21)?
Введите число.
Подсказка
Ветвь выбирай для каждого аргумента: нечётные берут F(n − 2), чётные — F(n − 1).
Решение
Нечётные n > 1 берут F(n − 2), чётные — F(n − 1). Значения от F(1): 2, 4, 7, 11, 19, 25, 45, … Программа выбирает ветвь в каждом вызове:
def F(n): if n == 1: return 2 elif n % 2 == 0: return F(n - 1) + n else: return 2 * F(n - 2) + n print(F(21))Ответ: 7143
Общий множитель
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = (n − 1) · F(n − 1), если n > 1. Чему равно значение выражения (F(2027) + 4 · F(2026)) / F(2025)?
Введите число.
Подсказка
Множитель здесь n − 1: F(2027) = 2026 · F(2026), F(2026) = 2025 · F(2025).
Решение
Числитель: 2026 · F(2026) + 4 · F(2026) = 2030 · F(2026) = 2030 · 2025 · F(2025). После сокращения на F(2025): 2030 · 2025 = 4 110 750.
import sys sys.setrecursionlimit(5000) def F(n): if n == 1: return 1 return (n - 1) * F(n - 1) print((F(2027) + 4 * F(2026)) // F(2025))Ответ: 4110750
Разность при шаге 3
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = n при n < 7; F(n) = n + 2 + F(n − 3), если n ≥ 7. Чему равно значение выражения F(4000) − F(3991)?
Введите число.
Подсказка
Раскрой F(4000) шагами по 3 до F(3991).
Решение
F(4000) = 4002 + F(3997) = 4002 + 3999 + F(3994) = 4002 + 3999 + 3996 + F(3991). Разность: 4002 + 3999 + 3996 = 11 997.
import sys sys.setrecursionlimit(5000) def F(n): if n < 7: return n return n + 2 + F(n - 3) print(F(4000) - F(3991))Ответ: 11997
Первое n с F(n) = 9
Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями: F(0) = 0; F(n) = F(n / 3), если n > 0 и n делится на 3; F(n) = (n mod 3) + F(n − (n mod 3)), если n не делится на 3. Назови минимальное значение n, для которого F(n) = 9.
Введите число.
Подсказка
Перебирай n по возрастанию до первого совпадения.
Решение
Функция считает сумму цифр троичной записи. Перебор по возрастанию останавливается на 161 = 12222₃: 1 + 2 + 2 + 2 + 2 = 9.
def F(n): if n == 0: return 0 elif n % 3 == 0: return F(n // 3) else: return n % 3 + F(n - n % 3) n = 1while F(n) != 9: n += 1print(n)Ответ: 161
Две функции и точное деление
Алгоритм вычисления значений функций F(n) и G(n), где n — целое число, задан следующими соотношениями: F(n) = F(n − 3) + 7, если n ≥ 15; F(n) = 4 · (G(n + 2) − 3), если n < 15; G(n) = n / 4, если n ≥ 50; G(n) = G(n + 5) + 3, если n < 50. Чему равно значение функции F(100)?
Введите число.
Подсказка
F идёт вниз шагами по 3, G — вверх шагами по 5. В базе G дробь — не заменяй / на //.
Решение
F: от 100 до 13 — двадцать девять переходов по 7, это 203. F(13) = 4 · (G(15) − 3). G: 15, 20, …, 50 — семь переходов по 3, G(15) = 50 / 4 + 21 = 33,5. F(13) = 4 · 30,5 = 122, F(100) = 122 + 203 = 325. С // в базе G получилось бы 323.
from fractions import Fraction def G(n): if n >= 50: return Fraction(n, 4) return G(n + 5) + 3 def F(n): if n >= 15: return F(n - 3) + 7 return 4 * (G(n + 2) - 3) print(F(100))Ответ: 325