Проект Эйлера (32 задача) может быть решена и простым перебором. Однако мы пойдем другим путем и получим ответ менее чем за 0.1 секунды.
Узнать больше в телеграм-канале: ProjectEuler++
Каждое n-значное число, которое содержит каждую цифру от 1 до n ровно один раз, будем считать пан-цифровым; к примеру, 5-значное число 15234 является пан-цифровым, т.к. содержит цифры от 1 до 5.
Произведение 7254 является необычным, поскольку равенство 39 × 186 = 7254, состоящее из множимого, множителя и произведения является пан-цифровым, т.е. содержит цифры от 1 до 9.
Найдите сумму всех пан-цифровых произведений, для которых равенство “множимое × множитель = произведение” можно записать цифрами от 1 до 9, используя каждую цифру только один раз.
ПОДСКАЗКА: Некоторые произведения можно получить несколькими способами, поэтому убедитесь, что включили их в сумму лишь единожды.
Измеряем время работы программы
Получение перестановок цифр в числе
Поскольку функция main() получилась довольно-таки объемной, потому решил не “мельчить” и разбить ее на два скриншота.
Вариант с простым перебором чисел и их последующей проверке условиям задания подробно рассматривать не будем.
Главная его проблема – в количестве этих чисел. Поскольку всего в данных пан-произведениях должно быть девять чисел (от 1 до 9), потому будут возможны следующие сочетания множителей:
Видно, что в итоге один из множителей может быть четырехзначным. И потому придется перебирать два множителя от 1 до 10000. Что в итоге уже составит сто миллионов комбинаций. А ведь их нужно еще перемножать и считать в них цифры (и в их произведении тоже).
Более перспективным является перебор не чисел, а перестановок цифр в числе. Потому что, если первой перестановкой будет являться 123456789, а последней – 987654321, то это составит всего 9! комбинаций (около 360000).
Более того, чтобы избежать лишних преобразований перестановки будем осуществлять прямо в массиве:
[0,1,2,3,4,5,6,7,8,9]
…
[0,9,8,7,6,5,4,3,2,1]
Перестановки будут получаться в цикле while() с помощью функций increase_indx_num() и get_pandig_num(). При этом первый ноль в массиве нужен будет для проверки окончания перебора цифр. Подробнее о перестановках, ниже, в описании соответствующих функций.
Получив очередную перестановку цифр в массиве (смотрите скриншот выше):
… в двух циклах for() из цифр массива формируются два множителя: num1 и num2.
Они перемножаются 4* 8 и их произведение (32) начинает по одной цифре сравниваться со следующими цифрами массива:
Поскольку они не совпадают, потому num2 увеличивается, включая в себя следующую цифру:
Их произведение 4 * 38 = 152 сравнивается таким же образом (2 c [7]).
После этого num2 опять увеличивается:
Не будем тут расписывать – опять не подойдет.
Вот их произведение уже даст 4*1738 = 6952 и совпадет с массивом [2,5,9,6]. Обратите внимание, что цифры в числе 6952 сравниваются, начиная с младшего разряда (2->5->9->6).
В задании предупреждали, что возможны разные комбинации множителей, дающих одинаковый результат. Потому сохраним наш результат в массиве по индексу:
Перед сохранением нового результата, в итоге, достаточно обратиться к массиву по соответствующему индексу, чтобы проверить, не было ли такого ответа ранее.
Также результат засчитывается, только если произведение точно укладывается в массив:
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
123 -> 132 -> 213 ->231 -> 312 ->321
Однако как понять, почему цифры переставляются именно таком порядке?
Рассмотрим, как формируется первая (нулевая) выборка цифр – 123 (Рисунок 1):
- [1,2,3] забираем 1 arr[0]
- [2,3] забираем 2 arr[0] – не arr[1]!!!
- [3] забираем 3 arr[0] – не arr[2]!!!
Если остальные числа перестановки чисел 1 2 3 преобразовать подобным образом, вся перестановка обретает смысл и становится видна логика перестановки:
В итоге мы получаем шесть искомых перестановок в виде чисел-из-индексов. При этом нулевая перестановка будет 000, а последняя, пятая – 210 (Рисунок 2). Однако нужно понимать ряд особенностей такой системы:
Например, для 4-й перестановки цифр 123, мы получаем число-из-индексов 200 (смотрите рисунок 2). Далее чтобы получить искомое значение перестановки промежуточное число 200 трансформируется следующим образом:
В итоге мы имеем следующую цепочку:
Поскольку, как указано выше, последняя ячейка всегда имеет значение 0, потому при получении следующего промежуточного числа сразу увеличиваем предпоследнюю ([LEN_ARR – 2]) ячейку:
При этом для (9-значных чисел) максимально возможным промежуточным числом будет:
Если это число еще увеличить, то получим:
… ненулевое значение в левой ячейке. Это в итоге послужит сигналом о превышении длины числа.
Именно по этому сигналу в программе останавливается перебор комбинаций цифр.
Способом, описанным выше данная функция получает из промежуточного числа искомую перестановку.
Из отсортированного массива берется число с соответствующим индексом, а остальные числа смещаются.
Также как и в предыдущей функции здесь предусмотрен сигнал о превышении длины 9-значного числа.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
