Подготовка к государственной итоговой аттестации по информатике

Задание 23. (ДЕМО-2023)

Исполнитель преобразует число на экране. 
У исполнителя есть две команды, которые обозначены латинскими буквами:  
A. Прибавить 1 
B. Умножить на 2 
Программа для исполнителя – это последовательность команд.  Сколько   существует   программ,   для   которых   при   исходном   числе   1 результатом  является  число  35,  при  этом  траектория  вычислений  содержит число 10 и не содержит 17? 
Траектория  вычислений  программы  –  это  последовательность  результатов выполнения  всех  команд  программы.  Например,  для  программы  ABA при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение

function f(x,y: integer):integer;

begin 

 if x=y then f:=1 else   

      if (x>y) or (x=17) then f:=0 else     

           if x<y then f:=f(x+1,y)+f(x*2,y)

end;

begin  

  print(f(1,10)*f(10,35));

end.

Ответ: 98

ПРИМЕРЫ:

1. У исполнителя есть три команды, которым присвоены номера:

   1. Прибавить 1

   2. Умножить на 3

   3. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает на 2.

Сколько существует программ, которые преобразуют исходное число 3 в число 14 и при этом траектория вычислений содержит число 9? 

function f(x,y: integer):integer;

begin  

   if x=y then f:=1 else    

      if (x>y)  then f:=0 else      

           if x<y then f:=f(x+1,y)+f(x*3,y)+f(x+2,y)

end;

begin  

  print(f(3,9)*f(9,14));

end.

Ответ:  112

2. Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

   1. Прибавить 1

   2. Умножить на 2

   3. Умножить на 3

Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 46, и при этом траектория вычислений содержит число 12 и не содержит число 25?

function f(x,y: integer):integer;

begin 

    if x=y then f:=1 else    

       if (x>y) or (x=25) then f:=0 else    

        if x<y then f:=f(x+1,y)+f(x*2,y)+f(x*3,y)

end;

begin  

   print(f(3,12)*f(12,46));

end.

Ответ:  120