Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: A — прибавь 1; B — поменяй местами. Команда A увеличивает число на экране на 1. Команда B применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и заменяет число на экране числом, в котором цифры двух младших разрядов поменялись местами. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 100 результатом является число 141? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42.
Шешім по шагам
3 қадамРассмотрим все допустимые переходы из исходного состояния 100. Команда A увеличивает текущее число на 1, а команда B выполняет перестановку двух последних цифр только при условии, что цифра десятков меньше цифры единиц.
Последовательно перебираем достижимые числа и для каждого числа сохраняем количество программ, которыми оно получено. При переходе по команде A значение увеличивается на 1; при допустимом переходе по команде B добавляется способ перейти к числу с переставленными последними цифрами.
После исключения недопустимых применений команды B и подсчёта всех путей от 100 до 141 количество программ равно 16.
$$N(141)=16$$Где здесь ошибаются
Разрешают команду B для чисел, у которых цифра десятков не меньше цифры единиц.
Считают только различные траектории, не учитывая, что разные последовательности команд могут приводить к одной траектории.
Забывают, что команда A может применяться на каждом шаге.