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


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

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

 

1. прибавь 2,

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

 

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

Решение.

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

Верно следующее соотношение: R(n) = R(n / 2) + R(n − 2) (если n > 2).

При n = 4 R(n)) = 2 (один способ: прибавлением двойки, второй способ: умножением на два). Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных 2 и не превосходящих 42. R(n) для любого нечетного n равно 0.

 

Имеем:

R(4)= 2,

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

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

R(10) = R(5) + R(8) = 0 + 4 = 4,

R(12) = R(6) + R(10) = 2 + 4 = 6,

R(14) = R(7) + R(12) = 0 + 6 = 6,

R(16) = R(8) + R(14) = 4 + 6 = 10,

R(18) = R(9) + R(16) = 0 + 10 = 10,

R(20) = R(10) + R(18) = 4 + 10 = 14.

R(22) = R(11) + R(20) = 0 + 14 = 14.

R(24) = R(12) + R(22) = 6 + 14 = 20.

R(26) = R(13) + R(24) = 0 + 20 = 20.

R(28) = R(14) + R(26) = 6 + 20 = 26.

R(30) = R(15) + R(28) = 0 + 26 = 26.

R(32) = R(16) + R(30) = 10 + 26 = 36.

R(34) = R(17) + R(32) = 0 + 36 = 36.

R(36) = R(18) + R(34) = 10 + 36 = 46.

R(38) = R(19) + R(36) = 0 + 46 = 46.

R(40) = R(20) + R(36) = 14 + 46 = 60.

R(42) = R(21) + R(40) = 0 + 60 = 60.