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