У исполнителя Удвоитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 2.
Первая из них увеличивает на 1 число на экране, вторая удваивает его.
Программа для Удвоителя – это последовательность команд.
Сколько есть программ, которые число 3 преобразуют в число 23?
Построим полное дерево решений и подсчитаем количество вариантов. Рассмотрим сначала ветвь, где первая команда умножение:
1) 3 → 6 → 12 → 13 → ... → 23
2) 6 → 7 → 14 → ... → 23
3) 7 → 8 → 16 → ... → 23
4) 8 → 9 → 18 → ... → 23
5) 9 → 10 → 20 → ... → 23
6) 10 → 11 → 22 → ...23
7) 11 → 12 → ... → 23
Теперь рассмотрим ветвь, где первая команда сложение, вторая умножение:
8) 3 → 4 → 8 → 16 → ... → 23
9) 8 → 9 → 18 → ... → 23
10) 9 → 10 → 20 → ... → 23
11) 10 → 11 → 22 → ...23
12) 11 → 12 → ... → 23
Ветвь, где первая и вторая команда сложение:
13) 3 → 4 → 5 → 10 → 20 → ... → 23
14) 10 → 11 → 22 → .. → 23
15) 11 → 12 → ... → 23
Первые три и более команд сложение:
16) 3 → 4 → 5 → 6 → 12 → ... → 23
Ещё 6 программ будут иметь такой же конец, как программы 2 — 7.
Всего 22 программы.
Ответ: 22.
Приведём другое решение на языке 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(3, 23))