Задание 16 ЕГЭ по информатике: рекурсивные алгоритмы и функции

Что проверяет задание

Задание 16 проверяет умение читать и вычислять рекурсивно заданную функцию $F(n)$, где $n$ — целое число. Функция описывается через базовый случай (значение при малых $n$) и одно или несколько рекуррентных соотношений, которые зависят от чётности, остатка от деления или сравнения с предыдущими значениями. Нужно либо найти конкретное значение $F(N)$ для заданного $N$, либо определить, сколько чисел $n$ из некоторого диапазона обладают заданным свойством результата (например, $F(n)=k$).

За этим заданием стоит проверка трёх связанных навыков: понимание структуры рекурсии (база + переход), умение аккуратно раскрутить цепочку вычислений без ошибок и способность увидеть в рекуррентном определении скрытую закономерность (например, что функция считает количество единиц в двоичной записи числа).

Как выглядит формулировка и сколько баллов

Типичная формулировка: «Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями: $F(0)=...$; $F(n)=...$, если $n>0$ и чётно; $F(n)=...$, если $n$ нечётно. Чему равно значение $F(N)$?» или «Сколько существует таких $n$ в диапазоне $[a;b]$, что $F(n)=k$?»

Задание оценивается 2 баллами. Ответ — целое число, записывается без пояснений и промежуточных вычислений. Частичный балл не предусмотрен: засчитывается только точное совпадение с верным числом. Из-за этого критически важна безошибочность на каждом шаге вычислений, а не только правильная стратегия.

Что нужно знать

• Рекурсия состоит из базового случая (значение функции при конкретном $n$, обычно $n=0$ или $n=1$) и рекуррентного перехода, выражающего $F(n)$ через $F$ от меньшего аргумента.
• Чётность числа определяется остатком от деления на 2: $n \bmod 2 = 0$ — чётное, $n \bmod 2 = 1$ — нечётное.
• Целочисленное деление (обычно обозначается как $n/2$ в условии таких задач) означает $\left\lfloor n/2 \right\rfloor$ — деление с отбрасыванием остатка.
• Глубина рекурсии — количество шагов от $F(n)$ до базового случая. У функций с одним предыдущим значением глубина равна $n$; у функций вида «делим на 2» глубина порядка $\log_2 n$.
• Разложение числа в двоичной системе: любое натуральное число можно представить как сумму степеней двойки, а операция «$n$ чётно — делим на 2, нечётно — вычитаем 1» соответствует последовательному разбору двоичных разрядов.
• Число единичных битов в двоичной записи числа $n$ иногда называют весом Хэмминга или popcount — это стандартная интерпретация ряда рекурсивных функций деления на 2.
• Сумма арифметической прогрессии: $S = \dfrac{(a_1+a_n)\cdot n}{2}$; сумма квадратов первых $n$ натуральных чисел: $\displaystyle\sum_{k=1}^{n} k^2 = \dfrac{n(n+1)(2n+1)}{6}$ — такие формулы помогают проверять результат прикидочно.
• Число сочетаний $C_n^k = \dfrac{n!}{k!(n-k)!}$ применяется, когда нужно посчитать количество чисел с заданным количеством единичных битов в двоичной записи.

Методы решения

1. Табулирование «снизу вверх» (для функций от одного предыдущего значения). Вместо честного рекурсивного спуска строится таблица значений от базового случая до нужного $n$. Это исключает путаницу с порядком вызовов. Пример: если $F(0)=0$, $F(n)=F(n-1)+n$, то последовательно считаем $F(1)=1$, $F(2)=3$, $F(3)=6$ и так далее — получаем треугольные числа.

2. Метод подстановки с накоплением суммы (для функций вида $F(n)=F(n-1)+g(n)$). Если переход всегда прибавляет некоторое выражение $g(n)$, значение $F(n)$ равно сумме базового значения и всех прибавок от начала до $n$. Удобно выписывать цепочку прибавок в столбик и складывать. Пример: $F(n)=F(n-1)+2n$, $F(0)=0$ — тогда $F(n)=2(1+2+\dots+n)=n(n+1)$.

3. Распознавание смысла функции через первые значения (для рекурсий «деление на 2»). Если функция вызывает себя от $n/2$ при чётном $n$ и добавляет 1 при переходе через нечётное значение, стоит вычислить несколько значений вручную и сравнить с известными характеристиками числа (количество единиц в двоичной записи, количество разрядов и т.п.). Пример: $F(0)=0$, $F(n)=F(n/2)$ при чётном $n$, $F(n)=1+F(n-1)$ при нечётном — проверка на малых числах показывает, что $F(n)$ равно количеству единиц в двоичном представлении $n$.

