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