Проект Эйлера (34 задача). Даже такую несложную задачу можно при желании оптимизировать, а время ее выполнения – ускорить.
Узнать больше в телеграм-канале: ProjectEuler++
145 является любопытным числом, поскольку 1! + 4! + 5! = 1 + 24 + 120 = 145.
Найдите сумму всех чисел, каждое из которых равно сумме факториалов своих цифр.
Примечание: поскольку 1! = 1 и 2! = 2 не являются суммами, учитывать их не следует.
Поскольку задача довольно таки несложная, потому все решение уместилось в функции main(). Однако, чтобы не “мельчить”, решил разбить ее на два скриншота.
Как указано в задании, необходимо найти сумму всех чисел, удовлетворяющих условию. Потому возникает резонный вопрос: до какого числа проверять, а точнее, после какого числа гарантированно не может быть ответа?
Максимальной цифрой, которую может содержать число в десятичной системе счисления является девять. Ее факториал:
… т.е. шестизначное число.
Самое большое шестизначное число будет также состоять из девяток:
Сумма факториалов его цифр составит:
… семизначное число в итоге.
В свою очередь сумма факториалов семизначного числа может быть максимум:
…что является также семизначным числом.
Вычислим то же самое для восьмизначного числа:
Видно, что поскольку максимальная сумма факториалов цифр восьмизначного числа является числом семизначным, потому такие числа не могут уже содержать ответов.
И в итоге проверять числа стоит только до 2540160, потому что именно его дает сумма из 7 факториалов 9! (смотрите скриншот выше).
В процессе работы программы значение факториалов чисел от 0 до 9 нам понадобится многократно. Потому разумно будет их один раз вычислить и сохранить.
Для хранения факториалов чисел будем использовать массив, потому что это позволяет обращаться к значению по индексу.
Значение 0! = 1 вносим в массив при его инициализации (смотрите выше скриншот). Значения факториалов вносим за один проход цикла for().
Как было указано выше, перебираем числа до максимально возможного (7 * 9!). Каждое из чисел необходимо проверить на соответствие условиям задания:
Если в итоге находится искомое число, то оно суммируется к ответу.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
