Шешімі: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — прибавить 1, B — прибавить 2, C — умножить на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 18, при этом траектория вычислений содержит число 8 и не содержит число 13?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 14, 16, 17.
Шешім по шагам
4 қадамОбозначим через $f(n)$ число программ, переводящих число 3 в число $n$. Для получения $n$ последняя команда может быть прибавлением 1, прибавлением 2 или умножением на 2.
$$f(n)=f(n-1)+f(n-2)+\begin{cases}f(n/2),& n\text{ чётно},\\0,& n\text{ нечётно}. \end{cases}$$Последовательно получаем значения до числа 8: $f(3)=1$, $f(4)=1$, $f(5)=2$, $f(6)=4$, $f(7)=6$, $f(8)=11$. Значит, существует 11 способов попасть из 3 в 8.
Теперь считаем число способов пройти от 8 до 18. Число 13 запрещено, поэтому полагаем $g(13)=0$, где $g(n)$ — число способов попасть из 8 в $n$.
$$g(8)=1,\ g(9)=1,\ g(10)=2,\ g(11)=3,\ g(12)=5,\ g(13)=0,\ g(14)=5,\ g(15)=5,\ g(16)=11,\ g(17)=16,\ g(18)=28$$Любая подходящая программа однозначно состоит из пути от 3 до 8 и пути от 8 до 18, не проходящего через 13.
$$11\cdot28=308$$Где здесь ошибаются
Не учитывать запрет на появление числа 13 в траектории.
Считать только команды прибавления и забывать команду умножения на 2.
Сложить числа способов вместо их умножения при объединении двух частей пути.