Исполнитель преобразует число на экране. У исполнителя есть три команды, обозначенные латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3
Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 23 результатом является 3, при этом траектория вычислений не содержит числа 5 и содержит 11?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы (исходное число в неё не входит).
В ответе запишите целое число.
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3
Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 23 результатом является 3, при этом траектория вычислений не содержит числа 5 и содержит 11?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы (исходное число в неё не входит).
В ответе запишите целое число.
Подсказка 1. Все команды уменьшают число, поэтому особых циклов нет: стройте таблицу числа программ «снизу вверх» от цели к исходному числу.
Подсказка 2. Для каждого числа запишите, из каких чисел можно к нему прийти одной командой, и просуммируйте варианты, отметив ограничения по траектории.
Подсказка 3. Ограничения: число 5 нельзя получать никогда, а число 11 должно встретиться хотя бы раз в траектории — ведите две колонки («встретилось 11» и «не встретилось»).
Разбор.
Приём — динамическое программирование (подсчёт программ). Идём от цели 3 вверх к 23: для каждого числа считаем количество программ, ведущих в цель, с учётом запрета 5 и обязательного появления 11 (две колонки состояний: «11 уже встречалось» / «ещё нет»). Числа меньше цели исключаются — из них в цель уже не попасть. В результате получаем 156 программ.
Ответ: 156.
Ответ.
156