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


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

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

 

1. прибавь 1

2. умножь на 4

 

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

Решение.

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

Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может превосходить 55.

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

1. Если n не делится на 4, то тогда R (n) = R(T(n)), так как существует единственный способ получения n из T(n) - прибавлением единиц.

2. Пусть n делится на 4.

Тогда R (n) = R(n/4)+R(n-1)= R(n/4)+R(n-4) (если n>4).

При n = 4 выполнено: R(n) = 2 (два способа: прибавлением трех единиц или однократным умножением на 4).

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

Имеем:

R(1)= R(2) = R(3) = 1

R(4) = 2 = R(5) = R(6) = R(7)

R(8) = R(2) + R(7) = 1 + 2 = 3 = R(9) = R(10) = R(11)

R(12) = R(3)+R(11) = 1 + 3 = 4 = R(13)= R(14) = R(15)

R(16) = R(4) + R(15) = 2 + 4 = 6 = R(17) = R(18) = R(19)

R(20) = R(5) + R(19) = 2 + 6 = 8 = R(21) = R(22) = R(23)

R(24) = R(6) + R(23) = 2 + 8 = 10 = R(25) = R(26) = R(27)

R(28) = R(7) + R(27) = 2 + 10 = 12 = R(29) = R(30) = R(31)

R(32) = R(8) + R(31) = 3 + 12 = 15 = R(33) = R(34) = R(35)

R(36) = R(9) + R(35) = 3 + 15 = 18 = R(37) = R(38) = R(39)

R(40) = R(10) + R(39) = 3 + 18 = 21 = R(41) = R(42) = R(43)

R(44) = R(11) + R(43) = 3 + 21 = 24 = R(45) = R(46) = R(47)

R(48) = R(12) + R(47) = 4 + 24 = 28 = R(49) = R(50) = R(51)

R(52) = R(13) + R(51) = 4 + 28 = 32 = R(53) = R(54) = R(55)

 

Ответ: 32.


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