4. Разбор по классам остатков (когда переход зависит от $n \bmod 2$ или $n \bmod 3$). Если рекурсия задаёт разные формулы для чётных и нечётных $n$, полезно отдельно проследить цепочку для нечётных индексов и отдельно для чётных, так как они могут «перескакивать» через два шага одновременно. Пример: $F(n)=2F(n-2)$ при нечётном $n>1$ — эта ветка связывает только нечётные индексы между собой, независимо от чётных.

5. Комбинаторный подсчёт количества чисел с заданным свойством результата. Если функция интерпретируется как количество единиц в двоичной записи, а нужно найти количество $n$ в диапазоне с $F(n)=k$, задача сводится к подсчёту чисел с ровно $k$ единичными битами не превышающих верхнюю границу — используются сочетания $C_m^k$, где $m$ — количество бит. Пример: количество чисел от 1 до 1023 с ровно тремя единичными битами равно $C_{10}^{3}=120$, поскольку 1023 записывается десятью единицами в двоичной системе.

Алгоритм решения по шагам

1. Определить тип задачи: нужно найти конкретное значение $F(N)$ или посчитать количество чисел $n$ с определённым свойством результата.
2. Выписать базовый случай и все ветки перехода, обратив внимание на условия (строгое/нестрогое неравенство, чётность/нечётность).
3. Если рекурсия опирается на одно предыдущее значение — построить таблицу от базового случая вверх до нужного $n$, вычисляя каждое значение по формуле.
4. Если рекурсия использует деление на 2 или пропуск через два шага — распознать закономерность на малых числах (0, 1, 2, ..., 10) и сформулировать общее правило (например, что функция считает количество единиц в двоичной записи или сумму определённых слагаемых).
5. Аккуратно проводить арифметику на каждом шаге, особенно операции целочисленного деления и возведения в степень — ошибка на одном шаге ломает всю цепочку.
6. Для задач «сколько чисел удовлетворяет условию» — свести к комбинаторной формуле или к прямому перечислению, если диапазон невелик, проверив пограничные значения (не выходят ли комбинации за пределы диапазона).
7. Проверить результат прикидочно: сравнить порядок величины полученного числа с ожидаемым (например, для суммы квадратов результат должен расти кубически от $n$).

Разбор примеров

Пример 1

Условие: $F(0)=0$; $F(n)=F(n/2)$, если $n>0$ и чётно; $F(n)=1+F(n-1)$, если $n$ нечётно. Найти количество чисел $n$, $1 \le n \le 1000$, таких что $F(n)=3$.

Шаг 1. Вычислим несколько значений вручную. $F(1)=1+F(0)=1$. $F(2)=F(1)=1$. $F(3)=1+F(2)=2$. $F(4)=F(2)=1$. $F(5)=1+F(4)=2$. $F(6)=F(3)=2$. $F(7)=1+F(6)=3$.

Шаг 2. Заметим закономерность: деление на 2 при чётном $n$ отбрасывает младший нулевой бит, а прибавление 1 при нечётном $n$ соответствует «снятию» единичного бита. Значит $F(n)$ равно количеству единиц в двоичной записи числа $n$ (весу Хэмминга).

Шаг 3. Нужно найти количество чисел от 1 до 1000 с ровно тремя единичными битами. Максимальное число диапазона $1000 = 1111101000_2$ — 10-битное число, значит все числа диапазона представимы не более чем 10 битами.

Шаг 4. Всего чисел с ровно тремя единичными битами среди 10-битных представлений (от 0 до 1023) равно $C_{10}^{3}=120$.

Шаг 5. Проверим, есть ли среди чисел от 1001 до 1023 такие, у которых ровно 3 единицы. Все они начинаются с $111110\ldots$ или более старших единиц (минимум шесть единичных бит в старшей части), поэтому среди них нет чисел с ровно тремя единицами.

Ответ: 120.

Пример 2

Условие: $F(n)=0$ при $n \le 1$; $F(n)=F(n-1)+3n^2$, если $n>1$ и нечётно; $F(n)=\dfrac{n}{2}+F(n-1)+2$, если $n>1$ и чётно. Найти $F(49)$.

Шаг 1. Так как функция опирается только на одно предыдущее значение, применяем табулирование снизу вверх от $F(1)=0$ до $F(49)$.

Шаг 2. Считаем последовательно по формулам, используя чётность каждого индекса: $F(2)=1+F(1)+2=3$; $F(3)=F(2)+27=30$; $F(4)=2+F(3)+2=34$; $F(5)=F(4)+75=109$; $F(6)=3+F(5)+2=114$; $F(7)=F(6)+147=261$; $F(8)=4+F(7)+2=267$; $F(9)=F(8)+243=510$; $F(10)=5+F(9)+2=517$.

Шаг 3. Продолжая таблицу тем же способом (каждое чётное значение прибавляет $n/2+2$, каждое нечётное прибавляет $3n^2$), получаем цепочку: $F(11)=880$, $F(12)=888$, $F(13)=1395$, $F(14)=1404$, $F(15)=2079$, $F(16)=2089$, $F(17)=2956$, $F(18)=2967$, $F(19)=4050$, $F(20)=4062$.

