Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 2.
Первая команда увеличивает число на экране
Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное
Решим задачу с помощью языка программирования PascalABC. Напишем рекурсивную функцию, подсчитывающую необходимое количество программ. Учтём, что в программе не должно повторяться две команды умножения подряд. Для этого введём булевую переменную multiplied. Приведём код решения:
function F(x, y: integer; multiplied: boolean): integer;
begin
if x = y
then F := 1
else if x > y
then F := 0
else if multiplied = False
then F := F(x + 1, y, False) + F(x + 2, y, False) + F(x * 2, y, True)
else if multiplied = True
then F := F(x + 1, y, False) + F(x + 2, y, False);
end;
begin
writeln(F(1, 11, False));
end.
Таким образом, количество программ, удовлетворяющих условию задачи и выведенное на экран,
Ответ: 213.
Приведём решение на языке Python.
def f(x, y, Flag):
if x > y:
return 0
if x == y:
return 1
elif Flag:
return f(x + 1, y, True) + f(x + 2, y, True) + f(x * 2, y, False)
else:
return f(x + 1, y, True) + f(x + 2, y, True)
print(f(1, 11, True))