Задание №16. Короткий конспект
Сокращение разностей и отношений, выбор базы, подсчёт шагов и сохранение точности при работе с рекурсивными функциями.
Сначала определяется нужное выражение и направление зависимостей. Затем раскрывается только та часть функции, которая не исчезнет при сокращении. База задаёт готовые значения, рекурсивный шаг связывает остальные.
Формулы и ориентиры
n — текущий аргумент; d>0 — целый шаг; a(n) — прибавляемое число; b(n) — множитель.
| Правило | Что остаётся после одного шага |
|---|---|
| F(n)=a(n)+F(n-d) | F(n)-F(n-d)=a(n) |
| F(n)=b(n)F(n-d) | F(n)/F(n-d)=b(n), если знаменатель ненулевой |
Формулы применяются только в области рекурсивного шага. Несколько раскрытий оставляют соответственно сумму слагаемых или произведение множителей. В дроби общий множитель сначала выносится из всего числителя.
Если цепочка от n до m идёт вниз через d, число переходов равно k=(n-m)/d. Это целое число только для аргументов одной цепочки. Прибавление константы c на каждом шаге даёт F(n)=F(m)+kc.
Порядок решения
- Выделяются база, знак границы, шаг и направление изменения аргумента.
- Для каждого нужного значения выписываются первые переходы. Проверяется, могут ли цепочки встретиться.
- В разности раскрытие идёт до общего остатка; в отношении — до общего ненулевого множителя. Если общего участка нет, цепочки считаются отдельно.
- После сокращения выполняется арифметика. Проверяются число переходов, конечные аргументы и требование к ответу: значение или целая часть.
Для программного расчёта таблица заполняется от известных значений к зависимым. Ссылка на меньший аргумент обычно требует возрастающего порядка, на больший — убывающего. Кеширование не устраняет глубину рекурсии.
Возможные ловушки
- Шаг принят за единицу. В EGE-16-0003 ↗ аргументы идут 3220\to3215\to3210. Соседние целые не входят в раскрытие; множители берутся при фактических аргументах.
- База подставлена одинаково. В EGE-16-0024 ↗ чётная цепочка заканчивается на 2026, нечётная — на 2025. Их замена одной точкой меняет ответ; проверяются шаг и условие остановки.
- Аргумент перепутан со значением. В EGE-16-0002 ↗ остановка на 9 означает G(9)=18. К числу шагов прибавляется базовое значение, а не сам аргумент.
- Частное округлено слишком рано. В EGE-16-0001 ↗ дробная часть промежуточного частного влияет на итог. Сначала нужно точное сокращение. В Python
//заменяет точное деление лишь при делимости без остатка;/может терять точность на больших целых.