Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:

$\text{A. Вычти 3}$

$\text{B. Вычти 8}$

$\text{C. Найди целую часть от деления на 2}$

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе $76$ результатом является число $12$ , и при этом траектория вычислений содержит число $41$ и не содержит $73$ ?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе $29$ траектория состоит из чисел $14, 6, 3$ .

Question

Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:

$\text{A. Вычти 3}$

$\text{B. Вычти 8}$

$\text{C. Найди целую часть от деления на 2}$

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе $76$ результатом является число $12$ , и при этом траектория вычислений содержит число $41$ и не содержит $73$ ?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе $29$ траектория состоит из чисел $14, 6, 3$ .

Решение:

Решение на Python:

def F(start, end):
    if start == 73:
        return 0
    if start == end:
        return 1
    if start < end:
        return 0

    return F(start - 3, end) + F(start - 8, end) + F(start // 2, end)

print(F(76, 41) * F(41, 12))

Ответ: 80

Ответ:

80

Accepted Answer

80