Подсчёт программ исполнителя
Исполнитель преобразует число на экране. Он умеет выполнять команды: прибавить 1, умножить на 2 и умножить на 3. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является 39 и при этом траектория вычислений не содержит числа 14? Траектория вычислений программы — это последовательность результатов выполнения всех команд. Например, для программы $ABC$ при исходном числе 7 траектория состоит из чисел 8, 16, 48.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Умножить на 2 C. Умножить на 3 Программа для исполнителя это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является 39 и при этом траектория вычислений не содержит числа 14? Траектория вычислений программы это последовательность результатов выполнения всех команд программы. Например, для программы ABC при исходном числе 7 траектория состоит из чисел 8, 16, 48. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Рассматривайте количество способов получить каждое число из предыдущих чисел.
2Наводящая — какие числа считатьуровень 2 из 3
Для числа $n$ возможны последние команды: прибавление 1 из $n-1$, умножение на 2 из $n/2$ и умножение на 3 из $n/3$.
3Прямая — фактически решениеуровень 3 из 3
Вычислите значения динамически, положив $f(14)=0$: $f(n)=f(n-1)+f(n/2)+f(n/3)$ для целых делений, а затем найдите $f(39)$.