Question

3. Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Разделить на 2 2. Вычесть 1 Первая команда уменьшает число на экране в 2 раза, вторая — уменьшает его на 1. Программа для исполнителя — это последовательность команд. Определите количество программ, которые число 64 преобразуют в чис ло 14.

Answer 1

Всего будет 8 программ:

Answer 2

Для решения этой задачи можно использовать динамическое программирование. Создадим массив, где каждый элемент будет представлять количество способов преобразовать число i в число 14 с помощью заданных команд. Начнем с числа 14 и будем двигаться в обратном направлении к числу 64, заполняя массив на каждом шаге.

Исходно у нас есть только один способ преобразовать число 14 в число 14, и это оставить его без изменений.

Далее, для числа 15 есть два способа: мы можем либо умножить 14 на 2 (команда "Разделить на 2"), либо вычесть 1 (команда "Вычесть 1"). Таким образом, dp[15] = dp[14] + dp[7].

Продолжая этот процесс в обратном направлении, мы заполним массив dp для числа 64.

Вот Python-код, который решает эту задачу:

pythonCopy code
def count_programs_to_transform(start, target):
    dp = [0] * (target + 1)
    dp[start] = 1

    for i in range(start + 1, target + 1):
        if i % 2 == 0:
            dp[i] += dp[i // 2]
        dp[i] += dp[i - 1]

    return dp[target]

start_number = 64
target_number = 14
result = count_programs_to_transform(start_number, target_number)
print(result)

При запуске этого кода получим количество программ, которые преобразуют число 64 в число 14 с заданными командами.