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