Задания
Версия для печати и копирования в MS Word
Тип 23 № 13606
i

Ис­пол­ни­тель А17 пре­об­ра­зу­ет число на экра­не.

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

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

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

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

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

Про­грам­ма для ис­пол­ни­те­ля А17  — это по­сле­до­ва­тель­ность ко­манд.

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

Тра­ек­то­рия вы­чис­ле­ний про­грам­мы  — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 121 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 8, 16, 17.

Спрятать решение

Ре­ше­ние.

Ис­поль­зу­ем ди­на­ми­че­ское про­грам­ми­ро­ва­ние. За­ве­дем мас­сив dp, где dp[i]  — ко­ли­че­ство спо­со­бов по­лу­чить число i.

База ди­на­ми­ки dp[2]  =  1.

Пе­ре­хо­ды:

dp[i]  =  dp[i – 1] + dp[i : 2] (если i четно) + dp[i : 3] (если i крат­но 3).

При этом если i > 14, а i – 1, или i : 2, или i : 3 мень­ше 14, то этими зна­че­ни­я­ми пре­не­бре­га­ем, так как тогда не будет вы­пол­не­но усло­вие тра­ек­то­рии. Далее будут по­ка­за­ны зна­че­ния мас­си­ва dp от 2 до 28:

1 1 2 2 4 4 6 7 9 9 15 15 19 19 19 19 19 19 19 19 19 19 19 19 19 19 38.

 

Ответ:38.

 

При­ведём дру­гое ре­ше­ние на языке Python.

def f(x, y):

if x > y:

return 0

if x == y:

return 1

else:

return f(x + 1, y) + f(x * 2, y) + f(x * 3, y)

print(f(2, 14) * f(14, 28))


Аналоги к заданию № 13606: 83153 83181 13633 Все

Раздел кодификатора ФИПИ: 1.6.2 Вы­чис­ли­мость. Эк­ви­ва­лент­ность ал­го­рит­ми­че­ских мо­де­лей