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

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

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

Тогда для исполнителя с командами «$$+1$$» и «$$\times 2$$» выполняется рекуррентная формула:

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

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

Нужно найти число программ, которые из $$1$$ получают $$25$$ и обязательно проходят через $$15$$.

Сначала найдём число программ до $$15$$:

Значит, до числа $$15$$ можно дойти $$26$$ способами.

После числа $$15$$ считаем аналогично, но все предыдущие значения для новых чисел не нужны, поэтому количество программ до каждого следующего числа остаётся равным $$26$$:

Следовательно, число программ, проходящих через $$15$$ и приводящих к $$25$$, равно $$26$$.

Ответ

26