Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — вычесть 1; B — вычесть 3; C — найти целую часть от деления на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 19 результатом является число 3, при этом траектория вычислений не содержит числа 9 и содержит 12? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 13 траектория состоит из чисел 6, 3, 2.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A. Вычесть 1 B. Вычесть 3 C. Найти целую часть от деления на 2 Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 19 результатом является число 3, при этом траектория вычислений не содержит числа 9 и содержит 12? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 13 траектория состоит из чисел 6, 3, 2. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Разбейте программу на две части: путь от 19 до 12 и путь от 12 до 3.
2Наводящая — какие числа считатьуровень 2 из 3
Используйте динамическое программирование: для каждого числа считайте количество способов попасть в него командами A, B и C, исключая переходы в число 9.
3Прямая — фактически решениеуровень 3 из 3
Заполните таблицу количества путей от 19 до 12 и от 12 до 3, затем перемножьте число способов прохождения через 12. Получается 153.