EGEsoll - сборник решений задач из ЕГЭ

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

1. Прибавь 1.

2. Сделай нечётное.

Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x + 1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ — это последовательность команд.

Сколько существует таких программ, которые число 1 преобразуют в число 27, причём траектория вычислений не содержит число 26? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.

Добавлено: 05.04.26 15:18

Перейти к решению

def f(s, e):
    if s == e:
        return 1
    if s > e or s == 26:
        return 0
    return f(s + 1, e) + f(2 * s + 1, e)


print(f(1, 27))  # 13