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


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

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

 

1. прибавь 1,

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

 

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

Решение.

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

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 = 3 R(n) = 1 (один способ: прибавлением единицы). Поэтому достаточно вычислить значения R(n) для всех чисел, кратных 3 и не превосходящих 34. Имеем:

 

R(6)= 2 = R(7),

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

R(12) = R(4) + R(11) = 1 + 3 = 4 = R(13),

R(15) = R(5) + R(14)= 1 + 4 = 5 = R(16),

R(18) = R(6) + R(17) = 2 + 5 = 7 = R(19),

R(21) = R(7) + R(20) = 2 + 7 = 9 = R(22),

R(24) = R(8) + R(23) = 2 + 9 = 11 = R(25),

R(27) = R(9) + R(26) = 3 + 11 = 14 = R(28),

R(30) = R(10) + R(29) = 3 + 14 = 17 = R(31),

R(33) = R(11) + R(32) = 3 + 17 = 20 = R(34).

 

Ответ: 20.

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Ва­ри­ант 501.