Тип 23 № 6011 
Оператор присваивания и ветвления. Перебор вариантов, построение дерева. Поиск количества программ по заданному числу
i
У исполнителя Удвоитель две команды, которым присвоены номера.
1. Прибавь 1.
2. Умножь на 2.
Первая из них увеличивает число на экране на 1, вторая удваивает его. Программа для Удвоителя — это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число 22?
Решение. Обозначим 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). При n = 2 R(n) = 2 (два способа: прибавлением единицы и удвоением). Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных 2 и не превосходящих 20.
Имеем:
R(3) = 1;
R(4) = 2 = R(5);
R(6) = R(3) + R(4) = 1 + 2 = 3 = R(7);
R(8) = R(4) + R(6) = 2 + 3 = 5 = R(9);
R(10) = R(5) + R(8) = 2 + 5 = 7 = R(11);
R(12) = R(6) + R(10) = 3 + 7 = 10 = R(13);
R(14) = R(7) + R(12) = 3 + 10 = 13 = R(15);
R(16) = R(8) + R(14) = 5 + 13 = 18 = R(17);
R(18) = R(9) + R(16) = 5 + 18 = 23 = R(19);
R(20) = R(10) + R(18) = 7 + 23 = 30 = R(21);
R(22) = R(11) + R(20) = 7 + 30 = 37.
Ответ: 37.
Приведём другое решение на языке Python.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x + 1, y) + f(x * 2, y)
print(f(2, 22))
Ответ: 37
PDF-версии: горизонтальная · вертикальная · крупный шрифт · с большим полем