Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды: $A$ — прибавить 1, $B$ — прибавить 3, $C$ — умножить на 3. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 18, при этом траектория вычислений не содержит числа 9 и не содержит числа 15? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $CBA$ при исходном числе 7 траектория будет состоять из чисел 21, 24, 25.
Шешімін қадамдап көрсету
4 қадамОбозначим через $f(n)$ количество программ, переводящих число 3 в число $n$ без прохождения через 9 и 15. Для разрешённого числа способы попасть в него приходят из $n-1$ командой $A$, из $n-3$ командой $B$, а также из $n/3$ командой $C$, если $n$ кратно 3.
$$f(n)=f(n-1)+f(n-3)+f(n/3)$$Для запрещённых чисел устанавливаем $f(9)=0$ и $f(15)=0$. Начальное значение: $f(3)=1$.
Последовательный расчёт даёт: $f(4)=1$, $f(5)=1$, $f(6)=2$, $f(7)=3$, $f(8)=4$, $f(10)=3$, $f(11)=7$, $f(12)=8$, $f(13)=11$, $f(14)=18$, $f(16)=11$, $f(17)=29$.
Для числа 18 учитываем переходы из 17, 15 и 6. Переход из 15 запрещён, поэтому его вклад равен нулю.
$$f(18)=f(17)+f(15)+f(6)=29+0+2=31$$Где здесь ошибаются
Учитывают программы, проходящие через 9 или 15.
Забывают переход к 18 командой умножения на 3 из числа 6.
Считают начальное число 3 частью траектории.