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


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

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

 

1. прибавь один,

2. умножь на полтора.

 

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

Решение.

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

 

Верны следующие утверждения:

 

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

 

2. Если n делится на 1,5 и результат деления — чётное число, тогда R(n) = R(n / 1,5) + R(n − 1). Достаточно вычислить все значения R(n). Заметим, что R от четного числа всегда равно нулю. R от числа, которое после вычитания 1 не кратно 2, тоже равно нулю.

 

R(2) = 1,

R(3) = 2 (можно умножить двойку на 1,5 или прибавить 1 к единице),

R(4) = R(3) = 2,

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

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

...

R(9) = R(6) + R(8) = 4 + 4 = 8,

...

R(12) = R(8) + R(11) = 4 + 8 = 12,

...

R(15) = R(10) + R(14) = 8 + 12 = 20,

...

R(18) = R(12) + R(17) = 12 + 20 = 32,

...

R(20) = R(19) = 32.

 

Ответ: 32.