Проект Эйлера (38 задача). Данная задача может быть легко решена обычным перебором, однако всегда есть возможность что-то ускорить.
Узнать больше в телеграм-канале: ProjectEuler++
Возьмем число 192 и умножим его по очереди на 1, 2 и 3:
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576Объединяя все три произведения, получим девятизначное число 192384576 из цифр от 1 до 9 (пан-цифровое число). Будем называть число 192384576 объединенным произведением 192 и (1,2,3)
Таким же образом можно начать с числа 9 и по очереди умножать его на 1, 2, 3, 4 и 5, что в итоге дает пан-цифровое число 918273645, являющееся объединенным произведением 9 и (1,2,3,4,5).
Какое самое большое девятизначное пан-цифровое число можно образовать как объединенное произведение целого числа и (1,2, … , n), где n > 1?
Поскольку функция main() получилась объемной, потому чтобы не “мельчить”, решил разбить ее на два скриншота.
Выше было указано, что если начать с числа 9 и перемножать его на множители (1, 2, 3, 4 и 5), то в итоге получим пан-цифровое число 918273645, вполне удовлетворяющее условиям задания. Однако, оно уже описано в условиях задачи, потому заведомо не может быть ответом.
При этом все же можно сделать вывод, что проверять необходимо только числа начинающиеся с 9 (90 – 99, 900 – 999 и т.п.), потому что иные дадут заведомо меньшее итоговое число.
Последнее число, которое может быть основой искомого ответа это 9999. Потому что последующие числа – уже пятизначные и два пятизначных числа дадут уже десятизначное, что превышает лимит в девять цифр.
В программе в итоге будем перебирать ряд чисел от 90 до 9999 и при этом пропускать промежутки, где заведомо нет ответа (100 – 900, 1000 – 9000).
При переборе чисел, каждое из них проверяется на возможность быть ответом. Т.е. при перемножении числа на ряд множителей (1,2,3…) получится ли пан-цифровое число с помощью функции is_pandigital(), описанной ниже.
Если пан-цифровое число формируется, то с помощью функции get_concat_prod() формируется данное объединенное произведение.
Максимальное из них сохраняется как ответ.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Чтобы определить, является ли число пан-цифровым, создадим массив для хранения цифр числа.
При этом цифры будут храниться по индексу:
Тогда по мере внесения цифр в массив, он будет заполняться единицами:
… пока в итоге не заполнится полностью (кроме нуля).
При том функция put_digits(), возвращает количество цифр занесенных в массив.
Если среди цифр не встретился ноль или цифра ранее занесенная в массив, то данное объединенное произведение является пан-цифровым и функция вернет true.
Иначе – false.
Данная функция берет младшую цифру числа:
Проверяет ее отсутствие в массиве (т.е. ячейка с таким индексом равна нулю):
И проверяет, что эта младшая цифра не является нулем:
Если условия соблюдены, то в массив записывается 1 по соответствующему индексу и цифра отрезается.
Иначе, возвращается цифра 10, заведомо превышающая допустимых 9 цифр в числе.
Количество цифр, заносимых в массив, при занесении в массив подсчитывается и (при корректной работе) возвращается в итоге функцией.
Поскольку данная функция работает с числами, из которых заведомо получится пан-цифровое девятизначное число, потому алгоритм работы простой.
Возьмем для примера число, начинающееся с 9:
Как только длина числа достигла девяти (согласно условиям задания), оно возвращается как результат.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
