infoegehelp.ru

Нам нужно построить граф, описывающий выполнение команд Удвоителя. Строим его до тех пор, пока не получим число 11. 23/2=11 с остатком. Числа больше 11 дают только одну программу, т.к. нельзя применить команду "умножить на 2". Если при построении графа получаем числа больше 11, то дальше от таких чисел ветки не строим. Также поступаем и с числами, которые уже есть в графе.

Построим этот граф:

После выполнения 4-х команд получаем число 11.

Обозначим количество программ-решений для получения из числа n числа 23 как Р(n).

Определим P(11):

12*2>23, поэтому к 23 ведет только 1 решение.

22*2>23, поэтому к 23 ведет только 1 решение.

Получили, P(11)=1+1=2.

Зная P(11), можно определить P(10):

P(11)=2 решения.

20*2>23, поэтому к 23 ведет только 1 решение.

Получили, P(10)=2+1=3.

Зная P(10) можно определить P(8):

P(10)=3 решения.

18*2>23, поэтому к 23 ведет только 1 решение.

16*2>23, поэтому к 23 ведет только 1 решение.

Получили, P(8)=3+1+1=5.

Зная P(8) можно определить P(6):

P(8)=5 решений.

14*2>23, поэтому к 23 ведет только 1 решение.

12*2>23, поэтому к 23 ведет только 1 решение.

Получили, P(6)=5+1+1=7.

Зная P(6) можно определить P(5):

P(6)=7 решений.

P(10)=3 решения.

Получили, P(5)=7+3=10.

Теперь можно определить P(3):

P(5)=10 решений.

P(8)=5 решений.

P(6)=7 решений.

P(3)=10+5+7=22.

Получили 22 программы.

Краткое решение:

P(n)=1 при n>11.

P(11)=P(12)+P(22)=2 программы.

P(10)=P(11)+P(20)=2+1=3 программы.

P(8)=P(9)+P(16)=P(10)+P(18)+P(16)=3+1+1=5 программ.

P(6)=P(7)+P(12)=P(8)+P(14)+P(12)=5+1+1=7 программ.