Ответ:
Обозначим команды: «+1» — прибавить 1, «×3» — умножить на 3.
Сжатое представление дерева результатов:
- 0 команд: 0.
- 1 команда: из 0: «+1» → 1, «×3» → 0.
- 2 команды: из 1 получаем 2 и 3; из 0 получаем 1 и 0.
- 3 команды: возможные результаты: 0, 1, 2, 3, 4, 6, 9.
- 4 команды: возможные результаты: 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 18, 27.
Все числа, которые можно получить программами длиной не более четырёх команд:
\(\{0,1,2,3,4,5,6,7,9,10,12,18,27\}\).
На третьем уровне дерева, то есть после выполнения трёх команд, наибольшее значение получается при последовательности команд «×3, ×3, ×3»:
\(0\xrightarrow{\times3}0\xrightarrow{+1}1\xrightarrow{\times3}3\) — не даёт максимума, поэтому рассмотрим наибольшую выгодную последовательность:
\(0\xrightarrow{+1}1\xrightarrow{\times3}3\xrightarrow{\times3}9\).
Ответ: 9.
Обозначим команды: «+1» — прибавить 1, «×3» — умножить на 3.
Сжатое представление дерева результатов:
- 0 команд: 0.
- 1 команда: из 0: «+1» → 1, «×3» → 0.
- 2 команды: из 1 получаем 2 и 3; из 0 получаем 1 и 0.
- 3 команды: возможные результаты: 0, 1, 2, 3, 4, 6, 9.
- 4 команды: возможные результаты: 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 18, 27.
Все числа, которые можно получить программами длиной не более четырёх команд:
\(\{0,1,2,3,4,5,6,7,9,10,12,18,27\}\).
На третьем уровне дерева, то есть после выполнения трёх команд, наибольшее значение получается при последовательности команд «×3, ×3, ×3»:
\(0\xrightarrow{\times3}0\xrightarrow{+1}1\xrightarrow{\times3}3\) — не даёт максимума, поэтому рассмотрим наибольшую выгодную последовательность:
\(0\xrightarrow{+1}1\xrightarrow{\times3}3\xrightarrow{\times3}9\).
Ответ: 9.
