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

Задача

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

Подробный ответ

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

Если рассмотреть дерево, то видно, что левая и правая части повторяются симметрично: правая половина дерева повторяет левую с позиций 3–4. В левой половине получается 7 программ.

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

$$7 \cdot 2 = 14$$

Ответ: 14