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

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

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

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

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

Пояснение

Решение:

Обозначим через $R(x)$ количество программ, переводящих число $x$ в заданное конечное число. Из $x$ исполнитель может перейти либо в $x+1$ (команда 1), либо в $2x$ (команда 2), поэтому $R(x)=R(x+1)+R(2x),$ причём $R(\text{конечного числа})=1$ (пустая программа), а если $x$ уже больше конечного числа, то $R(x)=0$ — числа только растут.

Траектория обязана содержать 10, а 10 лежит между 1 и 20, поэтому каждая подходящая программа однозначно распадается на две независимые части: сначала $1\to 10$ , потом $10\to 20$ . По правилу произведения общее количество равно произведению количеств.

1) Из 1 в 10. Считаем $R$ от 10 вниз к 1 (удвоение из $x\ge 6$ сразу перескакивает через 10, поэтому там остаётся только «прибавить 1»):

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

Например, $R(5)=R(6)+R(10)=1+1=2$ , $R(2)=R(3)+R(4)=4+3=7$ , $R(1)=R(2)+R(2)=14$ . Итого 14 программ.

2) Из 10 в 20. Для любого $x\ge 11$ удвоение даёт больше 20, значит $R(x)=R(x+1)=1$ для всех $x=11,\dots,20$ . А из 10 можно и прибавлять единицы, и сразу удвоить: $R(10)=R(11)+R(20)=1+1=2$ .

Итого $14\cdot 2=28$ .

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(2 * x)
    return R(start)

print(count(1, 10) * count(10, 20))

Ответ: 28