Шаг 4. Далее: $F(21)=5385$, $F(22)=5398$, $F(23)=6985$, $F(24)=6999$, $F(25)=8874$, $F(26)=8889$, $F(27)=11076$, $F(28)=11092$, $F(29)=13615$, $F(30)=13632$.

Шаг 5. Далее: $F(31)=16515$, $F(32)=16533$, $F(33)=19800$, $F(34)=19819$, $F(35)=23494$, $F(36)=23514$, $F(37)=27621$, $F(38)=27642$, $F(39)=32205$, $F(40)=32227$.

Шаг 6. Далее: $F(41)=37270$, $F(42)=37293$, $F(43)=42840$, $F(44)=42864$, $F(45)=48939$, $F(46)=48964$, $F(47)=55591$, $F(48)=55617$.

Шаг 7. Наконец $F(49)=F(48)+3\cdot 49^2 = 55617 + 3\cdot 2401 = 55617+7203=62820$.

Ответ: 62820.

Пример 3

Условие: $F(n)=1$ при $n=1$; $F(n)=n+F(n-1)$, если $n$ чётно; $F(n)=2\cdot F(n-2)$, если $n>1$ и нечётно. Найти $F(26)$.

Шаг 1. $F(26)$ чётно, поэтому $F(26)=26+F(25)$. Требуется значение $F(25)$.

Шаг 2. $F(25)$ нечётно, значит связано только с $F(23)$ через формулу $F(n)=2F(n-2)$. Это означает, что нужно раскрутить цепочку только нечётных индексов от 25 до 1, минуя чётные значения.

Шаг 3. Выписываем цепочку: $F(3)=2F(1)=2\cdot 1=2$; $F(5)=2F(3)=4$; $F(7)=2F(5)=8$; $F(9)=2F(7)=16$; $F(11)=2F(9)=32$; $F(13)=2F(11)=64$; $F(15)=2F(13)=128$; $F(17)=2F(15)=256$; $F(19)=2F(17)=512$; $F(21)=2F(19)=1024$; $F(23)=2F(21)=2048$; $F(25)=2F(23)=4096$.

Шаг 4. Заметим, что цепочка нечётных значений — геометрическая прогрессия со знаменателем 2, что можно было предсказать заранее: $F(2k+1)=2^{k}$ при таком правиле перехода.

Шаг 5. Возвращаемся к исходному значению: $F(26)=26+F(25)=26+4096=4122$.

Ответ: 4122.

Типичные ошибки и ловушки

• Путаница между обычным делением и целочисленным: запись $n/2$ в условии почти всегда означает $\left\lfloor n/2 \right\rfloor$, а не результат с дробной частью.
• Пропуск или неверное применение базового случая — важно проверить, при каком именно $n$ задано базовое значение ($n=0$, $n=1$ или $n \le 1$), иначе цепочка обрывается неправильно.
• Смешивание веток чётных и нечётных индексов при рекурсии вида $F(n)=2F(n-2)$: такая рекурсия связывает только числа одной чётности, попытка идти через $F(n-1)$ приведёт к неверному результату.
• Арифметические ошибки при вычислении квадратов, кубов или сумм на длинной цепочке — рекомендуется вести таблицу с промежуточными значениями, а не считать всё в уме.
• Ошибка при определении диапазона: не учитывать, что верхняя граница диапазона может входить или не входить в интервал, а также забывать проверить пограничные значения при комбинаторном подсчёте.
• Неверная интерпретация результата функции: прежде чем применять комбинаторную формулу (например, для подсчёта чисел с заданным весом Хэмминга), нужно убедиться, что закономерность действительно подтверждается на нескольких малых значениях, а не предполагается без проверки.
• Путаница знаков и коэффициентов при переносе формулы из условия в вычисления — рекомендуется переписывать формулу целиком перед каждым шагом, а не удерживать в памяти.

Как готовиться

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

Стоит отдельно потренироваться в переводе чисел в двоичную систему и обратно, поскольку многие задачи на функции вида «делим на 2, если чётно» сводятся к анализу битового представления числа. Разбор количества единичных битов, длины двоичной записи и связи с сочетаниями $C_n^k$ значительно упрощает решение задач на подсчёт количества чисел с заданным свойством.

Если есть возможность программировать, полезно писать короткие скрипты для проверки собственных ручных вычислений — это помогает быстро находить арифметические ошибки и убедиться в правильности выбранной закономерности перед тем, как записывать окончательный ответ.

Наконец, важно нарабатывать скорость и аккуратность при последовательном табулировании: чем быстрее и без ошибок строится таблица от базового случая до нужного $n$, тем меньше риск потерять баллы на этом задании, которое требует точного числового ответа без права на частичное совпадение.