Подсчёт траекторий исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: A — вычти 2; B — найди целую часть от деления на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 38 результатом является число 2, и при этом траектория вычислений содержит число 16? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 2 B. Найди целую часть от деления на 2 Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 38 результатом является число 2, и при этом траектория вычислений содержит число 16? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2. | |||
| |
Формат: өлшем бірліктері жоқ сан немесе сөз; бөлшек бөлігін үтірмен бөліңіз.
1Мягкая — с чего смотретьдеңгей 1 из 3
Разбейте программу в момент первого достижения числа 16: отдельно посчитайте пути из 38 в 16 и из 16 в 2.
2Жетекші — қандай сандарды есептеудеңгей 2 из 3
Для числа $n$ число подходящих программ можно находить рекуррентно: количество путей из $n$ равно сумме количеств путей после команд A и B.
3Тікелей — іс жүзінде шешімдеңгей 3 из 3
Из 38 в 16 существует 3 программы, а из 16 в 2 — 12 программ. Перемножьте эти количества: $3 \cdot 12 = 36$.