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


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

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

 

1. прибавь 1,

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

 

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

Решение.

Обозначим 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 = 2 R(n)) = 1 (один способ: прибавлением единицы). Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных 2 и не превосходящих 21.

 

Имеем:

 

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

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

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

R(8) = R(4)+R(6) = 4 + 6 = 10 = R(9),

R(10) = R(5) + R(8) = 4 + 10 = 14 = R(11),

R(12) = R(6) + R(10) = 6 + 14 = 20 = R(13),

R(14) = R(7) + R(12) = 6 + 20 = 26 = R(15),

R(16) = R(8) + R(14) = 10 + 26 = 36 = R(17),

R(18) = R(9) + R(16) = 10 + 36 = 46 = R(19),

R(20) = R(10) + R(18) = 14 + 46 = 60 = R(21).

 

Ответ: 60.

Источник: ЕГЭ по ин­фор­ма­ти­ке 30.05.2013. Ос­нов­ная волна. Сибирь. Ва­ри­ант 2., ЕГЭ по ин­фор­ма­ти­ке 30.05.2013. Ос­нов­ная волна. Сибирь. Ва­ри­ант 3., ЕГЭ по ин­фор­ма­ти­ке 30.05.2013. Ос­нов­ная волна. Сибирь. Ва­ри­ант 3.