У исполнителя Полтор две команды, которым присвоены номера:
1. прибавь один,
2. умножь на полтора.
Первая из них увеличивает на 1 число на экране, вторая увеличивает это число в 1,5 раза, если число чётное. К нечётным числам вторая команда неприменима. Программа для Полтора — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 20?
Решение.Обозначим 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(20) = R(19) = 32.
Ответ: 32.
Ответ: 32
