Упр.3.44 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)

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

Построим дерево всех возможных программ от числа $$1$$ к числу $$10$$. Из каждой вершины можно перейти либо по команде $$+1$$, либо по команде $$\times 2$$, если результат не превышает $$10$$.

Рассмотрим левую половину дерева — все программы, начинающиеся с команды $$+1$$. Таких программ получается $$7$$.

Правая половина дерева повторяет левую, начиная с позиций $$3$$–$$4$$, поэтому число программ в правой части тоже равно $$7$$.

Тогда общее число различных программ:

$$7 \cdot 2 = 14$$

Ответ: 14