Задание 16
Рекуррентные выражения
Функция, заданная через саму себя: значения вручную и программой, @cache и прогрев кеша, сокращение отношений и разностей при больших аргументах, цепочки до базы и перебор n.
6 подтем · 43 задачи + 12 дополнительных · повышенный · ≈ 5 мин
Подтема 1 из 6
Функция, заданная через себя
Что спрашивают в задании 16, как читать определение функции и как посчитать её значение вручную — вниз до базы и обратно.
Как устроена тема
В задании 16 функция задана через саму себя: её значение для n выражается через значения для других аргументов. Нужно найти значение функции или выражения из нескольких её значений. Вот задача, которую мы будем решать всю тему:
«Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n · F(n − 1), если n > 1. Чему равно значение выражения (F(2026) + 3 · F(2025)) / F(2024)?»
Считать F(2026) целиком не придётся: это число из тысяч цифр, и почти всё в нём сократится. Сначала разберём, что сказано в условии:
| В условии | Что это значит |
|---|---|
| F(n) | значение функции для аргумента n — какое-то число |
| n — натуральное число | аргументы 1, 2, 3, … |
| F(n) = 1 при n = 1 | для n = 1 ответ известен сразу |
| F(n) = n · F(n − 1), если n > 1 | остальные значения получают из значения для n − 1 |
| (F(2026) + 3 · F(2025)) / F(2024) | выражение из трёх значений функции — его и нужно найти |
Тема состоит из шести подтем — у каждой своя страница. Идём по ним по порядку:
- Функция, заданная через себя — ты сейчас здесь. Считаем значения вручную на маленьких n.
- Рекурсивная функция на Python — решим задачу темы программой: ответ 4 108 725.
- Повторные вызовы и таблица — что делать, если программа считает слишком долго.
- Раскрыть и сократить — задача темы вручную, без программы.
- Цепочки до базы и перебор n — шаг через несколько чисел, две функции, поиск n.
- Что считает функция — дополнительный урок для редких задач про цифры числа.
Почти любую задачу можно решить и программой, и вручную. На экзамене подойдёт любой способ, а второй пригодится для проверки.
База и шаг
Как посчитать F(5) по такому определению?
Значение для n = 1 известно сразу. Каждое следующее получается из предыдущего по формуле — так шаг за шагом доходим до нужного n. Возьмём функцию задачи темы:
| n | Вычисление | F(n) |
|---|---|---|
| 1 | дано в условии | 1 |
| 2 | 2 · F(1) = 2 · 1 | 2 |
| 3 | 3 · F(2) = 3 · 2 | 6 |
| 4 | 4 · F(3) = 4 · 6 | 24 |
| 5 | 5 · F(4) = 5 · 24 | 120 |
Значение, которое задано сразу, называют базой: здесь это F(1) = 1. Формулу, которая выражает F(n) через другие значения функции, — рекуррентным соотношением: F(n) = n · F(n − 1).
У нашей функции F(n) = 1 · 2 · 3 · … · n. Такое произведение называют факториалом и пишут n!, например 5! = 120.
Скобки после F всегда значат одно: посчитать функцию для того числа, что стоит в скобках. Поэтому похожие записи дают разные числа:
| Запись | Что сделать | При n = 3 |
|---|---|---|
| F(n − 1) | посчитать F для аргумента n − 1 | F(2) = 2 |
| F(n) − 1 | посчитать F(n) и вычесть 1 | 6 − 1 = 5 |
| 2 · F(n) | посчитать F(n) и умножить на 2 | 2 · 6 = 12 |
| F(2n) | посчитать F для аргумента 2n | F(6) = 720 |
Вниз до базы и обратно
А если предыдущих значений ещё нет, а нужно сразу F(5)?
Тогда вычисление сначала спускается до базы, а потом поднимается обратно. F(5) = 5 · F(4), но F(4) неизвестно — F(5) ждёт. F(4) = 4 · F(3) — ждёт и F(4). Так до F(1) = 1. Дальше ждущие вызовы получают ответы и доделывают своё умножение: F(2) = 2, F(3) = 6, F(4) = 24, F(5) = 120. Пройди этот путь по шагам:
- F(5) = 5 · F(4). Значения F(4) ещё нет, поэтому F(5) ждёт и помнит, что потом умножит его на 5.
- F(4) = 4 · F(3). Значения F(3) ещё нет, поэтому F(4) ждёт и помнит, что потом умножит его на 4.
- F(3) = 3 · F(2). Значения F(2) ещё нет, поэтому F(3) ждёт и помнит, что потом умножит его на 3.
- F(2) = 2 · F(1). Значения F(1) ещё нет, поэтому F(2) ждёт и помнит, что потом умножит его на 2.
- F(1) = 1 дано в условии — это база, новых запросов нет.
- F(1) возвращает 1 тому, кто его ждал, — вызову F(2).
- F(2) получил F(1) = 1 и выполнил отложенное действие: 2 · 1 = 2.
- F(3) получил F(2) = 2 и выполнил отложенное действие: 3 · 2 = 6.
- F(4) получил F(3) = 6 и выполнил отложенное действие: 4 · 6 = 24.
- F(5) получил F(4) = 24 и выполнил отложенное действие: 5 · 24 = 120. Ждущих вызовов не осталось — ответ готов.
Заметь порядок: F(1) начался последним, а закончился первым; F(5) начался первым, а закончился последним. Ждущие вызовы хранятся как стопка — что положили последним, то снимают первым. Её называют . У каждого вызова своё n: когда F(5) дождётся F(4) = 24, он умножит его именно на 5.
Ветви по условию
Что делать, если формул несколько и выбор зависит от n? Например:
F(n) = n при n ≤ 2; F(n) = F(n − 1) + n, если n > 2 и n чётно; F(n) = 2 · F(n − 2), если n > 2 и n нечётно.
Формулу выбирают заново для каждого аргумента, который встретился по пути. Найдём F(8):
| Аргумент | Какая формула | Что получается |
|---|---|---|
| 8 | чётное, больше 2 | F(8) = F(7) + 8 |
| 7 | нечётное, больше 2 | F(7) = 2 · F(5) |
| 5 | нечётное, больше 2 | F(5) = 2 · F(3) |
| 3 | нечётное, больше 2 | F(3) = 2 · F(1) |
| 1 | не больше 2 | F(1) = 1 |
Поднимаемся обратно: F(3) = 2, F(5) = 4, F(7) = 8, F(8) = 8 + 8 = 16.
Частая ошибка — выбрать формулу один раз по первому аргументу: 8 чётное, и дальше везде брать F(n − 1) + n. Так получится 35 вместо 16.
База сверху
Аргумент всегда уменьшается?
Нет: база может стоять сверху, и тогда аргумент растёт, пока не дойдёт до неё. Например: F(n) = n при n ≥ 10; F(n) = n + F(n + 1) при n < 10.
F(7) = 7 + F(8) = 7 + 8 + F(9) = 7 + 8 + 9 + F(10). При n = 10 работает база: F(10) = 10. Значит, F(7) = 7 + 8 + 9 + 10 = 34.
Порядок тот же: запросы идут от 7 к базе, результаты возвращаются обратно. Важно одно — чтобы аргументы дошли до базы. Как это проверять, разберём в следующей подтеме.
Итого
- Базазначение, известное сразу: F(1) = 1
- Рекуррентное соотношениеF(n) через другие значения: F(n) = n · F(n − 1)
- СкобкиF(n − 1) — функция от n − 1, F(n) − 1 — значение минус 1
- Вниз и обратнозапросы до базы, потом ждущие вызовы доделывают действия
- Ветвиформулу выбирают для каждого аргумента
- База сверхуаргумент растёт, пока не дойдёт до неё
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Прибавка 2n
F(1) = 3; F(n) = F(n − 1) + 2n при n > 1. Найди F(5).
Введите число.
Подсказка
Начни с базы F(1) = 3 и поднимайся: F(2) = 3 + 2 · 2, потом F(3), F(4), F(5).
Решение
Считаем от базы: F(2) = 3 + 4 = 7, F(3) = 7 + 6 = 13, F(4) = 13 + 8 = 21, F(5) = 21 + 10 = 31. Проверка программой:
def F(n): if n == 1: return 3 return F(n - 1) + 2 * n print(F(5))Ответ: 31
Утроить и вычесть единицу
F(1) = 2; F(n) = 3 · F(n − 1) − 1 при n > 1. Найди F(4).
Введите число.
Подсказка
Каждое следующее значение — утроенное предыдущее минус 1.
Решение
F(2) = 3 · 2 − 1 = 5, F(3) = 3 · 5 − 1 = 14, F(4) = 3 · 14 − 1 = 41.
def F(n): if n == 1: return 2 return 3 * F(n - 1) - 1 print(F(4))Ответ: 41
Скобки после имени функции
Пусть F(n) = 3n − 2. Чему равно F(2 · 3) − 2 · F(3)?
Введите число.
Подсказка
F(2 · 3) — функция от 6, а 2 · F(3) — удвоенное значение функции от 3.
Решение
F(2 · 3) = F(6) = 3 · 6 − 2 = 16. 2 · F(3) = 2 · (3 · 3 − 2) = 2 · 7 = 14. Разность: 16 − 14 = 2.
def F(n): return 3 * n - 2 print(F(2 * 3) - 2 * F(3))Ответ: 2
Два предыдущих значения
F(1) = 2, F(2) = 3; F(n) = F(n − 1) + 2 · F(n − 2) при n > 2. Найди F(6).
Введите число.
Подсказка
Каждому значению нужны два предыдущих — составь таблицу от F(1) до F(6).
Решение
F(3) = 3 + 2 · 2 = 7, F(4) = 7 + 2 · 3 = 13, F(5) = 13 + 2 · 7 = 27, F(6) = 27 + 2 · 13 = 53.
def F(n): if n == 1: return 2 if n == 2: return 3 return F(n - 1) + 2 * F(n - 2) print(F(6))Ответ: 53
Шаг назад на три
F(1) = F(2) = F(3) = 1; F(n) = F(n − 1) + F(n − 3) при n > 3. Найди F(10).
Введите число.
Подсказка
Заполни таблицу от 1 до 10: каждому значению нужны предыдущее и то, что на три назад.
Решение
Значения F(1), …, F(10): 1, 1, 1, 2, 3, 4, 6, 9, 13, 19. Например, F(10) = F(9) + F(7) = 13 + 6 = 19.
def F(n): if n <= 3: return 1 return F(n - 1) + F(n - 3) print(F(10))Ответ: 19
Задача в формате экзамена: F(6)
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = n + 2 при n ≤ 2; F(n) = 2 · F(n − 1) − F(n − 2) + n при n > 2. Чему равно значение функции F(6)?
Введите число.
Подсказка
Спустись от F(6) до баз F(1) и F(2), а потом поднимайся обратно по формуле.
Решение
Базы: F(1) = 3, F(2) = 4. Обратно: F(3) = 2 · 4 − 3 + 3 = 8, F(4) = 2 · 8 − 4 + 4 = 16, F(5) = 2 · 16 − 8 + 5 = 29, F(6) = 2 · 29 − 16 + 6 = 48.
def F(n): if n <= 2: return n + 2 return 2 * F(n - 1) - F(n - 2) + n print(F(6))Ответ: 48
Задача в формате экзамена: F(5)
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(1) = 1; F(n) = F(n − 1) · (n + 1) при n > 1. Чему равно значение функции F(5)?
Введите число.
Подсказка
F(5) ждёт F(4), тот — F(3), и так до базы F(1) = 1. Обратно умножай на n + 1.
Решение
Вниз: F(5) = F(4) · 6, F(4) = F(3) · 5, F(3) = F(2) · 4, F(2) = F(1) · 3. Обратно: F(2) = 3, F(3) = 12, F(4) = 60, F(5) = 360.
def F(n): if n == 1: return 1 return F(n - 1) * (n + 1) print(F(5))Ответ: 360
Ветвь по чётности
F(n) = n при n ≤ 2; F(n) = F(n − 1) + n, если n > 2 и n чётно; F(n) = 2 · F(n − 2), если n > 2 и n нечётно. Найди F(12).
Введите число.
Подсказка
У каждого аргумента по пути заново смотри на чётность: 12, потом 11, потом 9, …
Решение
12 чётное: F(12) = F(11) + 12. Дальше только нечётные: F(11) = 2 · F(9), F(9) = 2 · F(7), …, F(3) = 2 · F(1) = 2. Обратно: F(5) = 4, F(7) = 8, F(9) = 16, F(11) = 32, F(12) = 32 + 12 = 44.
def F(n): if n <= 2: return n elif n % 2 == 0: return F(n - 1) + n else: return 2 * F(n - 2) print(F(12))Ответ: 44
Ветвь для каждого вызова
F(1) = 5; F(n) = F(n − 1) − 2, если n чётно; F(n) = F(n − 1) + 3n, если n > 1 и n нечётно. Найди F(6).
Введите число.
Подсказка
Чётность проверяй у аргумента каждого шага, а не только у 6.
Решение
F(2) = 5 − 2 = 3, F(3) = 3 + 9 = 12, F(4) = 12 − 2 = 10, F(5) = 10 + 15 = 25, F(6) = 25 − 2 = 23.
def F(n): if n == 1: return 5 elif n % 2 == 0: return F(n - 1) - 2 else: return F(n - 1) + 3 * n print(F(6))Ответ: 23
Задача в формате экзамена: F(14)
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n чётно; F(n) = 3 · F(n − 2), если n > 1 и при этом n нечётно. Чему равно значение функции F(14)?
Введите число.
Подсказка
14 чётное — F(14) = 14 + F(13). Дальше нечётные аргументы идут через один до 1.
Решение
F(14) = 14 + F(13). Для нечётных F(n) = 3 · F(n − 2): аргументы 13, 11, 9, 7, 5, 3, 1 — шесть переходов, F(13) = 3⁶ · F(1) = 729. Значит, F(14) = 14 + 729 = 743.
def F(n): if n == 1: return 1 elif n % 2 == 0: return n + F(n - 1) else: return 3 * F(n - 2) print(F(14))Ответ: 743
База сверху
F(n) = n при n ≥ 20; F(n) = F(n + 3) + 2 при n < 20. Найди F(4).
Введите число.
Подсказка
Аргумент растёт на 3, пока не станет не меньше 20. На каком числе это случится?
Решение
Аргументы 4, 7, 10, 13, 16, 19, 22: шесть переходов по +2 и база F(22) = 22 — число 20 в цепочку не попадает. F(4) = 22 + 6 · 2 = 34.
def F(n): if n >= 20: return n return F(n + 3) + 2 print(F(4))Ответ: 34
Вверх с вычитанием
F(n) = n при n > 30; F(n) = F(n + 4) − 1 при n ≤ 30. Найди F(17).
Введите число.
Подсказка
База — первое число цепочки 17, 21, 25, …, которое больше 30.
Решение
Аргументы 17, 21, 25, 29, 33: четыре перехода по −1 и база F(33) = 33. F(17) = 33 − 4 = 29.
def F(n): if n > 30: return n return F(n + 4) - 1 print(F(17))Ответ: 29