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