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

Задача

1 — прибавить 1;
2 — умножить на 2.
Сколько существует различных программ, позволяющих преобразовать число 1 в число 10?
Для решения задачи постройте и проанализируйте дерево.
Правая половина дерева повторяет левую с позиций 3 – 4. В левой половине 7 программ. Всего программ: 7*2 = 14
Ответ: 14

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

Построим дерево всех возможных программ, которые переводят число $$1$$ в число $$10$$. У исполнителя две команды:

$$1$$ — прибавить $$1$$;
$$2$$ — умножить на $$2$$.

Из числа $$1$$ можно получить $$2$$ двумя способами: командой $$+1$$ и командой $$\times 2$$. Далее дерево продолжается. При анализе видно, что правая половина дерева повторяет левую с позиций $$3$$–$$4$$, поэтому число программ в правой части такое же, как в левой.

В левой половине дерева получается $$7$$ программ. Тогда всего программ:

$$7 \cdot 2 = 14$$