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