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

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

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

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

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

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

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

Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 1 ре­зуль­та­том яв­ля­ет­ся число 11?

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

Ре­ше­ние.

Пусть f левая круг­лая скоб­ка x пра­вая круг­лая скоб­ка   — ко­ли­че­ство спо­со­бов по­лу­чить из числа 1 число х. За­ме­тим, что для x > 2: f левая круг­лая скоб­ка x пра­вая круг­лая скоб­ка = f левая круг­лая скоб­ка x минус 1 пра­вая круг­лая скоб­ка плюс f левая круг­лая скоб­ка x минус 2 пра­вая круг­лая скоб­ка .

 

f левая круг­лая скоб­ка 1 пра­вая круг­лая скоб­ка = 1;

f левая круг­лая скоб­ка 2 пра­вая круг­лая скоб­ка = 1;

f левая круг­лая скоб­ка 3 пра­вая круг­лая скоб­ка = 2;

f левая круг­лая скоб­ка 4 пра­вая круг­лая скоб­ка = 3;

f левая круг­лая скоб­ка 5 пра­вая круг­лая скоб­ка = 5;

f левая круг­лая скоб­ка 6 пра­вая круг­лая скоб­ка = 8;

f левая круг­лая скоб­ка 7 пра­вая круг­лая скоб­ка = 13;

f левая круг­лая скоб­ка 8 пра­вая круг­лая скоб­ка = 21;

f левая круг­лая скоб­ка 9 пра­вая круг­лая скоб­ка = 34;

f левая круг­лая скоб­ка 10 пра­вая круг­лая скоб­ка = 55;

f левая круг­лая скоб­ка 11 пра­вая круг­лая скоб­ка = 89.

 

Ответ: 89.

 

При­ведём дру­гое ре­ше­ние на языке 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)

print(f(1, 11))


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

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