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