Пару недель назад, в поисках ответа на задачу, абсолютно не связанную с описываемой здесь, я волею поисковых систем наткнулся на следующий пост: Как сделать из 123456789 число 100 или 0.

Прочитав его, я вспомнил как полгода назад решил такую же, но чуть более глобальную задачу. В этой статье я хотел бы поделиться своим способом решения и дать возможность «поиграться» с алгоритмом. Но сначала немного предыстории.

Предыстория

Давным давно, когда у людей не было смартфонов, в поездках на общественном транспорте каждый развлекал себя как умеет. Одним из таких способов не заскучать была занимательная игра, которая помогала не только скоротать поездку на автобусе, но и немного «расшевелить мозги». Звучит она так. На автобусном билетике есть номер из шести цифр. Необходимо, расставляя между цифрами скобки и знаки математических операций, получить выражение, которое после выполнения операций будет равно 100. Набор операций стандартный: сложение, вычитание, умножение, деление.

Уже не вспомню, кто научил меня этой игре, и кого из своих друзей заразил я, но до сих пор мы периодически любили любим так развлекаться. И вот, полгода назад, мне попался следующий пример.



То ли комбинация оказалась сложной, то ли я на тот момент давно не практиковался, но с этим примером я провозился минут 15. В середине этого времени в голове появилась назойливая мысль, что это число вполне может входить в подмножество, для которых решения не существует. Пример я в итоге решил, но осадочек от осознания, что я мог безрезультатно провозиться несколько часов, остался. Кроме того, даже для конкретного числа, доказать такое свойство будет проблематично (конечно, если вы — не профессор теории чисел). Поэтому я задумал решить эту задачу при помощи программирования.

Решение и алгоритм

Предупреждение. Автор данной статьи не является профессиональным программистом. Однако, он с благодарностью примет полезные советы по улучшению предложенного алгоритма или его реализации.

Решать поставленную задачу мы будем при помощи перебора. При этом перебирать придётся три различных характеристики решения:

1. Различные разбиения исходного числа на подчисла;
2. Для каждого разбиения — различные расстановки операций;
3. Для каждой расстановки операций — различный порядок выполнения операций (расстановки скобок).

Первый цикл

В первом цикле мы будем генерировать очередное разбиение. Для этого представляем произвольное шестизначное число в виде упорядоченного набора цифр с пятью «контейнерами» между ними: 1_2_3_4_5_6. В каждый контейнер мы можем положить либо 1, что будет означать склеивание соседних цифр, либо 0 — соседние цифры будут принадлежать разным числам. Всего существует 2^5 = 32 различных вариантов разбиений, не так уж много. Указанное в примере разбиение кодируется последовательностью 10101.

Перебирать такие варианты можно элементарно — задаём начальное разбиение (00000), и последовательно 31 раз прибавляем к нему единицу в двоичной системе счисления.

Второй цикл

Во втором цикле мы имеем N+1 число и N контейнеров между ними. Можно заметить, что количество контейнеров N определяется количеством нулей в коде разбиения. Но более важно здесь осознание того, что в эти новые контейнеры мы должны разложить различные операции из набора (+, -, *, /). В худшем случае N=5, поэтому наихудшая оценка — 4^5 = 1024 варианта расстановки операций.

Перебирать расстановки операций можно способом, аналогичным предыдущему. Кодируем каждую операцию своим ключом (0, 1, 2, 3), задаём начальный набор операций 00000, и последовательно 4^N — 1 раз прибавляем к нему единицу в четверичной системе счисления.

Третий цикл

И, наконец, в третьем цикле нужно расставить скобки. Конечно же, делать это совсем «в лоб», расставляя скобки как-нибудь и подсчитывая баланс открывающих и закрывающих, мы не будем. Проще заметить, что для тех же N контейнеров нам всего лишь нужно расставить приоритеты выполнения операций. Имеем N операций, необходимо перебрать все упорядоченные расстановки чисел из набора (0, ..., N). Число всех возможных порядков выполнения будет равно N!, в худшем случае 5! = 120.

Перебирать расстановки приоритетов операций можно перебирая различные перестановки цифр в последовательности (0,1,2,3,4). В своей программе я реализовал какой-то неочевидный алгоритм, последовательно меняющий местами цифры в последовательности. (Если бы писал сейчас, скорее всего, реализовал бы что-то более понятное).

Проверка комбинации

Теперь для решения задачи осталось совсем немного — сделать процедуру, которая по набору из трёх кодов и исходного числа вычисляет результат выражения и в случае если результат равен 100, распечатывает закодированное выражение. Перебор всех вариантов для числа с N+1 цифрой в худшем случае подразумевает рассмотрение 2^N ? 4^N ? N! выражений. Для шестизначных чисел это равно 3.9 миллионов выражений. Оценка получается сильно завышенной, поскольку в выражении 4^N ? N! фактически будет не N, а число нулей в первом разбиении.

Заключение

В заключении хочу сделать два замечания.

Во-первых, в моей программе сначала использовались стандартные операции над int. Люди же при решении этой задачи работают в поле рациональных чисел, поэтому многие решения, выдаваемые программой на практике нельзя использовать. Спустя какое-то время я написал свой небольшой модуль с рациональными числами и прикрутил к задаче его.

Во-вторых, в моей программе есть зародыш пятой операции — возведения в степень. Причины, по которым эта операция не реализована следующие. Во-первых, необходимо добавлять некоторый ограничитель для возведения в степень (поскольку число 2^2^2^2^2^2, например, уже не влезет в память). Во вторых, в таком случае вычисления выходят из поля рациональных чисел (например, 2^(1/2)).

Ссылки

Программную реализацию предложенного алгоритма на С++ выкладываю на GitHub.
Кроме того, те, кто не хочет заморачиваться с компиляцией, могут скачать исполняемые файлы для Windows там же из релиза.