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

Задача

Исполнитель Калькулятор имеет следующую систему команд: 1) прибавь 1; 2) умножь на 2. С помощью первой из них исполнитель увеличивает число на экране на 1, с помощью второй — в 2 раза. Выясните, сколько разных программ, преобразующих число 1 в число 20, можно составить для этого исполнителя.
Сколько среди них таких программ, у которых в качестве промежуточного результата обязательно получается число 15?
Сколько среди них таких программ, у которых в качестве промежуточного результата никогда не получается число 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$$:

$$n$$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
$$K(n)$$	1	2	2	4	4	6	6	10	10	14	14	20	20	26	26	36	36	46	46	60

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

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

$$n$$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$$K(n)$$	1	2	2	4	4	6	6	10	10	14	14	20	20	26	26

Следовательно, через число $$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$$.