dict.get(key, 0)Возвращает число путей из предшественника или 0, если он недостижим.
В ЕГЭ №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 совпадать со стартом или целью.
- Не рассчитывай запрещённую точку, а затем используй её как предшественника.
Синтаксис этой страницы
range(start + 1, target + 1)Проходит состояния в возрастающем порядке, когда все предшественники уже посчитаны.
%Проверяет, существует ли обратный переход через деление на 2.
+=Прибавляет пути от дополнительного предшественника.
ifИсключает запрещённое состояние или добавляет условный переход.
printВыводит число путей к цели.