12. У исполнителя Вычислитель две команды, которым присвое ны номера: 122 1 - прибавь 13 2 - умножь на 3. Выполняя первую из них, Вычислитель прибавляет к числу на экране 1, а…
12. У исполнителя Вычислитель две команды, которым присвое ны номера: 122 1 - прибавь 13 2 - умножь на 3. Выполняя первую из них, Вычислитель прибавляет к числу на экране 1, а выполняя вторую, утраивает это число. Какое максимальное количество разных программ, состоя ших из пяти команд, можно составить для этого исполни- теля, Пусть 0 — начальное значение. Какие числа будут получе- ны в результате выполнения всех программ для исполни- теля Вычислитель, состоящих не более чем из четырёх ко- манд? Решение оформите в виде дерева, корневой вершиной которого является начальное значение (число 0), а рёбрам соответствуют команды исполнителя; в вершинах дерева за- пишите результаты выполнения соответствующих программ. Какое наибольшее число будет записано в вершинах третье- го уровня?
Вот решение по заданной трактовке задачи: две команды с номерами 1 и 2:
- 1 — прибавь 13
- 2 — умножь на 3 Начальное значение: 0.
- maximal количество программ из пяти команд
- Каждую позицию между двумя командами можно выбрать либо 1, либо 2.
- Количество таких последовательностей длины 5: 2^5 = 32. Ответ: 32 программы.
- Числа на всех вершинах дерева для программ не более чем из четырех команд Дерево строим так: корень — число 0; ребра помечены командами 1 или 2; вершины содержат результат выполнения соответствующей программы.
Уровень 0 (корень): 0
Уровень 1:
- 1 → 0 + 13 = 13
- 2 → 0 × 3 = 0
Уровень 2 (расширяем каждый узел уровня 1):
- От 13:
- 1 → 13 + 13 = 26
- 2 → 13 × 3 = 39
- От 0:
- 1 → 0 + 13 = 13
- 2 → 0 × 3 = 0
Уровень 3 (расширяем узлы уровня 2 по порядку):
- От 26:
- 1 → 26 + 13 = 39
- 2 → 26 × 3 = 78
- От 39:
- 1 → 39 + 13 = 52
- 2 → 39 × 3 = 117
- От 13:
- 1 → 13 + 13 = 26
- 2 → 13 × 3 = 39
- От 0:
- 1 → 0 + 13 = 13
- 2 → 0 × 3 = 0
Уровень 4 (расширяем узлы уровня 3 по порядку):
- От 39:
- 1 → 39 + 13 = 52
- 2 → 39 × 3 = 117
- От 78:
- 1 → 78 + 13 = 91
- 2 → 78 × 3 = 234
- От 52:
- 1 → 52 + 13 = 65
- 2 → 52 × 3 = 156
- От 117:
- 1 → 117 + 13 = 130
- 2 → 117 × 3 = 351
- От 26:
- 1 → 26 + 13 = 39
- 2 → 26 × 3 = 78
- От 39:
- 1 → 39 + 13 = 52
- 2 → 39 × 3 = 117
- От 13:
- 1 → 13 + 13 = 26
- 2 → 13 × 3 = 39
- От 0:
- 1 → 0 + 13 = 13
- 2 → 0 × 3 = 0
Кратко резюме уровней:
- Уровень 0: 0
- Уровень 1: 13, 0
- Уровень 2: 26, 39, 13, 0
- Уровень 3: 39, 78, 52, 117, 26, 39, 13, 0
- Уровень 4: 52, 117, 91, 234, 65, 156, 130, 351, 39, 78, 52, 117, 26, 39, 13, 0
Наибольшее число, которое встречается на вершинах третьего уровня (уровень 3), равно 117.
Ответы:
- Максимальное количество программ из пяти команд: 32.
- Числа на вершинах дерева для программ до четырех команд перечислены выше (уровни 0–4).
- Наибольшее число на вершинах третьего уровня: 117.
