Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — вычесть 1; B — вычесть 2; C — найти целую часть от деления на 3. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 20 результатом является число 3, при этом траектория вычислений не содержит чисел 13 и 14? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 13 траектория состоит из чисел 4, 2, 1.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A. Вычесть 1 B. Вычесть 2 C. Найти целую часть от деления на 3 Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 20 результатом является число 3, при этом траектория вычислений не содержит чисел 13 и 14? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы СBА при исходном числе 13 траектория состоит из чисел 4, 2, 1. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Обозначьте через $f(n)$ число допустимых программ, переводящих число $n$ в число 3.
2Наводящая — какие числа считатьуровень 2 из 3
Для разрешённых значений $n$ используйте рекуррентное соотношение $f(n)=f(n-1)+f(n-2)+f(\lfloor n/3\rfloor)$. Для чисел 13 и 14 положите $f(13)=f(14)=0$.
3Прямая — фактически решениеуровень 3 из 3
Последовательно вычислите значения от $f(3)=1$ до $f(20)$: $f(15)=2$, $f(16)=4$, $f(17)=8$, $f(18)=15$, $f(19)=26$, $f(20)=44$.