Задание №98 ЕГЭ Информатике

Искомое количество программ равно количеству программ, получающих из числа 1 число 27. Траектория вычислений не должна содержать чисел 10 и 11 и должна содержать число 8.

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

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

1. R(n) = R(n−1) + R(n−2) + R(n/3) — если n делится на три, при n > 2.

2. R(n) = R(n−1) + R(n−2) — если n не делится на три, при n > 2.

 

R(1) = 1.

R(2) = 1.

R(3) = R(2) + R(1) + R(1) = 3.

R(4) = R(3) + R(2) = 4.

R(5) = R(4) + R(3) = 7.

R(6) = R(5) + R(4) + R(2) = 12.

R(7) = R(6) + R(5) = 19.

R(8) = R(7) + R(6) = 31.

 

Программ, получающих из числа 8 число 27 всего 4: 3111, 312, 321 и 13.

Таким образом, количество программ, удовлетворяющих условию задачи, равно 31 · 4 = 124.

 

Ответ: 124.