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


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

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

 

1. прибавь 1,

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

 

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

Решение.

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

Обе команды увеличивают исходное число, поэтому количество команд не может превосходить 20 − 1 = 19.

 

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

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) = 2 (два способа: прибавлением единицы и удвоением).

Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных 2 и не превосходящих 20.

 

Имеем:

R(2) = 2 = R(3)

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

R(6) = R(3) + R(4) = 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.