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

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

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

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

3.  При­бавь 5.

Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 3, вто­рая уве­ли­чи­ва­ет это число на 4, а тре­тья  — на 5. Про­грам­ма для ис­пол­ни­те­ля Уве­ли­чи­тель345  — это по­сле­до­ва­тель­ность ко­манд.

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

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

Ре­ше­ние.

За­ме­тим, что все опе­ра­ции толь­ко лишь при­бав­ля­ют не­ко­то­рую кон­стан­ту к числу. По­это­му не важно, в каком по­ряд­ке вы­пол­нять не­ко­то­рый дан­ный набор ко­манд. Пусть x  — ко­ли­че­ство пер­вых ко­манд, y  — вто­рых, а z  — тре­тьих. Со­ста­вим урав­не­ние:

3 умно­жить на x плюс 4 умно­жить на y плюс 5 умно­жить на z = 20; x, y, z боль­ше или равно 0; x, y, z при­над­ле­жит Z .

А имен­но  — найдём с его по­мо­щью все на­бо­ры ко­манд, ко­то­рые под­хо­дят под усло­вие. И уже для каж­до­го на­бо­ра в от­дель­но­сти под­счи­та­ем ко­ли­че­ство воз­мож­ных пе­ре­ста­но­вок.

Найдём все ре­ше­ния урав­не­ния: (0, 5, 0), (4, 2, 0), (1, 3, 1), (5, 0, 1), (2, 1, 2), (0, 0, 4).

Ко­ли­че­ство пе­ре­ста­но­вок для дан­но­го на­бо­ра по­счи­та­ем по фор­му­ле подсчёта пе­ре­ста­но­вок с по­вто­ре­ни­я­ми:

Пусть каж­до­го вида ко­манд a, b и с. Тогда всего пе­ре­ста­но­вок из этих ко­манд будет  дробь: чис­ли­тель: левая круг­лая скоб­ка a плюс b плюс c пра­вая круг­лая скоб­ка !, зна­ме­на­тель: a!b!c! конец дроби .

Найдём те­перь ответ на за­да­чу, про­сум­ми­ро­вав от­ве­ты для каж­до­го на­бо­ра:

 дробь: чис­ли­тель: 5!, зна­ме­на­тель: 5! конец дроби плюс дробь: чис­ли­тель: 6!, зна­ме­на­тель: 4!2! конец дроби плюс дробь: чис­ли­тель: 5!, зна­ме­на­тель: 3! конец дроби плюс дробь: чис­ли­тель: 6!, зна­ме­на­тель: 5! конец дроби плюс дробь: чис­ли­тель: 5!, зна­ме­на­тель: 2!2! конец дроби плюс дробь: чис­ли­тель: 4!, зна­ме­на­тель: 4! конец дроби = 1 плюс 15 плюс 20 плюс 30 плюс 6 плюс 1 = 73.

Ответ: 73.

 

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

def f(x, y):

if x > y:

return 0

if x == y:

return 1

else:

return f(x + 3, y) + f(x + 4, y) + f(x + 5, y)

print(f(22, 42))


Аналоги к заданию № 8670: 7466 7679 7706 ... Все

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