Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A — прибавить 1, B — прибавить 2, C — умножить на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 17, при этом траектория вычислений содержит число 9 и не содержит 12? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 14, 16, 17.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 17, при этом траектория вычислений содержит число 9 и не содержит 12? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 14, 16, 17. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Разбейте программу в точке, когда впервые получено число 9. Сколько способов ведёт от 2 к 9 и сколько — от 9 к 17 без числа 12?
2Наводящая — какие числа считатьуровень 2 из 3
Для подсчёта числа программ используйте рекуррентное соотношение: число способов попасть в $n$ равно сумме способов попасть в $n-1$, $n-2$ и $n/2$, если $n$ чётно.
3Прямая — фактически решениеуровень 3 из 3
Получается $N_{2\to9}=35$, а число способов пройти от 9 до 17, не попадая в 12, равно 10. Перемножьте эти количества.