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


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

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

1) прибавь 1,

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

Первая из них увеличивает число на экране на 1, вторая утраивает его.

Программа для Утроителя – это последовательность команд.

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

Решение.

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

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

 

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

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

 

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

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

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

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

Имеем:

R(3)=1

R(6) = R(5) = R(4) = 1 = R(7) = R(8),

R(9) = R(3) + R(6) = 1 + 1 = 2 = R(10) = R(11),

R(12) = R(4)+ R(9)= 1 + 2 = 3 = R(13) = R(14),

R(15) = R(5) + R(12) = 1 + 3 = 4 = R(16) = R(17),

R(18) = R(6) + R(15) = 1 + 4 = 5 = R(19) = R(20),

R(21) = R(7) + R(18) = 1 + 5 = 6 = R(22) = R(23),

R(24) = R(8) + R(21) = 1 + 6 = 7 = R(25) = R(26),

R(27) = R(9) + R(24) = 2 + 7 = 9 = R(28) = R(29),

R(30) = R(10) + R(27) = 2 + 9 = 11 = R(31) = R(32),

R(33) = R(11) + R(30) = 2 + 11 = 13 = R(34) = R(35),

R(36) = R(12) + R(33) = 3 + 13 = 16 = R(37).

 

 

Ответ: 16.