Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. Команда A увеличивает число на 1. Команда B применяется только к числу, у которого цифра в разряде десятков меньше цифры в разряде единиц, и меняет местами цифры двух младших разрядов. Сколько существует программ, которые при исходном числе 100 получают результат 150?
Решение по шагам
4 шагаРассмотрим числа как вершины графа. Из каждой вершины проводим переход по команде A к числу, увеличенному на 1.
Переход по команде B добавляем только тогда, когда цифра десятков меньше цифры единиц; при этом две младшие цифры меняются местами.
Для каждой достижимой вершины вычисляем число программ, приводящих из 100 в это число. Число способов попасть в вершину равно сумме способов попасть в неё из всех предшествующих вершин.
После заполнения таблицы динамического подсчёта для числа 150 получаем количество программ, равное 35.
Где здесь ошибаются
Разрешают команду B при неверном условии для цифр десятков и единиц.
Считают одинаковые траектории одной программой, хотя программы могут отличаться последовательностью команд.
Забывают учитывать переходы по команде B, которые могут уменьшать число.