Проект Эйлера (29 задача) столкнет Вас с типичными проблемами больших чисел. Однако, вполне возможно получить ответ менее чем за 0.1 секунды.
Узнать больше в телеграм-канале: ProjectEuler++
Рассмотрим все целочисленные комбинации ab для 2 ≤ a ≤ 5 и 2 ≤ b ≤ 5:
22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125Если их расположить в порядке возрастания, исключив повторения, мы получим следующую последовательность из 15 различных членов:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
Сколько различных членов имеет последовательность ab для 2 ≤ a ≤ 100 и 2 ≤ b ≤ 100?
Поскольку функция main() получилась довольно-таки объемной, потому решил не “мельчить” и разбить ее на два скриншота.
Чтобы была возможность оперативно менять значения без поиска по всему коду, потому пределы вычислений BASE (последнее число) и POW (самая большая степень) записал через #define. Кроме того, это позволяет использовать эти значения в функциях без передачи их в качестве аргументов.
Для хранения чисел использовал двумерный массив arr[BASE * POW][BASE + 1] (смотрите выше на фото). Потому что 100 (BASE ) чисел в 100 (POW) степенях могут дать 10000 чисел, и нам понадобится столько же массивов длиной также 101. Чтобы такой большой массив не переполнял стек, воспользуемся static для размещения его в основной памяти компьютера.
Чтобы понять суть проблемы работы с большими числами, приведенными в задании, приведу пример.
Так 21 в степени 7 это 1801088541 и его можно хранить как int. Однако 100 в степени 100 – это уже 200-значное число. Как такие числа хранить, в виде массива цифр?
Если 21^7 (1801088541 ) в массиве будет выглядеть как ряд цифр [1,8,0,1,0,8,8,5,4,1], то как будет выглядеть умножение? При возведении в следующую степень (21^8) каждую цифру потребуется “столбиком” перемножать на 21. При этом понадобится переносить остатки. Так 21 * 4 = 84, 4 остается в этом регистре, остаток (8) переносится в старший.
Как сравнивать два числа? Придется поэлементно проходить по двум массивам и сравнивать каждую цифру.
В общем, в итоге, требуется не только много места для хранения чисел, но и огромное количество операций для операций с ними.
В нашем случае числа будут храниться в массиве в виде множителей. Индекс массива будет означать множитель, а значение по этому индексу – количество этих множителей в числе.
Так число 3^7 будет храниться не как 2187 и не как массив цифр [2,1,8,7], а как массив множителей [0,0,0,7,0,0,0..].
arr[3] = 7 – означает, что число имеет 7 множителей 3 (3*3*3*3*3*3*3).
В итоге, чтобы возвести 3^7 в следующую степень 3^8, необходимо просто увеличить соответствующий индекс в массиве arr[3]++.
Для сравнения двух чисел необходимо сравнить соответствующие индексы. Однако, чтобы не пришлось поэлементно сравнивать два массива, понадобится несколько улучшений алгоритма. О них будет рассказано ниже, в соответствующих разделах.
При возведении разных чисел в разные степени может получиться одно и то же число. Так, например, 2^4 = 16 и 4^2 = 16.
Однако, при сравнении массивов они будут разными:
Потому, во-первых, перед сохранением числа в массив, его необходимо разложить простые множители. Так 4 = 2^2 и, следовательно, 4^2 = (2^2)^2= 2^4.
Во-вторых, простые числа уже нельзя разложить как либо еще по определению. Потому, числа, образованные степенями простых чисел, можно не проверять на наличие пары, а сразу же учитывать как уникальные.
До 100 существует 25 простых чисел. Занесем их в массив по индексу при его инициализации (смотри скриншот выше).
В основной части программы с помощью двух циклов for() перебираются все основания (base) и степени (pow) числа до сотни и формируются все возможные числа.
Далее, как описано было выше, число не заносится сразу в массив. Сначала число раскладывается на простые множители.
Так вместо 21^4 в память заносится 3^4, после чего 7^4. Т.е. в итоге число 21^4 записывается не как 21*21*21*21, а как 3*3*3*3*7*7*7*7 ([0,0,0,4,0,0,0,4,0,0…] в массиве).
Поскольку простые числа начинаются с 2, потому в массиве первые две ячейки всегда будут пустыми. Для облегчения последующего сравнения массивов между собой запишем в них признаки числа. В нулевую ячейку запишем количество множителей числа, а в первую – сумму номиналов множителей.
Например, вышеупомянутое число 21^4 запишем в итоге так:
Далее число проверяется на его уникальность.
Если оно образовано степенью простого числа – оно уникально, дополнительных проверок не потребуется.
Иначе число сравнивается с ранее сохраненными, поэлементно сравнивая массивы. Поскольку первые две ячейки заняты признаками числа, потому в большинстве случаев после их проверки сразу переходим к следующему числу. Это позволяет не пробегать все сто элементов каждого массива, а в итоге ограничиться парой первых ячеек (в большинстве случаев).
Если число не уникально, то оно обнуляется и перезаписывается. Иначе оно сохраняется и учитывается.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Поскольку раскладываемые на множители числа крайне небольшие (до 100), потому не стал усложнять функцию. Просто перебираются делители числа вплоть до него самого до тех пор, пока не будет найден искомый делитель.
В итоге функция вернет либо минимальный делитель числа, либо само число (если оно не делится).
Поскольку мы храним число в виде массива, номиналов множителей и их количества, потому все сводится лишь внесению соответствующих записей в массив.
Например, при возведении числа 21^4:
Перед началом работы функции проверяется невыход вносимого множителя за пределы массива.
Очень полезная функция. Поскольку ошибки всегда неизбежны, потому вставляю везде, где можно проконтролировать корректность ввода. В случае ошибки, будет выведено предупреждение в консоль и функция вернет true, которое можно правильно обработать в коде.
Данная функция подсчитывает данные для второго признака массива. (о важности этих признаков было написано выше). Проходя по массиву, она суммирует номиналы всех множителей в первую ячейку массива.
Поскольку в нулевой ячейке уже сохранено количество множителей сохранение в данном массиве, потому следует при проходе массива их подсчитывать. Когда в итоге будут пройдены все множители, хранящиеся в массиве, можно остановить проход.
Как было уже описано выше, функция сравнивает два массива поэлементно. Однако, поскольку в первых двух ячейках сохранены признаки массива, потому различие массивов будет ясно сразу же.
Если и количество множителей в массивах совпало и сумма номиналов множителей, тогда проход по массивам продолжится. Однако и при этом проход закончится сразу же, как будут пройдены все множители, хранящиеся в массиве (это значение сохранено в нулевой ячейке). Все вышеперечисленное в итоге сокращает проход по массиву со ста до одной-двух ячеек для большинства чисел.
Так как часть чисел повторяется, потому потребуется массивов перезаписывать. Для этого и служит данная функция. Она проходит по массиву и заполняет его ячейки нулями. В ней так же проверяется корректность ввода, потому что иначе можно записать нули за пределы массива.
В итоге ответ на 29 задачу проекта Эйлера составил 9183, программа считает ответ довольно быстро – за 0.1 секунды.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
