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

Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, утраивает число на экране. Сколько существует программ, для которых при исходном числе 1 результатом является число 25?
K(n)=K(n-2)+K(n/3) – если n делится на 3
K(n)=K(n-2) – если n не делится на 3
Ответ: 8

Обозначим через $$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