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


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

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

 

1. прибавь 1

2. умножь на 2

 

Сколько есть программ, которые число 1 преобразуют в число 16?

Решение.

Обозначим 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 и не превосходящих 16.

Имеем:

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


Аналоги к заданию № 3301: 3305 3525 7275 7279 Все