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

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

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

2.  Сде­лай нечётное.

Пер­вая из этих ко­манд уве­ли­чи­ва­ет число x на экра­не на 1, вто­рая пе­ре­во­дит число x в число 2x + 1. На­при­мер, вто­рая ко­ман­да пе­ре­во­дит число 10 в число 21. Про­грам­ма для ис­пол­ни­те­ля Не­четМ  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет таких про­грамм, ко­то­рые число 1 пре­об­ра­зу­ют в число 25, причём тра­ек­то­рия вы­чис­ле­ний не со­дер­жит число 24? Тра­ек­то­рия вы­чис­ле­ний про­грам­мы  — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 121 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 8, 17, 18.

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

Ре­ше­ние.

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

База ди­на­ми­ки:

dp[1]  =  1.

Фор­му­ла пе­ре­хо­да:

dp[i]  =  dp[i – 1]  — если i чет­ное;

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

Но при этом если i – 1  =  24 или (i – 1) : 2  =  24, то его не учи­ты­ва­ем. Можно за­ме­тить, что для числа 25 будет фор­му­ла

dp[25]  =  dp[24] + dp[12], а так как dp[24] не счи­та­ем, то ответ сов­па­да­ет с dp[12].

По­счи­та­ем dp[13] (далее будет при­ве­де­ны зна­че­ния в ячей­ках dp от 1 до 12): 1 1 2 2 3 3 5 5 7 7 10 10.

 

Ответ: 10.

 

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

def f(x, y):

if x > y or x == 24:

return 0

if x == y:

return 1

else:

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

print(f(1,25))


Аналоги к заданию № 13418: 13471 Все

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