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

Задача

1 — прибавь 1;
2 — умножь на 3.
Выполняя первую из них, Вычислитель прибавляет к числу на экране 1, а выполняя вторую, утраивает это число.
Какое максимальное количество разных программ, состоящих из пяти команд, можно составить для этого исполнителя?
Пусть 0 — начальное значение. Какие числа будут получены в результате выполнения всех программ для исполнителя Вычислитель, состоящих не более чем из четырёх команд? Решение оформите в виде дерева, корневой вершиной которого является начальное значение (число 0), а рёбрам соответствуют команды исполнителя; в вершинах дерева запишите результаты выполнения соответствующих программ. Какое наибольшее число будет записано в вершинах третьего уровня?
Количество программ, состоящих из 2-х возможных, равно 32 (25)
На рисунке ниже показано количество программ из 4-х команд.
Наибольшее число, полученное на 3-ем уровне – 27.

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

У исполнителя две команды, значит на каждом шаге есть 2 варианта выбора. Тогда число различных программ длиной 5 команд равно:

$$2^5 = 32$$

Теперь рассмотрим все результаты, которые можно получить из числа $$0$$ не более чем за 4 команды.

Построим дерево значений:

0
├─ $$+1$$ → 1
│  ├─ $$+1$$ → 2
│  │  ├─ $$+1$$ → 3
│  │  └─ $$\times 3$$ → 6
│  └─ $$\times 3$$ → 3
│     ├─ $$+1$$ → 4
│     └─ $$\times 3$$ → 9
└─ $$\times 3$$ → 0
    ├─ $$+1$$ → 1
    │  ├─ $$+1$$ → 2
    │  └─ $$\times 3$$ → 3
    └─ $$\times 3$$ → 0
        ├─ $$+1$$ → 1
        └─ $$\times 3$$ → 0

На третьем уровне дерева наибольшее число получается при последовательности команд $$+1, +1, +1$$:

$$0 \to 1 \to 2 \to 3$$

Значит, наибольшее число в вершинах третьего уровня равно $$3$$.

Если учитывать все программы не более чем из 4 команд, то возможные числа в вершинах дерева: $$0, 1, 2, 3, 4, 6, 9, 12, 18, 27$$.