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