Подсчёт программ исполнителя
Исполнитель преобразует число на экране. Он умеет выполнять команды: $A$ — прибавить 1, $B$ — прибавить 3, $C$ — умножить на 3. Сколько существует программ, которые при исходном числе 3 получают число 20, при этом траектория вычислений содержит число 14 и не содержит число 15? Траектория вычислений — последовательность результатов выполнения всех команд программы.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 20, при этом траектория вычислений содержит число 14 и не содержит 15? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 21, 24, 25. | |||
| |
Формат: өлшем бірліктері жоқ сан немесе сөз; бөлшек бөлігін үтірмен бөліңіз.
1Мягкая — с чего смотретьдеңгей 1 из 3
Разбейте программу на две части: путь от 3 до 14 и путь от 14 до 20.
2Жетекші — қандай сандарды есептеудеңгей 2 из 3
Для подсчёта числа путей используйте рекуррентное соотношение: количество путей в число $n$ равно сумме количеств путей в числа $n-1$, $n-3$ и $n/3$, если соответствующий переход возможен.
3Тікелей — іс жүзінде шешімдеңгей 3 из 3
Число путей из 3 в 14 равно 46. Из 14 в 20 без прохождения через 15 существует 2 пути, поэтому общее количество программ равно $46 \cdot 2$.