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