Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды, обозначенные латинскими буквами: A — прибавить 1; B — прибавить 3; C — умножить на 3. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений содержит число 16 и не содержит 12? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 7 траектория состоит из чисел 21, 24, 25.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений содержит число 16 и не содержит 12? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 7 траектория состоит из чисел 21, 24, 25. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Разбейте программу на две части: путь от 2 до 16 и путь от 16 до 20. При подсчёте первой части исключите все пути, проходящие через 12.
2Наводящая — какие числа считатьуровень 2 из 3
Пусть $f(n)$ — число способов получить $n$ из 2. Тогда учитываются переходы из $n-1$, $n-3$ и, если $n$ кратно 3, из $n/3$.
3Прямая — фактически решениеуровень 3 из 3
Число путей из 2 в 16 без прохождения через 12 равно $60$, а число путей из 16 в 20 равно $3$. Перемножьте эти значения.