Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: 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$.