Задание 2 Вариант 1 Самостоятельная работа 6 ГДЗ Рабочая тетрадь Босова 11 класс (Информатика)

1. У исполнителя «Калькулятор» две команды, которым присвоены номера: 1 — прибавь 2; 2 — умножь на 3. Выполняя первую из них, «Калькулятор» прибавляет к числу на экране 2, а выполняя вторую, утраивает число на экране. Сколько существует программ, для которых при исходном числе $$1$$ результатом является число $$25$$?

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

Тогда для исполнителя с командами «прибавь 2» и «умножь на 3» получаем рекуррентные соотношения:

$$K(n)=K(n+2)+K(3n)$$ — если из $$n$$ можно перейти к обоим следующим состояниям;

удобнее считать в обратном направлении от числа $$25$$ к началу:

$$K(n)=K(n-2)+K\!\left(\frac{n}{3}\right)$$ — если $$n$$ делится на 3,

$$K(n)=K(n-2)$$ — если $$n$$ не делится на 3.

Заполним значения последовательно от $$1$$ до $$25$$. Нужное значение — $$K(1)$$.

Следовательно, $$K(1)=8$$.

Ответ

8