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


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

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

 

1. прибавь 2,

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

 

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

Ре­ше­ние.

Обо­зна­чим R(n) — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n.

 

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

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

 

2. Пусть n де­лит­ся на 3. Тогда R(n) = R(n / 3) + R(n − 2).

 

До­ста­точ­но вы­чис­лить все зна­че­ния R(n). За­ме­тим, что R от чет­но­го числа все­гда равно нулю. R от числа, ко­то­рое после вы­чи­та­ния 1 не крат­но 2, тоже равно нулю.

 

R(2) = 0,

R(3) = 2 (можно умно­жить еди­ни­цу на 3 или при­ба­вить 2 к еди­ни­це),

R(4) = R(2) = 0,

R(5) = R(3) = 2,

R(6) = R(4) + R(2) = 0,

R(7) = R(5) = 2,

R(8) = R(6) = 0,

R(9) = R(7) + R(3) = 2 + 2 = 4,

...

R(12) = R(10) + R(4) = 0 + 0 = 0,

...

R(15) = R(13) + R(5) = 4 + 2 = 6,

...

R(18) = R(16) + R(6) = 0 + 0 = 0,

...

R(21) = R(19) + R(7) = 6 + 2 = 8,

...

R(24) = R(22) + R(8) = 0 + 0 = 0,

...

R(27) = R(25) + R(9) = 8 + 4 = 12,

...

R(30) = R(28) + R(10) = 0 + 0 = 0,

...

R(33) = R(31) + R(11) = 12 + 4 = 16,

...

R(36) = R(34) + R(12) = 0 + 0 = 0,

...

R(39) = R(37) + R(13) = 16 + 4 = 20,

...

R(42) = R(40) + R(14) = 0 + 0 = 0,

...

R(45) = R(43) + R(15) = 20 + 6 = 26,

...

R(48) = R(46) + R(16) = 0 + 0 = 0,

 

R(49) = R(47) = 26.