Question

Программирование Python Напишите программы по примеру:
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?
Решение (теоретическое):
запишем рекуррентную формулу для вычисления – количества возможных программ для получения числа N из некоторого начального числа:
, если N не делится на 2
, если N делится на 2
все допустимые программы можно разбить на 2 части:
– переход от 1 до 10
– переход от 10 до 20

обозначим через количеств возможных программ получения числа b из числа a
очевидно, что если траектория проходит через c, то для любого c, такого что a < c < b
поэтому
вычисляем эти значения отдельно стандартным по рекуррентным формулам и перемножаем: 14 ⋅ 2 = 28
ответ: 28.

Решение (рекурсивная программа, Python):
главная проблема при решении этого задания – высокая вероятность арифметической ошибки, поэтому для проверки (если есть время) можно написать программу, реализующую тот же алгоритм
вычисления по рекуррентным формулам можно организовать с рекурсии
рекурсивная функция, которая возвращает количество программ для преобразования числа start в число x, может быть написана так:
def numProg( start, x ):
if x < start: return 0 # (1)
if x == start: return 1 # (2)
K = numProg( start, x-1 ) # (3)
if x % 2 == 0:
K += numProg( start, x//2 ) # (4)
return K
если число x меньше, чем начальное значение, количество программ равно 0 (строка (1))
если число x равно начальному значению, количество программ равно 1 (строка (2))
в остальных случаях всегда учитываем количество программ предыдущего числа (если последняя команда программы будет +1), см. строку (3)
если число 0078 чётное, нужно добавить ещё и количество программ для числа x//2 (строка (4))
в основной программе вычисляем количество программ от 1 до 10 и умножаем на количество программ от 10 до 20:
print( numProg(1,10)*numProg(10,20) )
ответ: 28.