У исполнителя Удвоитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 2.
Первая из них увеличивает число на экране на 1, вторая удваивает. Программа для Удвоителя — это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 24?
Пояснение.Обозначим R(n) — количество программ, которые преобразуют число 2 в число n. Обозначим t(n) наибольшее кратное 2, не превосходящее n. Заметим, что мы можем получить только числа, кратные 2 или 3.
Верны следующие соотношения:
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 > 6). При n = 4 R(n)) = 1 (один способ: прибавлением единицы). Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных 3 и не превосходящих 24.
Имеем:
R(4)= 1 = R(5),
R(6) = 2 = R(7),
R(8) = R(4)+R(6)= 1 + 2 = 3 = R(9),
R(10) = R(5) + R(8) = 1 + 3 = 4 = R(11),
R(12) = R(6) + R(10) = 2 + 4 = 6= R(13),
R(14) = R(7) + R(12) = 2 + 6 = 8 = R(15),
R(16) = R(8) + R(14) = 3 + 8 = 11 = R(17),
R(18) = R(9) + R(16) = 3 + 11 = 14 = R(19),
R(20) = R(10) + R(18) = 4 + 14 = 18 = R(21),
R(22) = R(11) + R(20) = 4 + 18 = 22 = R(23),
R(24) = R(12) + R(22) = 6 + 22 = 28.
Ответ: 28.
Ответ: 28
Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Сибирь. Вариант 1.