СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 22 № 3623

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

 

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

2. умножь на 3.

 

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

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

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

Ре­ше­ние.

Обо­зна­чим R(n) — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 3 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 9, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 3.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить (93- 3) / 3= 31.

 

Верны сле­ду­ю­щие со­от­но­ше­ния:

1. Если n не де­лит­ся на 9, то тогда R(n) = R(t(n)), так как су­ще­ству­ет един­ствен­ный спо­соб по­лу­че­ния n из t(n) — при­бав­ле­ни­ем троек.

 

2. Пусть n де­лит­ся на 9.

Тогда R(n) = R(n / 3) + R(n - 3)= R(n / 3) + R(n - 9) (если n > 9).

При n = 9 R(n)) = 1 (один спо­соб: при­бав­ле­ни­ем трой­ки).

По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 9 и не пре­вос­хо­дя­щих 72: сна­ча­ла вы­чис­ля­ем R(3), затем R(9), R(18) и т. д.

Имеем:

R(3)=1=R(6)

R(9) = 2 = R(12) = R(15),

R(18) = R(6)+R(9)=1+2=3= R(21)=R(24),

R(27) = R(9) + R(18) =2 + 3 = 5 = R(30) = R(33),

R(36) = R(12) + R(27) =2 + 5 = 7= R(39) = R(42),

R(45) = R(15) + R(36) =2 + 7 = 9= R(48) = R(51),

R(54) = R(18) + R(45) =3 + 9 =12= R(57) = R(60),

R(63) = R(21) + R(54) =3 + 12 =15= R(66) = R(69),

R(72) = R(24) + R(63) =3 + 15 =18= R(75) = R(78),

R(81) = R(27) + R(72) =5 + 18 =23= R(84) = R(87),

R(90) = R(30) + R(81) =5 + 23 =28= R(93).

 

Ответ: 28.

 

Дру­гая форма ре­ше­ния.

Будем ре­шать по­став­лен­ную за­да­чу по­сле­до­ва­тель­но для чисел 3, 6, 9,..., 93 (то есть для каж­до­го из чисел опре­де­лим, сколь­ко про­грамм ис­пол­ни­те­ля су­ще­ству­ет для его по­лу­че­ния). За­ме­тим, что мы можем по­лу­чить толь­ко числа крат­ные 3. Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 6 в число n, будем обо­зна­чать через R(n). Число 3 у нас уже есть, зна­чит, его можно по­лу­чить с по­мо­щью «пу­стой» про­грам­мы. Любая не­пу­стая про­грам­ма уве­ли­чит ис­ход­ное число, т. е. даст число, боль­ше 3. Зна­чит, R(3) = 1. Для каж­до­го сле­ду­ю­ще­го числа рас­смот­рим, из ка­ко­го числа оно может быть по­лу­че­но за одну ко­ман­ду ис­пол­ни­те­ля. Если число не де­лит­ся на де­вять, то оно может быть по­лу­че­но толь­ко из преды­ду­ще­го с по­мо­щью ко­ман­ды при­бавь 3. Зна­чит, ко­ли­че­ство ис­ко­мых про­грамм для та­ко­го числа равно ко­ли­че­ству про­грамм для преды­ду­ще­го воз­мож­но­го числа:

Если число на 3 де­лит­ся, то ва­ри­ан­тов по­след­ней ко­ман­ды два: при­бавь 3 и умножь на 3, тогда . За­пол­ним со­от­вет­ству­ю­щую таб­ли­цу по при­ведёным фор­му­лам слева на­пра­во:

 

369121518212427303336394245
112223335557779
485154576063666972757881848790
9912121215151518181823232328
93
28

При этом ячей­ки, от­но­ся­щи­е­ся к чис­лам, ко­то­рые не де­лят­ся на 9, можно в ре­ше­нии и опу­стить (за ис­клю­че­ни­ем пер­во­го и по­след­не­го чисел):

 

3918273645546372819093
123579121518232828

 

Ответ: 28.