Подсчёт программ Вычислителя
Исполнитель Вычислитель преобразует число на экране. У него есть две команды: «Прибавить 1» и «Умножить на 2». Программа для Вычислителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 30, траектория вычислений содержит число 14 и не содержит число 25? Траектория вычислений программы — это последовательность результатов выполнения всех команд.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для Вычислителя это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 30 и при этом траектория вычислений содержит число 14 и не содержит числа 25? Траектория вычислений программы это последовательность результатов выполнения всех команд программы. Например, для программы 121 | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Разбейте программу на две части: путь от 2 до 14 и путь от 14 до 30.
2Наводящая — какие числа считатьуровень 2 из 3
Для подсчёта числа путей используйте рекуррентное соотношение: количество путей в число $n$ равно сумме количества путей в числа $n-1$ и $n/2$, если $n$ чётно.
3Прямая — фактически решениеуровень 3 из 3
От 2 до 14 существует 13 программ. Из 14 в 30 без посещения 25 можно попасть двумя способами: последовательно прибавляя 1 или командами $1, 2, 1, 1$ — то есть $14 \to 15 \to 30$ и $14 \to 28 \to 29 \to 30$. Всего $13 \cdot 2 = 26$.