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

У ис­пол­ни­те­ля Ариф­ме­тик две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

 

1.  при­бавь 1,

2.  при­бавь 3.

 

Пер­вая из них уве­ли­чи­ва­ет на 1 число на экра­не, вто­рая уве­ли­чи­ва­ет это число на 3.

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

Сколь­ко су­ще­ству­ет про­грамм, ко­то­рые число 7 пре­об­ра­зу­ют в число 20?

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

Ре­ше­ние.

Для сло­же­ния спра­вед­лив пе­ре­ме­сти­тель­ный (ком­му­та­тив­ный) закон, зна­чит, по­ря­док ко­манд в про­грам­ме не имеет зна­че­ния для ре­зуль­та­та.

 

Обе ко­ман­ды уве­ли­чи­ва­ют ис­ход­ное число, по­это­му ко­ли­че­ство ко­манд не может пре­вос­хо­дить 20 − 7 = 13. При этом ми­ни­маль­ное ко­ли­че­ство ко­манд  — 5 (так как (15 − 2)/3 = 4, 15−3 · 4 = 1 = 1 · 1). При этом за­ме­тим, что 7  — не­чет­ное, а 20  — чет­ное. А так как обе ко­ман­ды уве­ли­чи­ва­ют ис­ход­ное число на не­чет­ное число, то ко­ли­че­ство ко­манд долж­но быть не­чет­ным.

 

Иначе го­во­ря, ко­манд может быть 5, 7, 9, 11 или 13. Так как, как было ска­за­но выше, по­ря­док ко­манд не имеет зна­че­ния, каж­до­му числу ко­манд со­от­вет­ству­ет один набор ко­манд, ко­то­рые можно рас­по­ло­жить в любом по­ряд­ке. 5 ко­ман­дам со­от­вет­ству­ет набор 22221 (5 воз­мож­ных ва­ри­ан­тов рас­по­ло­же­ния), 7 ко­ман­дам  — набор 2221111 (35 воз­мож­ных ва­ри­ан­тов рас­по­ло­же­ния: это число пе­ре­ста­но­вок с по­вто­ре­ни­я­ми P7(3,4)  =  7!/(3! · 4!)), 9 ко­ман­дам  — 22111111 (36 воз­мож­ных ва­ри­ан­тов рас­по­ло­же­ния), 11 ко­ман­дам  — 21111111111 (11 воз­мож­ных ва­ри­ан­тов рас­по­ло­же­ния), 13 ко­ман­дам  — 11111111111111 (1 ва­ри­ант рас­по­ло­же­ния). Всего по­лу­ча­ет­ся 88 про­грамм.

 

Ответ: 88.

 

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

def f(x, y):

if x == y:

return 1

if x > y:

return 0

else:

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

print(f(7, 20))


Аналоги к заданию № 4944: 4985 5497 5753 ... Все

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