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

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

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

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

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

Пер­вая ко­ман­да уве­ли­чи­ва­ет число на экра­не на 1, вто­рая уве­ли­чи­ва­ет его на 2. Про­грам­ма для ис­пол­ни­те­ля Май16  — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 1 ре­зуль­та­том яв­ля­ет­ся число 13 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 7? Тра­ек­то­рия вы­чис­ле­ний про­грам­мы  — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 121 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 8, 10, 11.

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

Ре­ше­ние.

Ис­ко­мое ко­ли­че­ство про­грамм равно про­из­ве­де­нию ко­ли­че­ства про­грамм, по­лу­ча­ю­щих из числа 1 число 7, на ко­ли­че­ство про­грамм, по­лу­ча­ю­щих из числа 7 число 13. За­ме­тим, что ко­ли­че­ство спо­со­бов по­лу­чить из числа 1 число 7 равно ко­ли­че­ству спо­со­бов по­лу­чить из числа 7 число 13. По­это­му по­счи­та­ем ко­ли­че­ство спо­со­бов по­лу­чить из числа 1 число 7 и воз­ведём его в квад­рат.

 

Пусть 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

 

13 в квад­ра­те = 169

 

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


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

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