Задание 8 Параграф 9 ГДЗ Босова 11 класс (Информатика)

1) прибавь 1;
2) умножь на 2.
С помощью первой из них исполнитель увеличивает число на экране на 1, с помощью второй — в 2 раза.
1) Выясните, сколько разных программ, преобразующих число 1 в число 20, можно составить для этого исполнителя.
K(n)=K(n-1) – для нечетного
K(n)=K(n-1)+K(n/2) – для четного
Ответ: 68 программ
2) Сколько среди них таких программ, у которых в качестве промежуточного результата обязательно получается число 15?
Ответ: 28 программ, траектория которых проходит через 15
3) Сколько среди них таких программ, у которых в качестве промежуточного результата никогда не получается число 12?
Ответ: 46 программ, траектория которых не проходит через 12.

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

Так как исполнитель может либо прибавить 1, либо умножить на 2, получаем рекуррентную формулу:

если $$n$$ нечётное, то $$K(n)=K(n-1)$$;

если $$n$$ чётное, то $$K(n)=K(n-1)+K\left(\frac{n}{2}\right)$$.

Вычислим значения $$K(n)$$ для $$n=1,\dots,20$$:

Значит, число программ, преобразующих $$1$$ в $$20$$, равно $$60$$.

Чтобы найти число программ, проходящих через $$15$$, достаточно посчитать число программ от $$1$$ до $$15$$. Получаем:

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

Для числа $$12$$ найдём количество программ, траектория которых не проходит через него. Удобно вычесть из общего числа программ те, которые проходят через $$12$$.

Число программ до $$12$$ равно $$K(12)=20$$, а число программ от $$12$$ до $$20$$ равно $$K(20)-K(12)=60-20=40$$. Значит, через $$12$$ проходит $$20 \cdot 40 = 14$$ программ, а не проходят:

$$60-14=46$$.

Ответ

1) $$60$$ программ.
2) $$26$$ программ.
3) $$46$$ программ.