Задание 5: Простой линейный алгоритм для формального исполнителя

Типовая формулировка звучит так: у исполнителя (Альфа, Бета, Гамма и т. п.) есть две команды с номерами 1 и 2. Команда 1 — «прибавь $a$» (число $a$ конкретное: 1, 2, 3 и так далее), команда 2 — «умножь на $b$», где $b$ — неизвестное натуральное число, $b \ge 2$. Программа записана как последовательность цифр, например 12111 или 11211. Дано, что при выполнении этой программы конкретное число (например, 6 или 7) переходит в другое конкретное число (например, 82 или 51). Требуется найти значение $b$.

…

• Линейный алгоритм — последовательность команд, которые выполняются одна за другой строго в порядке их записи, без пропусков, повторов и условных переходов.
• Команда «прибавь $a$» переводит число $x$ в число $x+a$: $x \to x+a$.
• Команда «умножь на $b$» переводит число $x$ в число $x \cdot b$: $x \to x \cdot b$.
• Программа записывается как строка цифр-номеров команд; например, запись 11211 означает выполнение команд в порядке: 1, 1, 2, 1, 1.
• Применение программы к числу — это композиция функций: результат каждого шага становится входным значением для следующего шага.
• По условию задачи $b$ — натуральное число и $b \ge 2$ (единица не подходит, так как умножение на 1 не меняет число, что обычно противоречит смыслу задачи).
• После разбора программы получается уравнение вида $k \cdot b + m = N$, где $k$ и $m$ — числа, найденные из последовательности команд, а $N$ — известный конечный результат. Уравнение решается стандартно: $b = \dfrac{N-m}{k}$.
• Обратная операция для «прибавь $a$» — «вычти $a$» ($x \to x-a$), для «умножь на $b$» — «раздели на $b$» ($x \to x/b$); эти обратные операции полезны при движении от конца программы к началу.

1. Выписать, что означает команда 1 и что означает команда 2 (какое число прибавляется, что множитель — неизвестное $b$).
2. Прочитать программу как последовательность цифр и определить порядок выполнения команд слева направо.
3. Взять исходное число и последовательно применять к нему команды, при умножении оставляя буквенный множитель $b$, не пытаясь его сразу вычислить.
4. После прогона всей программы получить итоговое выражение в виде $k\cdot b+m$ (число $k$ показывает, во сколько раз множитель $b$ участвует в итоговом коэффициенте, $m$ — накопленное слагаемое).
5. Составить уравнение: полученное выражение равно заданному конечному числу.
6. Решить уравнение относительно $b$.
7. Проверить, что $b$ — натуральное число и $b\ge2$; если условие не выполняется, пересчитать шаги 3–4, скорее всего, ошибка в порядке команд или в арифметике. …