Проект Эйлера (30 задача) из тех, что решаются в одно действие. Однако, скорость работы программы вполне возможно значительно ускорить.
Узнать больше в телеграм-канале: ProjectEuler++
Удивительно, но существует только три числа, которые могут быть записаны в виде суммы четвертых степеней их цифр:
1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 441 = 14 не считается, так как это – не сумма.
Сумма этих чисел равна 1634 + 8208 + 9474 = 19316.
Найдите сумму всех чисел, которые могут быть записаны в виде суммы пятых степеней их цифр.
Поскольку функция main() получилась довольно-таки объемной, потому решил не “мельчить” и разбить ее на два скриншота.
Алгоритм работы программы в точности соответствует приведенному заданию:
Данный алгоритм, конечно, тоже дает правильный ответ, однако его возможно ускорить
Перед началом работы программы возникает вопрос: до какого числа искать ответ (MAX_NUM – смотрите скриншот выше)?
Можно, конечно, постепенно увеличивать MAX_NUM:
Однако, необходимо гарантированно определить, что после определенного числа ответов не будет. Потому что даже, если в результате такого подбора ответ совпал, то это непроизводительно. Так как проверяются числа, которые в итоге заведомо не могли быть ответом.
Ход рассуждений будет следующим.
Максимальной цифрой в любом месте числа будет девятка. 9^5 = 9*9*9*9*9 = 59049. Потому:
Таким образом видно, что даже максимально возможное семизначное число (9999999) в итоге дает только шестизначное (413343).
Поскольку меньшие семизначные числа дадут еще меньшие суммы цифр, потому среди всех этих чисел не могут быть ответы. В итоге, максимальным числом, теоретически способным выполнить условия задачи, может быть только шестизначное.
Более того, потому оно и не может быть более 6*9^5 = 354294.
В итоге, уточнение диапазона поиска сокращает объем вычислений (относительно 1000000 – в три раза).
В стандартной библиотеке math.h, есть функция pow() для возведения числа в степень. Данная функция обладает обширными возможностями, может возводить в дробные и отрицательные степени, например. Однако за счет расширенной функциональности, работает она медленней, чем могла бы.
В нашем случае нам нужно всего лишь возводить натуральные числа в натуральные степени. Потому в функции число просто перемножается само на себя нужное количество раз (смотрите скриншот).
В итоге, применение такой облегченной и урезанной функции pow() при прочих равных ускорило работу программы на порядок.
Поскольку нам необходимо возводить только в пятую степень и только цифры от 0 до 9, потому вычислим эти значения и сохраним в массив (смотрите выше).
В итоге, чтобы получить пятую степень числа, можно просто обратиться к соответствующей ячейке массива.
Поскольку теперь не нужно повторно вычислять одно и то же, потому ответ вычисляется практически мгновенно.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
