Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — вычесть 1; B — вычесть 4; C — найти целую часть от деления на 3. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 19 результатом является число 2, при этом траектория вычислений не содержит числа 9 и содержит 15? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 22 траектория состоит из чисел 7, 3, 2.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A. Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 19 результатом является число 2, при этом траектория вычислений не содержит числа 9 и содержит 15? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы СBА при исходном числе 22 траектория состоит из чисел 7, 3, 2. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Рассматривайте каждое промежуточное число как состояние. Исключайте переходы, приводящие к числу 9, и отдельно учитывайте, было ли достигнуто число 15.
2Наводящая — какие числа считатьуровень 2 из 3
Для подсчёта используйте динамическое программирование по состояниям $(n, f)$, где $n$ — текущее число, а $f$ показывает, встречалось ли уже число 15.
3Прямая — фактически решениеуровень 3 из 3
Переберите допустимые переходы из 19 до 2 командами A, B и C, не добавляя траектории с числом 9. Сумма для состояний, заканчивающихся в 2 и содержащих 15, равна 70.