Пару недель назад, в поисках ответа на задачу, абсолютно не связанную с описываемой здесь, я волею поисковых систем наткнулся на следующий пост: Как сделать из 123456789 число 100 или 0.
Прочитав его, я вспомнил как полгода назад решил такую же, но чуть более глобальную задачу. В этой статье я хотел бы поделиться своим способом решения и дать возможность «поиграться» с алгоритмом. Но сначала немного предыстории.
Предыстория
Давным давно, когда у людей не было смартфонов, в поездках на общественном транспорте каждый развлекал себя как умеет. Одним из таких способов не заскучать была занимательная игра, которая помогала не только скоротать поездку на автобусе, но и немного «расшевелить мозги». Звучит она так. На автобусном билетике есть номер из шести цифр. Необходимо, расставляя между цифрами скобки и знаки математических операций, получить выражение, которое после выполнения операций будет равно 100. Набор операций стандартный: сложение, вычитание, умножение, деление.
Уже не вспомню, кто научил меня этой игре, и кого из своих друзей заразил я, но до сих пор мы периодически любили любим так развлекаться. И вот, полгода назад, мне попался следующий пример.
То ли комбинация оказалась сложной, то ли я на тот момент давно не практиковался, но с этим примером я провозился минут 15. В середине этого времени в голове появилась назойливая мысль, что это число вполне может входить в подмножество, для которых решения не существует. Пример я в итоге решил, но осадочек от осознания, что я мог безрезультатно провозиться несколько часов, остался. Кроме того, даже для конкретного числа, доказать такое свойство будет проблематично (конечно, если вы — не профессор теории чисел). Поэтому я задумал решить эту задачу при помощи программирования.
Решение и алгоритм
Предупреждение. Автор данной статьи не является профессиональным программистом. Однако, он с благодарностью примет полезные советы по улучшению предложенного алгоритма или его реализации.
Решать поставленную задачу мы будем при помощи перебора. При этом перебирать придётся три различных характеристики решения:
- Различные разбиения исходного числа на подчисла;
- Для каждого разбиения — различные расстановки операций;
- Для каждой расстановки операций — различный порядок выполнения операций (расстановки скобок).
Тогда один из вариантов разбиения на подчисла: 12_34_56.
Вариант расстановки операций: 12+34*56.
Вариант расстановки скобок: (12+34)*56.
Первый цикл
В первом цикле мы будем генерировать очередное разбиение. Для этого представляем произвольное шестизначное число в виде упорядоченного набора цифр с пятью «контейнерами» между ними: 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)).
Ссылки
Программную реализацию предложенного алгоритма на С++ выкладываю на Git.
Кроме того, те, кто не хочет заморачиваться с компиляцией, могут скачать исполняемый файл 64-битной версии отсюда.
Автор: ltvlx
