Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера:
1. прибавь 1
2. сделай нечётное
Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ — это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 25, причём траектория вычислений не содержит число 24? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.
Используем метод динамического программирования. Заведем массив dp, где dp[i] — количество способов получить число i с помощью таких команд.
База динамики:
dp[1]=1;
Формула перехода:
dp[i]=dp[i-1] - если i - четное.
dp[i]=dp[i-1] + dp[(i-1)/2] - если i нечетное;
Но при этом если i-1 = 24 или (i-1)/2 = 24, то его не учитываем. Можно заметить, что для числа 25 будет формула
dp[25]=dp[24] + dp[12], а т. к. dp[24] не считаем, то ответ совпадает с dp[12].
Посчитаем dp[13] (далее будет приведены значения в ячейках dp от 1 до 12): 1 1 2 2 3 3 5 5 7 7 10 10.
Ответ: 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))