У исполнителя Удвоитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 2.
Первая из них увеличивает число на экране на 1, вторая удваивает его. Программа для Удвоителя — это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20?
Обозначим R(n) — количество программ, которые преобразуют число 2 в число n. Обозначим t(n) наибольшее кратное 2, не превосходящее n. Верны следующие соотношения:
1. Если n не делится на 2, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) — прибавлением единиц.
2. Пусть n делится на 2. Тогда R(n) = R(n / 2) + R(n − 1) = R(n / 2) + R(n − 2) (если n > 2). Таким образом, достаточно вычислить значения R(n) для всех чисел, кратных 2 и не превосходящих 20. Имеем:
R(2)= 2 = R(3),
R(4) = R(2) + R(3) = 2 + 2 = 4 = R(5),
R(6) = R(3) + R(5) = 2 + 4 = 6 = R(7),
R(8) = R(4) + R(7)= 4 + 6 = 10 = R(9),
R(10) = R(5) + R(9) = 4 + 10 = 14 = R(11),
R(12) = R(6) + R(11) = 6 + 14 = 20 = R(13),
R(14) = R(7) + R(13) = 6 + 20 = 26 = R(15),
R(16) = R(8) + R(15) = 10 + 26 = 36 = R(17),
R(18) = R(9) + R(17) = 10 + 36 = 46 = R(19),
R(20) = R(10) + R(19) = 14 + 46 = 60.
Ответ: 60.
Приведём другое решение на языке Python.
def f(x, y):
if x > y:
return 0
if x == y:
return 1
else:
return f(x + 1, y) + f(x * 2, y)
print(f(1, 20))