Задача
Каждое n-значное число, которое содержит каждую цифру от 1 до n ровно один раз, будем считать пан-цифровым; к примеру, 5-значное число 15234 является пан-цифровым, т.к. содержит цифры от 1 до 5.
Произведение 7254 является необычным, поскольку равенство 39 × 186 = 7254, состоящее из множимого, множителя и произведения является пан-цифровым, т.е. содержит цифры от 1 до 9.
Найдите сумму всех пан-цифровых произведений, для которых равенство "множимое × множитель = произведение" можно записать цифрами от 1 до 9, используя каждую цифру только один раз.
ПОДСКАЗКА: Некоторые произведения можно получить несколькими способами, поэтому убедитесь, что включили их в сумму лишь единожды.
Решение
Видится так, что нужно взять все возможные перестановки цифр от 1 до 9 и в каждой перестановке перебрать множители, которые могли бы дать панцифровое произведение.
Но так как перебор множителей тоже надо организовывать, то можно начать прямо с него. То есть взять цикл по одному множителю типа от 1 до 9999, а в нём цикл от 1 до 9999 по другому, и перемножать их с проверкой произведения.
Единственное, что нужно обеспечить – чтобы цифры в одном и другом множителе никогда не повторялись. Для этого надо опять-таки воспользоваться перестановками цифр.
Я поднял код перестановок из предыдущей задачи:
Но он и тогда мне не нравился, так как вышел слишком громоздкий, отчасти потому, что было надо вести подсчёт вариантов аж в трёх местах.
В данной задаче количество вариантов считать не надо, вместо этого нужны сами перестановки на каждом шаге, и поэтому рекурсивный алгоритм не годится. Нужен генератор, который будет помнить своё состояние и при каждом запросе будет выдавать следующую перестановку.
Я сделал быстрый тест перебора для трёхзначных чисел c цифрами от 1 до 3:
И результат:
123 132
213 231
312 321
Работает, но в таком виде оно малополезно, так как во-первых циклы задаются фиксированно, и во-вторых, в каждом внутреннем цикле нужно проверять совпадение со всеми предыдущими, т.е. количество сравнений растёт.
Поэтому ставлю такую подзадачу:
- Сделать генератор, который начинает перебор в одном разряде, затем добавляет второй разряд, делает опять перебор, добавляет третий разряд и т.д. сколько угодно раз.
- Генераторов может быть много, и каждый из них должен быть в курсе, какие цифры уже используются другими, чтобы не повторять их.
Теперь нужно декомпозировать.
- Цифры, несмотря на то, что идут по порядку от 1 до 9, в общем случае могут быть совершенно произвольными значениями, поэтому из этих произвольных значений делается пул:
char pool[MAX_LEN] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; - Далее, чтобы знать, какая цифра (а точнее, какая позиция в пуле) уже занята, добавляем маску занятости:
char pool_mask[MAX_LEN] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
Нужен метод получения из пула первого незанятого элемента, начиная с нужной позиции.
Ввиду строгой типизации языка C мы не можем определить, что вернёт такой метод – то ли реально значение из пула, то ли false, в случае если он не смог ничего найти.
Зачастую применяют такой лайфхак: если вернулось отрицательное число, или число вне валидного диапазона, значит это ошибка, а иначе это нужное нам значение. Но поступим мудрее и введём свой тип – структуру Result:
В ней есть поле success, которое и будет обозначать успех, и второе поле val, которое можно использовать только в случае, если success == 1.
Теперь наконец можно написать метод получения элемента из пула:
В метод передаётся позиция start. Если маска pool_mask в этой позиции ненулевая, элемент уже занят и мы увеличиваем start на 1 и снова пытаемся получить элемент. Получив элемент, сразу помечаем его в маске как занятый.
Теперь можно перейти к самим генераторам.
Генератор это также структура, которая имеет поле длины len (сколько разрядов в числе) и массив digits для хранения разрядов. Хранятся не непосредственно значения, а позиции в пуле значений.
Метод для инициализации генератора. Устанавливаем длину в 1 разряд и ищем для этого разряда первый незанятый элемент в пуле:
Проверим, что получилось на данный момент:
Стартуют два генератора, при этом у первого задаётся позиция в пуле 0, а у второго 1, так как 0 уже занята. Пока всё хорошо.
Делаем метод для получения следующего значения из генератора:
Самый главный и пухлый метод в программе. Он по факту отображает состояния вложенных циклов на элементы массива. Первый элемент массива digits это значение внешнего цикла, второй это внутренний цикл и т.д.
Циклы двигаются вручную. В первой части метода:
Мы берём последний разряд и пытаемся увеличить его путём поиска следующей свободной позиции в пуле. Если она найдена, то данный этап заканчивается с имеющимся результатом в переменной res.
Если же она не найдена, мы переходим на предпоследний разряд и пытаемся увеличить его и т.д.
В конце концов этот этап заканчивается с позицией len на том разряде, где мы остановились, и результатом res.
Во второй части:
Если результата не было, значит мы дошли до самого первого разряда (то есть закончился самый внешний цикл), и нужно а) увеличить количество разрядов и б) начать текущий, то есть самый первый разряд с нуля, для чего переполучаем res.
В третьей части:
Ставим значение res в текущий разряд. Затем все следующие разряды "обнуляем" путём записи в них минимально доступных значений из пула.
Таким образом генератор может наращивать разряды хоть до бесконечности.
Вспомогательный метод для получения текущего значения генератора, складывающий разряды:
Вспомогательный метод для освобождения занятых генератором значений в маске пула. Это требуется при перезапуске генератора:
Теперь, имея весь инструментарий, можно организовать циклы для двух множителей.
Циклы ограничены достижением генератором длины в 5 разрядов. Перебирая значения gen1 и gen2, получаем их произведение product. Тут можно вставить дополнительные фильтры, отсекающие заведомо неподходящие варианты, но я этого не стал делать ради краткости.
Окончальная проверка производится в методе is_pan():
Здесь мы разлагаем product на разряды путём деления на 10, и каждый разряд ищется в массиве pool. Найти нужно позицию в массиве, поэтому приходится делать перебор:
И здесь нам тоже пригодился тип Result.
Если разряд вообще не найден (например, это 0), то естественно сразу происходит возврат. Также происходит возврат, если в маске pool_mask эта позиция уже занята. Но если она не занята, мы пока не можем радоваться. В product могут быть два одинаковых разряда. Поэтому мы дополнительно помечаем позиции, которые занимает product, в отдельном массиве product_mask. Одновременно с пометкой уменьшаем счётчик оставшихся позиций. Для этого в метод передаётся параметр target_len, который вычисляется так: из общей длины MAX_LEN вычитаются длины обоих множителей, и то, что осталось, должно заполниться разрядами product. Поэтому в конце метода длина target_len должна стать равна нулю, если всё прошло удачно.
Ну и как всегда, чтобы не считать те числа, которые уже были, используется массив cache. Я уже не стал тут ничего мудрить, тем более что памяти тратится не сильно страшно.
Ссылка на онлайн-компилятор языка C с текстом программы
Подборка всех задач: