23.05 Количество программ из A в B смешанное
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 19 результатом является 2, при этом траектория вычислений не содержит числа 7 и содержит 13?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы СBА при исходном числе 22 траектория состоит из чисел 7, 3, 2.
Идея решения:
Определим функцию f(a, b), которая считает количество программ, преобразующих число a в b. Функция возвращает:
- 0, если a < b или если в процессе встречается запрещённое число 7;
- 1, если a == b;
- сумму значений для трёх возможных переходов (вычитание 1, вычитание 4, целая часть от деления на 3), если a > b.
Так как нужно, чтобы траектория содержала число 13, но не содержала число 7, то общее количество программ равно произведению f(19, 13) и f(13, 2). Первая часть считает количество способов дойти от 19 до 13, вторая — от 13 до 2.
Решение:
# Функция считает количество программ преобразования a -> b def f(a, b): # Если число меньше целевого или равно запрещённому 7 if a < b or a == 7: return 0 # Если дошли до целевого числа if a == b: return 1 # Считаем все возможные переходы return f(a - 1, b) + f(a - 4, b) + f(a // 3, b) # Условие: траектория проходит через 13 print(f(19, 13) * f(13, 2))
