Задание №16. Рекурсивные функции и сокращение вычислений

В задании функция определяется через её значения при других аргументах. Требуется найти отдельное значение, разность или отношение нескольких значений. Большие числа в аргументах не всегда означают длинный расчёт: часто достаточно раскрыть несколько звеньев, после чего общая часть сокращается. Поэтому сначала рассматривается всё искомое выражение, затем выбирается, какие значения действительно нужно вычислить.

Как читать определение функции

Запись F(n) означает значение функции при аргументе n. Если справа встречается та же функция, определение является рекурсивным. Условия рядом с формулами определяют, какое правило действует на каждом шаге.

Например, в EGE-16-0004 ↗ заданы два правила:

Первое правило называют базой, второе задаёт шаг рекурсии. Для аргумента 10 ещё действует второе правило: F(10)=9+F(9)=18. Только при аргументе 9 цепочка доходит до базы. Граница нужна даже тогда, когда в решении удаётся сократить функцию раньше.

Разность: остановка на общем значении

В этом же задании требуется F(8567)-F(8563). Если выразить первое значение через второе, неизвестная общая часть исчезнет. Подстановка n=8567 даёт F(8567)=8566+F(8566): и свободное слагаемое, и аргумент функции уменьшаются на единицу относительно подставленного числа.

Следующие подстановки продолжают эту цепочку. На каждом шаге раскрывается только оставшаяся функция:

После четырёх переходов появляется именно то значение, которое вычитается в условии:

F(8567)=8566+8565+8564+8563+F(8563).

Вычитание F(8563) убирает общий остаток. Ответ равен 8566+8565+8564+8563=34258. Слагаемых четыре, потому что разность аргументов 8567-8563=4, а шаг равен единице. Раскрывать F(8563) до базы уже не требуется: оно присутствует с противоположными знаками.

При другом шаге меняется и число переходов. В EGE-16-0005 ↗ правило F(n)=n^2+F(n-9) соединяет аргументы 5101,5092,5083,5074. До общего значения нужны три перехода, поэтому остаются три квадрата, а не двадцать семь слагаемых.

Отношение: выделение общего множителя

Когда рекурсивный шаг содержит умножение, общая часть сокращается после вынесения множителя. В EGE-16-0009 ↗ заданы F(1)=1 и F(n)=(n-1)F(n-1) при n>1. Требуется:

\frac{F(2024)-3F(2023)}{F(2022)}.

Знаменатель подсказывает удобную точку остановки. Сначала F(2024)=2023F(2023), поэтому числитель равен (2023-3)F(2023)=2020F(2023). Затем ещё один шаг даёт F(2023)=2022F(2022). Теперь вся дробь принимает вид:

\frac{2020\cdot2022\cdot F(2022)}{F(2022)}=2020\cdot2022=4084440.

Сокращение законно: база положительна, все последующие множители положительны, значит F(2022)\ne0. Само огромное значение функции не понадобилось. Коэффициенты взяты из правила n-1; подмена его на n изменила бы оба множителя и ответ.

Тот же приём работает при шаге больше единицы. В EGE-16-0003 ↗ правило F(n)=(n-2)F(n-5) даёт F(3220)=3218F(3215) и F(3215)=3213F(3210). Поэтому выражение [F(3220)-2F(3215)]/F(3210) равно (3218-2)\cdot3213=10333008. Требуемая целая часть совпадает с этим числом: после сокращения дробной части нет.

Если аргумент растёт

Рекурсия может идти к большим аргументам, если база находится справа. В EGE-16-0024 ↗ задано F(n)=n при n\ge2025, а для меньших аргументов F(n)=n+F(n+2). Требуется F(2022)-F(2023).

Шаг через два сохраняет чётность. Из чётного аргумента нечётный не получится, поэтому две цепочки не встретятся:

Последнее число каждой суммы является значением базы. Чётная цепочка перескакивает через границу и останавливается при 2026; это разрешено условием n\ge2025. Ответ: 6072-4048=2024. Сокращать последние значения между собой нельзя: F(2026) и F(2025) различны.

Если заданы две функции

Сначала нужно понять, какие значения второй функции входят в первую. В EGE-16-0002 ↗ требуется F(15548), где:

F(n)=2(G(n-3)+8); G(n)=2n при n<10; G(n)=G(n-2)+1 при n\ge10.

Подстановка в первую формулу даёт F(15548)=2(G(15545)+8). У второй функции аргумент уменьшается на два: 15545\to15543\to\ldots\to9. Цепочка нечётная, поэтому первым аргументом ниже десяти будет 9, а базовое значение равно G(9)=18.

Пусть k обозначает число переходов. После них аргумент равен 15545-2k=9, откуда k=(15545-9)/2=7768. Каждый переход добавляет единицу к базовому значению, поэтому G(15545)=18+7768=7786. Возврат в первую формулу завершает расчёт: F(15548)=2(7786+8)=15588.

Если в первой формуле несколько значений второй функции, каждому нужна своя цепочка. Так, в EGE-16-0006 ↗ значение F(26728)=2G(26728)+G(26727) зависит от чётного и нечётного аргументов. Для правила G(n)=n при n\le10 и G(n)=G(n-2)+1 при n>10 они доходят соответственно до 10 и 9. Получаются G(26728)=10+13359=13369 и G(26727)=9+13359=13368; итог равен 2\cdot13369+13368=40106.

Когда полезна программа

Если общего остатка нет или требуется много отдельных значений, удобно заполнить таблицу. При зависимости от меньших аргументов расчёт идёт от базы вверх; при зависимости от больших аргументов — от базы вниз. Такой способ не создаёт длинную цепочку вложенных вызовов. Устройство таблицы и отличие вычисления значения от вывода программы объясняются в статье «Рекурсия и рекуррентные соотношения».

В архивных условиях встречаются небольшие значения с ветвлением по чётности, подсчёт звёздочек и восстановление порядка печати. Для них важны все выполненные вызовы и место команды вывода. Они требуют отдельного чтения алгоритма; правило сокращения одинаковых значений не заменяет такой разбор.

Возможные ловушки

• Лишнее раскрытие в разности. В EGE-16-0004 ↗ после появления F(8563) раскрытие заканчивается. Прибавление ещё одного слагаемого без одновременного раскрытия вычитаемой функции нарушит равенство. Проверка: четыре перехода должны оставить четыре слагаемых.
• Сокращение похожих, но разных значений. В EGE-16-0024 ↗ соседние аргументы попадают в разные цепочки. Объявление их базовых значений одинаковыми меняет разность. До сокращения должны совпасть и имя функции, и её аргумент.
• Подмена базы её границей. В EGE-16-0002 ↗ число 10 ещё не относится к базе, а нечётная цепочка заканчивается на 9. Подстановка G(10)=20 использует не то правило. Остановка определяется одновременно шагом и знаком неравенства.
• Округление до завершения сокращения. В EGE-16-0001 ↗ после раскрытия остаётся (247566/519-477)\cdot247563. Частное внутри скобок не целое; преждевременное округление уничтожит небольшую разность. Точное преобразование даёт (3/519)\cdot247563=1431. В Python операция / для больших целых может потерять точность; целочисленное // заменяет точное деление только после проверки делимости.