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