Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера.
1. Прибавь 1.
2. Сделай нечётное.
Первая из этих команд увеличивает число x на экране
Используем метод динамического программирования. Заведем массив dp, где dp[i] — количество способов получить
База динамики:
dp[1] = 1.
Формула перехода:
Но при этом если
dp[25] = dp[24] + dp[12], а так как dp[24] не считаем, то ответ совпадает с dp[12].
Посчитаем dp[13] (далее будет приведены значения в ячейках dp
Ответ: 10.
Приведём другое решение на языке Python.
def f(x, y):
if x > y or x == 24:
return 0
if x == y:
return 1
else:
return f(x + 1, y) + f(x * 2 + 1, y)
print(f(1,25))

