Исполнитель РазДва преобразует число на экране. У исполнителя есть две команды, которым присвоены номера.
1. Прибавить 1.
2. Умножить на 2.
Первая команда увеличивает число на экране
Сколько существует программ, которые преобразуют исходное
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном
Искомое количество программ равно количеству программ, получающих
Пусть R(n) — количество программ, которые
Верно следующее соотношение:
Найдём количество программ, преобразующих
R(1) = 1;
R(2) = 2;
R(3) = 2;
R(4) = 4;
R(5) = 4;
R(6) = 6;
R(7) = 6;
R(8) = 10;
R(9) = 10.
Из числа 9 число 20 можно получить только последовательностью команд 211, поскольку траектория не должна содержать
Найдём количество программ, преобразующих
R(1) = 1;
R(2) = 2;
R(3) = 2;
R(4) = 4;
R(5) = 4.
Из числа 5 число 20 можно получить либо последовательностью команд 22, либо последовательностью команд 21..1, поскольку траектория не должна содержать
Таким образом, ответ — 10 + 8 = 18.
Ответ: 18.
Приведём другое решение на языке Python.
def f(x, y):
if x > y or x == 10:
return 0
if x == y:
return 1
else:
return f(x + 1, y) + f(x * 2, y)
def f1(x, y):
if x > y or x == 9:
return 0
if x == y:
return 1
else:
return f1(x + 1, y) + f1(x * 2, y)
print(f(1, 9) * f(9, 20) + f1(1, 10) * f1(10, 20))