Рекуррентные выражения, обработка числовых последовательностей

Зачем на экзамене

Рекуррентная формула определяет новое значение через уже известные, а задача на последовательность требует проверить один и тот же критерий для многих чисел. Эти приемы связаны с заданиями 16 и 17. В обоих случаях важны порядок вычислений, точная граница диапазона и проверяемые промежуточные результаты.

Что нужно уметь

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

База

Рекуррентное определение

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

Например, последовательность может быть задана так:

Чтобы найти F(4), сначала нужны F(2) и F(3). При одном предыдущем значении удобно построить таблицу от базы до нужного аргумента. Если формула обращается к F(n - 1) и F(n - 2), нужно хранить два последних результата.

Ветвление и несколько вызовов

Правило может зависеть от четности аргумента, остатка от деления или диапазона. Перед подстановкой выбери ровно ту ветку, условие которой выполнено. После рекурсивного вызова выражение может содержать дополнительные действия, например умножение или сложение.

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

Отдельно следи за командами вывода. Если функция печатает число до или после рекурсивного вызова, порядок строк зависит от места команды. Значение, которое функция возвращает, и текст, который она выводит, являются разными результатами.

Числовая последовательность

В задаче на последовательность сначала определяется объект проверки: отдельный элемент, соседняя пара, тройка или другая группа. Пара соседних элементов с индексами i и i + 1 существует для i от 0 до n - 2. Последний элемент не начинает новую пару.

Условие часто содержит несколько частей: знак числа, делимость, количество цифр, остаток, сравнение с порогом. Переведи каждую часть отдельно, затем соедини их точным логическим оператором.

Проверка последней цифры должна учитывать знак: обычно берут последнюю цифру модуля числа. Делимость на d проверяют равенством остатка нулю. Ноль делится на любое ненулевое целое число.

Количество и экстремум

Если нужно вывести количество подходящих пар и максимальную сумму, эти величины обновляют только при выполнении условия. Счетчик начинается с 0. Максимум нельзя бездумно начинать с 0, потому что все допустимые суммы могут быть отрицательными.

Безопасный подход: первое подходящее значение сделать текущим максимумом, а следующие сравнивать с ним. Если подходящих объектов нет, поведение должно соответствовать условию задачи. Не придумывай числовой ответ вместо явно заданного правила.

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

Как решать

Рекуррентная функция

1. Выпиши все базовые случаи и условия ветвей.
2. Проверь, какие меньшие аргументы нужны для искомого значения.
3. Построй таблицу значений от базы вверх.
4. Для каждого аргумента сначала выбери ветку, затем подставь уже найденные значения.
5. Если есть вывод на экран, отдельно запиши момент вывода относительно рекурсивного вызова.
6. Подставь результат обратно в исходное правило и проверь последнюю операцию.

Обработка последовательности

1. Прочитай все числа и уточни, какие группы считаются: соседние пары, все пары или тройки.
2. Если нужен общий порог, найди его отдельным проходом.
3. Перебирай только существующие группы без выхода за границу.
4. Вычисли логические признаки каждого элемента и соедини их по условию.
5. При успехе увеличь счетчик и обнови требуемый максимум или минимум.
6. Проверь первую и последнюю группы вручную, а также случай отсутствия подходящих данных.

Частые ошибки

• Ошибка: подставлять рекуррентную формулу в базовом случае. Как избежать: сначала проверяй условие остановки.
• Ошибка: выбирать ветку по значению функции вместо аргумента. Как избежать: подпиши, к какой переменной относится каждое условие.
• Ошибка: повторно вычислять одни и те же вызовы. Как избежать: веди таблицу уже найденных значений.
• Ошибка: считать все сочетания вместо соседних пар. Как избежать: формируй пару только из элементов i и i + 1, если так сказано в условии.
• Ошибка: понимать "ровно один" как "хотя бы один". Как избежать: проверь, что логические признаки элементов различаются.
• Ошибка: начинать максимум с 0 при отрицательных данных. Как избежать: инициализируй экстремум первым подходящим результатом.

Проверь себя

1. Чему равно F(3), если F(1) = 2, а F(n) = F(n - 1) + n?
2. Сколько соседних пар содержит последовательность из 8 элементов?
3. Подходит ли пара 6 и 9 условию "ровно одно число делится на 3"?
4. Почему максимум подходящих сумм нельзя всегда начинать с 0?

Ответы: 1) 7; 2) 7; 3) нет, оба числа делятся на 3; 4) все подходящие суммы могут быть отрицательными.

Связь с заданиями

В задании 16 требуется вычислить рекуррентно заданную функцию или восстановить порядок действий и вывода. Задание 17 связано с обработкой числовой последовательности: проверкой элементов, соседних пар или других групп по составному условию. Для обоих номеров полезно разделять вычисление признаков и обновление итогового ответа.