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

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

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

Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A) Прибавить 1
B) Прибавить 2
C) Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 4 в число 15, и при этом траектория вычислений программы содержит числа 11 и 13?Траектория должна содержать оба указанных числа. Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ACB при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.

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

100

Пояснение

Решение:

Из числа $x$ исполнитель попадает в $x+1$ (A), $x+2$ (B) или $2x$ (C). Пусть $R(x)$ — количество программ, переводящих $x$ в заданное конечное число. Тогда $R(x)=R(x+1)+R(x+2)+R(2x),$ $R(\text{конечного числа})=1$ , а $R(x)=0$ , если $x$ больше конечного числа (числа только растут, поэтому «перепрыгнув» цель, вернуться нельзя).

Траектория обязана содержать и 11, и 13, а $4\lt 11\lt 13\lt 15$ , значит программа распадается на три независимые части: $4\to 11$ , $11\to 13$ , $13\to 15$ . Ответ — произведение.

1) Из 4 в 11. Удвоение полезно только из $x=5$ (даёт 10):

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

Например, $R(9)=R(10)+R(11)+R(18)=1+1+0=2$ , $R(5)=R(6)+R(7)+R(10)=8+5+1=14$ , $R(4)=R(5)+R(6)+R(8)=14+8+3=25$ .

2) Из 11 в 13. Удвоение даёт 22 — перелёт, поэтому $R(12)=R(13)=1$ и $R(11)=R(12)+R(13)=1+1=2$ (это программы AA и B).

3) Из 13 в 15. Аналогично $R(13)=2$ (программы AA и B).

Итого $25\cdot 2\cdot 2=100$ .

from functools import lru_cache

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

print(count(4, 11) * count(11, 13) * count(13, 15))

Ответ: 100