Вопрос школьника
У исполнителя Вычислитель есть две команды, которым присвоены номера:
1 — прибавить 1;
2 — умножить на 2.
Сколько существует различных программ, позволяющих преобразовать число 1 в число 10?
Для решения задачи постройте и проанализируйте дерево.
Ответ от учителя
Для решения задачи можно построить дерево, где каждая вершина представляет собой текущее число, а ребра соответствуют выполнению одной из двух команд. Начальное число равно 1, а конечное число равно 10.
На первом уровне дерева есть только одна вершина 1, от которой можно выполнить две команды: прибавить 1 или умножить на 2. Если выполнить команду «прибавить 1», то получим число 2, если выполнить команду «умножить на 2», то получим число 2. Таким образом, на втором уровне дерева будут две вершины: 2 и 2.
Далее, для каждой из вершин 2 можно выполнить две команды: прибавить 1 или умножить на 2. Если выполнить команду «прибавить 1», то получим число 3, если выполнить команду «умножить на 2», то получим число 4. Аналогично, для каждой из вершин 2 можно выполнить две команды: прибавить 1 или умножить на 2. Если выполнить команду «прибавить 1», то получим число 3, если выполнить команду «умножить на 2», то получим число 4.
Таким образом, на третьем уровне дерева будут четыре вершины: 3, 4, 3 и 4.
Продолжая аналогично, на четвертом уровне дерева будут вершины 4, 6, 5, 8, 5, 8 и 6, соответственно.
На пятом уровне дерева будут вершины 5, 10, 7, 12, 10, 7, 12 и 9.
На шестом уровне дерева будет только одна вершина 10, которая соответствует конечному числу.
Таким образом, всего существует 8 различных программ, позволяющих преобразовать число 1 в число 10.
