12. У исполнителя Вычислитель две команды, которым присвоены номера: 1 — прибавь 1; 2 — умножь на 3. Выполняя первую из них, Вычислитель прибавляет к числу на экране 1, а выполняя вторую, утраивает это число. Какое максимальное количество разных программ, состоящих из пяти команд, можно составить для этого исполнителя? Пусть 0 — начальное значение. Какие числа будут получены в результате выполнения всех программ для исполнителя Вычислитель, состоящих не более чем из четырёх команд? Решение оформите в виде дерева, корневой вершиной которого является начальное значение (число 0), а рёбрам соответствуют команды исполнителя; в вершинах дерева запишите результаты выполнения соответствующих программ. Какое наибольшее число будет записано в вершинах третьего уровня?
Ответ
Для составления программы из пяти команд, у нас есть две возможности для каждой команды: прибавить 1 или умножить на 3. Таким образом, общее количество разных программ можно рассчитать как 2 в степени 5 (2^5 = 32).
Далее, я построю дерево для программ, состоящих не более чем из четырех команд, чтобы определить числа, которые будут получены при выполнении этих программ:
Вершины дерева представляют числа, полученные после выполнения программы, а ребра соответствуют командам исполнителя. Чтобы выяснить числа, полученные в результате выполнения программы на третьем уровне, нам нужно рассмотреть всех потомков вершин второго уровня.
Из дерева видно, что наибольшее число, которое будет записано в вершинах третьего уровня, равно 39.
Таким образом, наибольшее число, которое будет записано в вершинах третьего уровня, равно 39.