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