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


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

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

 

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

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

 

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

Про­грам­ма для Удво­и­те­ля — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, ко­то­рые число 2 пре­об­ра­зу­ют в число 22?

Ре­ше­ние.

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

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

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

2. Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 2). При n = 4 R(n)) = 2 (два спо­со­ба: при­бав­ле­ни­ем еди­ни­цы и умно­же­ни­ем на 2). До­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 22.

Имеем:

R(4) = 2 = R(5),

R(6) = R(3) + R(5) = 1 + 2 = 3 = R(7),

R(8) = R(4) + R(6) = 2 + 3 = 5 = R(9),

R(10) = R(5) + R(8) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(10) = 3 + 7 = 10 = R(13),

R(14) = R(7) + R(12) = 3 + 10 = 13 = R(15),

R(16) = R(8) + R(14) = 5 + 13 = 18 = R(17),

R(18) = R(9) + R(16) = 5 + 18 = 23 = R(19),

R(20) = R(10) + R(18) = 7 + 23 = 30 = R(21),

R(22) = R(11) + R(20) = 7 + 30 = 37.

 

Ответ: 37.