Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: вычесть 1 и найти целую часть от деления на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 30 результатом является число 1 и при этом траектория вычислений содержит число 12? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ABB при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 1 B. Найди целую часть от деления на 2 Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 30 результатом является число 1 и при этом траектория вычислений содержит число 12? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABB при исходном числе 10 траектория состоит из чисел 9, 4, 2. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Разбейте программу в момент первого получения числа 12: сначала посчитайте пути из 30 в 12, затем — из 12 в 1.
2Наводящая — какие числа считатьуровень 2 из 3
Для подсчёта количества программ используйте рекуррентную формулу: $f(n)=f(n-1)+f(\lfloor n/2\rfloor)$.
3Прямая — фактически решениеуровень 3 из 3
Из 30 в 12 существует 8 программ, а из 12 в 1 — 47 программ. Общее количество равно $8\cdot47=376$.