Задание №23 — Поиск количества программ

#69243Задание №23ФИПИ

Анализ алгоритмов и исполнители

Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
1) Прибавить 1
2) Умножить на 2
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 35, при этом траектория вычислений содержит число 10 и не содержит 17? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABA при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Правильный ответ

Пояснение

Решение:

Названия команд (цифры или буквы) на подсчёт не влияют: из $x$ можно попасть в $x+1$ или в $2x$ . Пусть $R(x)$ — число программ, переводящих $x$ в конечное число. Тогда $R(x)=R(x+1)+R(2x),$ $R(\text{конечного числа})=1$ , $R(x)=0$ при $x$ , большем конечного числа, и $R(17)=0$ , потому что 17 запрещено (числа только растут, так что запрет достаточно поставить один раз).

Траектория обязана содержать 10, поэтому задача распадается на две части: $1\to 10$ и $10\to 35$ ; ответ — произведение.

1) Из 1 в 10. Все числа траектории здесь не превосходят 10, так что запрет на 17 не работает:

$x$	10	9	8	7	6	5	4	3	2	1
$R(x)$	1	1	1	1	1	2	3	4	7	14

Получаем 14 программ.

2) Из 10 в 35 без числа 17. Для $x\ge 18$ удвоение даёт больше 35, поэтому $R(x)=1$ при $x=18,\dots,35$ . Далее $R(17)=0$ (запрещено) и считаем вниз:

$x$	18	17	16	15	14	13	12	11	10
$R(x)$	1	0	1	2	3	4	5	6	7

Здесь, например, $R(16)=R(17)+R(32)=0+1=1$ , $R(15)=R(16)+R(30)=1+1=2$ , и так далее до $R(10)=R(11)+R(20)=6+1=7$ .

Итого $14\cdot 7=98$ .

from functools import lru_cache

def count(start, finish, forbidden):
    @lru_cache(None)
    def R(x):
        if x > finish or x in forbidden:
            return 0
        if x == finish:
            return 1
        return R(x + 1) + R(2 * x)
    return R(start)

print(count(1, 10, ()) * count(10, 35, (17,)))

Ответ: 98