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

На экзамене

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

Формулы и факты

• Базовый случай останавливает рекурсию и вычисляется без нового вызова.
• Таблицу значений заполняй от меньших аргументов к большим.
• При нескольких одинаковых вызовах сохраняй уже найденное значение.
• Возвращаемое значение функции и напечатанный текст: разные результаты.
• В последовательности из n элементов есть n - 1 соседних пар.
• Последняя цифра отрицательного числа обычно проверяется у его модуля.
• Делимость на d: остаток равен 0; ноль делится на любое ненулевое целое d.

Алгоритм

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

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

Последовательность

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

Ловушки

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