Question

Исполнитель КЕДР преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 12. Умножь на 2Первая из них увеличивает число на экране на 1, вторая увеличивает это число в 2 раза.Программа для исполнителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 16?

Answer 1

Ответ:

36

Объяснение:

Составим формулу: F(x) = F(x + 1) + F(x * 2), где x - число которое нужно получить, "+ 1" и "*2" - это команды исполнителя.

Последнее значение - это число 16. Запишем, что

F(16) = 1 (т.е. из числа 16 можно сделать 1 программу)

F(15) = F(15+1) (предыдущая) + F(15*2) = F(16) + F(30) = 1 + 0 = 1 (т.к. значения F(30) у нас нет, то равно 0)

F(14) = F(14+1) + F(14*2) = 1+0=1

F(13) = F(14) + F(13*2) = 1+0=1

F(12) = F(13) + F(12*2) = 1+0=1

F(11) = F(12) + F(11*2) = 1+0=1

F(10) = F(11) + F(10*2) = 1+0=1

F(9) = F(10) + F(9*2) = 1+0=1

F(8) = F(9) + F(8*2) = 1+1=2

F(7) = F(8) + F(7*2) = 2+1=3

F(6) = F(7) + F(6*2) = 3+1=4

F(5) = F(6) + F(5*2) = 4+1=5

F(4) = F(5) + F(4*2) = 5+2=7

F(3) = F(4) + F(3*2) = 7+4=11

F(2) = F(3) + F(2*2) = 11+7=18

F(1) = F(2) + F(1*2) = 18+18=36

Answer 2

Для решения этой задачи, давайте разберемся, сколько всего существует возможных программ, которые преобразуют число 1 в число 16, используя две заданные команды: "Прибавить 12" и "Умножь на 2".

Для начала, давайте представим это в виде дерева возможных программ:

pythonCopy code
      1
     / \
   +12 *2
   /    \
 +12    *2
  /       \
...       ...

Мы можем видеть, что существует несколько путей от числа 1 к числу 16, используя только две заданные команды. Давайте посчитаем количество программ, которые приводят к числу 16.

1. Путь: 1 → +12 → +12 → +12 → +12 = 37
2. Путь: 1 → *2 → +12 → +12 = 28
3. Путь: 1 → +12 → *2 → +12 = 26
4. Путь: 1 → *2 → *2 → +12 = 20
5. Путь: 1 → +12 → +12 → *2 = 26
6. Путь: 1 → *2 → +12 → *2 = 24
7. Путь: 1 → +12 → *2 → *2 = 25
8. Путь: 1 → *2 → *2 → *2 = 16

Итак, существует 8 различных программ, которые преобразуют число 1 в число 16, используя только команды "Прибавить 12" и "Умножь на 2".