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

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

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

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

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

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

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

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

Ре­ше­ние.

Ис­ко­мое ко­ли­че­ство про­грамм равно ко­ли­че­ству про­грамм, по­лу­ча­ю­щих из числа 1 число 14.

Пусть R(n)  — ко­ли­че­ство про­грамм, ко­то­рые число 2 пре­об­ра­зу­ют в число n.

Верно сле­ду­ю­щее со­от­но­ше­ние:

R(n)  =  R(n − 2) + R(n : 2) (если n чётно и боль­ше од­но­го).

R(1)  =  1;

R(2)  =  1;

R(3)  =  1;

R(4)  =  2;

R(5)  =  1;

R(6)  =  3;

R(7)  =  1;

R(8)  =  5;

R(9)  =  1;

R(10)  =  6;

R(11)  =  1;

R(12)  =  9;

R(13)  =  1;

R(14)  =  10.

 

Из числа 14 число 30 можно по­лу­чить двумя спо­со­ба­ми. Пер­вый спо­соб  — по­сле­до­ва­тель­но­стью ко­манд 1..1, вто­рой  — по­сле­до­ва­тель­но­стью ко­ман­дам 21. Таким об­ра­зом, ко­ли­че­ство про­грамм, удо­вле­тво­ря­ю­щих усло­вию за­да­чи, равно 10 · 2  =  20.

 

Ответ: 20.

 

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

def f(x, y):

if x > y:

return 0

if x == y:

return 1

else:

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

print(f(1, 14) * f(14, 30))


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

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