Рекурсия и траектории программы

Содержание и основные понятия

В ЕГЭ №23 команда переводит число между состояниями. Число программ до состояния можно считать рекурсией с мемоизацией или динамикой.
суть и практика
11 класс
ОГЭ №6/16
ЕГЭ №16/17/23–27
01
Как это устроено
Задача на траектории описывает состояния и команды перехода. Количество способов попасть в состояние равно сумме количеств способов попасть в допустимые предшественники.
Состояние.
Число или другая достаточная характеристика текущей позиции.
База.
У старта есть один пустой путь.
Переход.
Каждая команда добавляет пути из одного предшественника.
Запрет.
Недопустимое состояние имеет ноль путей и не передаёт пути дальше.
02
Один пример в исполнении
Запусти короткую программу и переходи по строкам. Визуализатор показывает только код, текущую строку, переменные и вывод.
Для команд +1 и *2 удобно считать таблицу от старта к цели: у чётного value есть предшественники value - 1 и value // 2, у нечётного — только value - 1. Если путь обязан пройти через точку, часто считают два независимых отрезка и перемножают количества. Направление переходов нужно выписать до программы, иначе легко сложить пути не из тех состояний.
Карта алгоритма
Читай слева направо, затем запускай код.
1
Начало
2
Задать ways[1]
3
Взять следующее состояние
4
Сложить пути предшественников
5
Сохранить ways[value]
03
Запомнить
Проверь start == target: ответ обычно равен 1.
Определи, разрешено ли forbidden совпадать со стартом или целью.
Не рассчитывай запрещённую точку, а затем используй её как предшественника.
Синтаксис этой страницы
dict.get(key, 0)
Возвращает число путей из предшественника или 0, если он недостижим.
range(start + 1, target + 1)
Проходит состояния в возрастающем порядке, когда все предшественники уже посчитаны.
%
Проверяет, существует ли обратный переход через деление на 2.
+=
Прибавляет пути от дополнительного предшественника.
if
Исключает запрещённое состояние или добавляет условный переход.
print
Выводит число путей к цели.