Есть неплохое упражнение для занятия в детском математическом кружке для учеников разных возрастов: собирание циферблата часов из всяких дико-выглядящих формул. Разнообразные варианты гуляют по сети и их нетрудно отыскать и разобраться в них. Множество примеров приведено тут.
Есть и мой собственный вариант, в котором все числа собраны ровно из трёх двоек:
Надо заметить, это ограничение (использовать только три двойки) достаточно жёсткое, поскольку 2+2 = 2*2 = 2², о чём мы говорили в прошлой статье:
Впрочем, ровно трёх двоек достаточно для выражения любого натурального числа, если использовать традиционное обозначение для квадратного корня. Так, например, можно выразить число 13:
Это прикольно, конечно, но смысл в таком занятии будет только если оно научит нас чему-то полезному. Например, систематическому подходу к постановке и решению задачи, элементам теории вычислений и формальных грамматик. Для этого мы зададимся более общим вопросом:
Какие числа можно представить корректными выражениями использующими заданный набор чисел (цифр) и арифметических операций?
Поиск ответа на него будет интересен и полезен старшеклассникам, увлекающимся программированием. Оно позволит освежить в памяти кое-какую комбинаторику, принципы динамического программирования, и познакомит с универсально полезным способом организации вычислений: простейшей стековой машиной.
Поехали!
Общий язык
Решение задачи генерации всевозможных арифметических выражений лучше всего предоставить компьютеру. А для этого нужно как-то объяснить ему какими бывают эти самые арифметические выражения.
Можно использовать традиционную запись, но это будет неудобно, поскольку разные приоритеты операций и скобки усложняют как генерацию, так интерпретацию выражений. Самое общее решение дадут абстрактные синтаксические деревья, но ради нехитрой задачи лень возиться со сложными структурами данных. Мне кажется полезным и поучительным воспользоваться для этой задачи постфиксной или обратной польской нотацией (ОПН). Она позволяет превратить сложное древообразное выражение в линейный список операндов и операций (в простую строку), который может быть однозначно вычислен элементарным вычислителем.
Вычисления выражений, представленных в такой форме, может произвести простая стековая машина или автомат с магазинной памятью. В ходе вычислений она по очереди перебирает входные символы (слова). Встречающиеся при этом числа машина помещает в стек, а операции выполняет с двумя верхними числами на стеке, помещая результат на его вершину.
Например, выражение "(3+1)*2" в обратной польской записи будет записано как "3 1 + 2 *", а вычисляется эта цепочка таким образом:
Стоящая перед нами задача содержит в себе генерацию всех корректных выражений в ОПН нужного объёма.
Выражения могут быть и некорректными, например, операции может не хватить операндов на стеке, либо в результате вычислений на стеке может остаться несколько лишних значений. Таким образом, не всякий набор чисел и операций может быть вычислен. Заведомо корректное арифметическое выражение, состоящее из бинарных операций, можно построить как бинарное дерево. Но для этого нет необходимости строить само дерево в памяти. Древообразным (рекурсивным) может быть процесс генерации выражения.
В качестве языка для общения с компьютером мы воспользуемся Julia, похожим на Python, но более строгим и, если можно так сказать, математичным.
Вот программа, которая генерирует шаблоны корректных выражений с бинарными операциями в обратной польской записи, обходя (но не строя) все возможные бинарные деревья заданной глубины:
Здесь используется синтаксис для генерации списков, который мы будем использовать в этой статье повсеместно. Цепочка из конструкций for ... in ... в приведённом выше примере реализует паттерн функционального программирования, который называется монада List. Он позволяет производить вычисления с величинами, принимающими множество значений (либо ни одного), и организовывать комбинаторный перебор, отсекая при необходимости ненужные варианты.
В получаемых шаблонах символ # будет обозначать число, а точка -- какую-нибудь арифметическую операцию. Давайте посмотрим какими эти шаблоны получаются:
Количество таких выражений растёт с глубиной, образуя известную последовательность чисел Каталана:
Полезно разобраться какие выражения и деревья соответствуют тем или иным шаблонам выражений в ОПН.
Теперь надо как-то заполнить сгенерированные шаблоны конкретными значениями и знаками. Для этого напишем простую функцию subst, подставляющую вместо символов # и • заданные значения из переданных ей списков.
Обратите внимание на то, что функция возвращает результат, "завёрнутый" в список из одного элемента в случае удачной подстановки, и пустой список, если подстановка по какой-то причине не удалась (например, шаблону не хватило аргументов). Это нам пригодится в дальнейшей организации вычислений.
Отлично! Теперь мы способны перечислить все корректные арифметические выражения в ОПН, состоящие из трёх двоек и двух операций:
Здесь функция combinations(lst, n) возвращает все возможные комбинации элементов заданного списка длины n:
А вот так строятся все арифметические выражения для множества чисел от 1 до 3, причём так, чтобы каждое число встретилось в выражении только один раз:
Здесь, для того, чтобы числа в выражении не повторялись, перебираются не комбинации, а перестановки:
Учим машину понимать написанное
Грамматическая часть задачи решена. Теперь давайте напишем универсальную стековую машину для интерпретации строковых выражений, записанных в обратной польской нотации:
Как видно, это лево-ассоциативная свёртка (катаморфизм) с функцией-интерпретатором, обернутся в блок try-catch. Если что-то пойдёт не так, например, случится деление на ноль или не целочисленное деление, машина просто отбросит это выражение, как негодное, не сломавшись.
Интерпретатор для калькулятора прост и почти прямолинеен:
Давайте проверим работу нашей машины на простом примере:
Постфиксная нотация хороша для машин, а нам, людям, привычнее инфиксная запись, в которой операция записывается между операндами. Для стековой машины нетрудно написать простой интерпретатор-переводчик арифметических выражений из постфиксной нотации в инфиксную (без приоритетов). Вот как может выглядеть такой переводчик:
Он пригодится нам для того, чтобы понимать получаемые решения.
Вот что у нас получается
Теперь мы готовы к исследованию поставленной задачи. Для начала перечислим все положительные числа, которые можно получить, оперируя тремя двойками:
И все положительные числа, собираемые из 1, 2 и 3, используя их по одному разу:
Давайте теперь построим функцию, которая перечисляет все арифметические выражения для заданного числа, используя заданный набор термов:
Здесь есть два нюанса. Во-первых, обратите внимание на то, что значение k тоже задаётся конструкцией for, что позволяет не нарушать монадический подход. А во-вторых, вся конструкция окружена не квадратными скобками, порождающими список, а круглыми, при этом конструируется ленивый генератор списка. Вот как можно его использовать:
Функция collect собирает из генератора список. А, например, с помощью функции first можно получить только первый вариант, не вычисляя все остальные.
Наконец, напишем функцию, которая ищет пример выражения с минимальным количеством одинаковых термов для представления указанного числа.
Минимальное выражение ищется методом поиска в ширину по огромному дереву всевозможных арифметических выражений.
С её помощью легко найти выражения для циферблатов, в которых каждое число построено с помощью минимального количества одинаковых однозначных чисел и простейшей арифметики.
В этих выражениях нетрудно разглядеть определённую систему.
Мы не использовали унарных операций, таких как факториал, или округление, хотя они здорово расширили бы диапазон выразимых чисел. Добавить их обработку в интерпретатор calc совсем несложно. Сложнее дело обстоит с корректной генерацией выражений, поскольку унарные операции могут применяться к одному числу или результату вычислений многократно. Это означает, что число выражений, задействующих конечное число термов (конечных элементов, чисел) становится бесконечным и нужно искусственно ограничивать глубину выражений.
Любопытные читатели могут поиграть с кодом здесь.