Программы с траекторией через 9
Исполнитель преобразует число на экране. Команда 1 уменьшает число на 1, команда 2 заменяет число на целую часть от деления числа на 2. Сколько существует программ, для которых при исходном числе 30 результатом является число 1, а траектория вычислений содержит число 9? Траектория вычислений программы — последовательность результатов выполнения всех команд.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Вычти 1 2. Найди целую часть от деления на 2
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2.
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 30 результатом является число 1, и при этом траектория вычислений содержит число 9? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Разбейте программу на две части: от 30 до 9 и от 9 до 1.
2Наводящая — какие числа считатьуровень 2 из 3
Для подсчёта числа программ используйте рекуррентное соотношение: количество путей в число $n$ равно сумме количеств путей в числа $n-1$ и $\left\lfloor n/2 \right\rfloor$.
3Прямая — фактически решениеуровень 3 из 3
Число программ от 30 до 9 равно $14$, а от 9 до 1 — $23$. Перемножьте эти количества.