Решение: Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — вычесть 1, B — вычесть 2, C — найти целую часть от деления на 3. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 19 результатом является число 3, при этом траектория вычислений не содержит чисел 9 и 16? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Решение по шагам
5 шаговПусть $f(n)$ — количество допустимых программ, переводящих число $n$ в число 3. Базовое значение: из числа 3 можно завершить программу без выполнения команд.
$$f(3)=1$$Для каждого числа $n$ учитываем три последние команды: A переводит в $n-1$, B — в $n-2$, C — в $\lfloor n/3\rfloor$.
$$f(n)=f(n-1)+f(n-2)+f(\lfloor n/3\rfloor)$$Числа 9 и 16 запрещены в траектории, поэтому количество программ, попадающих в них, принимаем равным нулю. Последовательно получаем: $f(4)=1$, $f(5)=2$, $f(6)=3$, $f(7)=5$, $f(8)=8$.
Продолжая вычисления с учётом запретных чисел, получаем $f(10)=9$, $f(11)=10$, $f(12)=20$, $f(13)=31$, $f(14)=52$, $f(15)=85$.
Для чисел 17–19 имеем: $f(17)=87$, $f(18)=90$, $f(19)=90+87+f(6)=90+87+3=180$.
$$f(19)=f(18)+f(17)+f(6)=90+87+3=180$$Где здесь ошибаются
Не исключают переходы через числа 9 и 16.
Забывают, что команда C переводит число в целую часть от деления на 3.
Считают последовательности чисел вместо последовательностей команд.