12. У исполнителя Вычислитель две команды, которым присвое ны номера: 122 1 - прибавь 1 2 - умножь на 3. Выполняя первую из них, Вычислитель прибавляет к числу на экране 1, а…
12. У исполнителя Вычислитель две команды, которым присвое ны номера: 122 1 - прибавь 1 2 - умножь на 3. Выполняя первую из них, Вычислитель прибавляет к числу на экране 1, а выполняя вторую, утраивает это число. Какое максимальное количество разных программ, состоя ших из пяти команд, можно составить для этого исполни- теля, Пусть 0 — начальное значение. Какие числа будут получе- ны в результате выполнения всех программ для исполни- теля Вычислитель, состоящих не более чем из четырёх ко- манд? Решение оформите в виде дерева, корневой вершиной которого является начальное значение (число 0), а рёбрам соответствуют команды исполнителя; в вершинах дерева за- пишите результаты выполнения соответствующих программ. Какое наибольшее число будет записано в вершинах третье- го уровня?
Вот подробное решение задачи с пошаговым разбором и представлением в виде дерева.
Исходные команды:
- 1: прибавь 1
- 2: умножь на 3 Начальное значение: 0
Максимальное количество программ длиной 5 команд Каждая позиция в последовательности из пяти команд может быть либо 1, либо 2. Всего возможностей 2^5 = 32. Значит, максимум разных программ длиной 5 команд — 32.
Программы длины до 4 команд: дерево и результаты
Корень дерева: вершина 0 (начальное значение).
Уровень 1 (после 1 команды)
- 1 → 1
- 2 → 0
Уровень 2 (после 2 команд) Из 1:
- 11 → 2 (0 + 1 + 1)
- 12 → 3 (0 + 1, затем ×3) Из 0 (из второй вершины на уровне 1):
- 21 → 1 (0 + 1)
- 22 → 0 (0 × 3)
Уровень 3 (после 3 команд) Из 11 (значение 2):
- 111 → 3
- 112 → 6 Из 12 (значение 3):
- 121 → 4
- 122 → 9 Из 21 (значение 1):
- 211 → 2
- 212 → 3 Из 22 (значение 0):
- 221 → 1
- 222 → 0
Итак, значения на третьем уровне (после трёх команд) и соответствующие программы:
- 111: 3
- 112: 6
- 121: 4
- 122: 9
- 211: 2
- 212: 3
- 221: 1
- 222: 0
Максимальное число на третьем уровне: 9. Это достигается программой 122 (0 → 1 → 3 → 9).
Уровень 4 (после 4 команд) Раскрываем каждую ветку уровня 3 двумя командами: Из 111 (значение 3):
- 1111 → 4
- 1112 → 9 Из 112 (значение 6):
- 1121 → 7
- 1122 → 18 Из 121 (значение 4):
- 1211 → 5
- 1212 → 12 Из 122 (значение 9):
- 1221 → 10
- 1222 → 27 Из 211 (значение 2):
- 2111 → 3
- 2112 → 6 Из 212 (значение 3):
- 2121 → 4
- 2122 → 9 Из 221 (значение 1):
- 2211 → 2
- 2212 → 3 Из 222 (значение 0):
- 2221 → 1
- 2222 → 0
Максимальное число на четвёртом уровне: 27 (программа 1222).
Кратко резюмируя
- Программы длиной 5 команд: 32 разных программы.
- В разрезе до четырёх команд (включительно) максимальные значения:
- После 3 команд: максимальное 9 (программа 122).
- После 4 команд: максимальное 27 (программа 1222).
Их можно представить в виде дерева следующим образом (ключевые узлы):
- Корень: 0
- 1 → 1
- 2 → 0
- Далее:
- от 1: 11 → 2; 12 → 3
- от 0: 21 → 1; 22 → 0
- Далее на третьем уровне:
- 111 → 3, 112 → 6, 121 → 4, 122 → 9, 211 → 2, 212 → 3, 221 → 1, 222 → 0
- И на четвёртом уровне:
- 1111 → 4, 1112 → 9, 1121 → 7, 1122 → 18, 1211 → 5, 1212 → 12, 1221 → 10, 1222 → 27, 2111 → 3, 2112 → 6, 2121 → 4, 2122 → 9, 2211 → 2, 2212 → 3, 2221 → 1, 2222 → 0
Если нужно, могу представить это в виде более наглядного графического дерева или дать таблицу соответствий (последовательность команд → результат).
