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

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

A.  вычти 3

B.  по­де­ли на 2

Пер­вая ко­ман­да умень­ша­ет число на экра­не на 3, вто­рая ко­ман­да делит число на 2 (не­це­лый ре­зуль­тат округ­ля­ет­ся до бли­жай­ше­го це­ло­го в боль­шую сто­ро­ну). Про­грам­ма для ис­пол­ни­те­ля  — это по­сле­до­ва­тель­ность ко­манд.

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

Тра­ек­то­рия вы­чис­ле­ний про­грам­мы  — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы.

На­при­мер, для про­грам­мы ABA при ис­ход­ном числе 100 тра­ек­то­рия со­сто­ит из чисел 97, 49, 46.

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

Ре­ше­ние.

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

def f(x, y):

if x < y :

return 0

if x == 35 or x == 51:

return 0

if x == y:

return 1

else:

return f(x - 3, y) + f(x // 2 + x % 2, y)

print(f(120, 20))

 

Ответ: 10.