Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: A — прибавь 1; B — поменяй местами. Команда A увеличивает число на экране на 1. Команда B применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и заменяет число на экране числом, в котором цифры двух младших разрядов поменялись местами. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 111 результатом является число 165? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42.
Решение по шагам
4 шагаКаждому числу сопоставим количество программ, которые переводят исходное число 111 в это число. Для числа 111 начальное количество программ равно 1.
Из каждого состояния добавляем переход по команде A: число увеличивается на 1. Также добавляем переход по команде B, если цифра в разряде десятков меньше цифры в разряде единиц; при этом две последние цифры меняются местами.
Последовательно заполняем таблицу количества способов для всех достижимых состояний, не пропуская разные траектории, даже если они приводят к одному и тому же числу.
После обработки всех допустимых переходов количество программ, приводящих из 111 в 165, составляет 89.
Где здесь ошибаются
Учитывают только программы, состоящие из команд A.
Разрешают команду B при невыполнении условия о цифрах десятков и единиц.
Считают различные программы одинаковыми, если они приводят к одному промежуточному числу.
Забывают, что каждая последовательность команд задаёт отдельную траекторию.