Question

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

1. Вычти 2

2. Найди целую часть от деления на 2

Первая из них уменьшает число на экране на 2, вторая заменяет число на экране на целую часть от деления числа на 2. Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 28 результатом является число 1, и при этом траектория вычислений содержит число 10?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например, для программы 122 при исходном числе 13 траектория состоит из чисел 11, 5, 2.

Answer 1

def count_programs(start, target):

   table = [[0] * (target + 1) for _ in range(start + 1)]

   table[start][target] = 1

   for i in range(start, 0, -1):

       for j in range(target, 0, -1):

           if i - 2 >= 0:

               table[i - 2][j] += table[i][j]

           if i % 2 == 0:

               table[i // 2][j] += table[i][j]

   return table[1][1]

start_number = 28

target_number = 1

count = count_programs(start_number, target_number)

print("Количество программ:", count)