Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды: 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$.