Question

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

Answer 1

d = [0] * 21

d[1] = 1

for i in range(2, 11):

   d[i] = d[i-1]

   if i % 2 == 0:

       d[i] += d[i // 2]

for i in range(11, 21):

   d[i] = d[i-1]

   if i % 2 == 0 and i // 2 >= 10:

       d[i] += d[i // 2]

print(d[20])

Ответ: 28

Answer 2

Для решения данной задачи можно использовать рекурсивную функцию.

Создадим функцию `count_programs(start, end, trajectory)`, которая будет принимать текущее число `start`, конечное число `end` и текущую траекторию `trajectory`. Функция будет рекурсивно вызывать саму себя, увеличивая `start` на 1 или умножая его на 2, и добавлять результаты в траекторию.

В каждом вызове функции будем проверять, достигли ли мы конечного числа `end`. Если достигли, то проверяем, содержит ли траектория число 10. Если да, то увеличиваем счетчик программ на 1.

В конечном итоге, функция `count_programs(1, 20, [])` вернет количество программ, удовлетворяющих условию задачи.

Пример реализации на языке Python:

def count_programs(start, end, trajectory):
    if start == end:
        if 10 in trajectory:
            return 1
        else:
            return 0
    elif start > end:
        return 0
    else:
        return count_programs(start + 1, end, trajectory + [start]) + count_programs(start * 2, end, trajectory + [start])

result = count_programs(1, 20, [])
print(result)

В данном примере результатом будет количество программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10.