Проект Эйлера (44 задача). Не стоит одно и то же вычислять дважды, и потому результаты будем сохранять в динамические массивы.
Узнать больше в телеграм-канале: ProjectEuler++
Пятиугольные числа вычисляются по формуле:
- Pn=n(3n−1)/2.
Первые десять пятиугольных чисел:
- 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …
Можно убедиться в том, что P4 + P7 = 22 + 70 = 92 = P8. Однако, их разность, 70 − 22 = 48, не является пятиугольным числом.
Найдите пару пятиугольных чисел Pj и Pk, для которых сумма и разность являются пятиугольными числами и значение D = |Pk − Pj| минимально, и дайте значение D в качестве ответа.
Формулу из задания:
… можно преобразовать в квадратное уравнение вида a * x^2 + b * x + c = 0:
Это позволит проверять наличие решения, вычисляя его корни:
где x – порядковый номер пятиугольного числа.
Если вычисленный корень x (порядковый номер) – целое число, то число пятиугольное.
Однако, у такого подхода есть один минус. Для поиска ответа нам понадобится перебирать все возможные комбинации пятиугольных чисел и потому – снова и снова вычислять одни и те же значения.
Чтобы этого в итоге избежать, вычисленные значения пятиугольных чисел будем сразу сохранять в массивы.
Для хранения списка пятиугольных чисел создадим структуру. Она будет содержать указатели на два массива и значения их длин.
Массив arr[ ] будет служить для хранения списка вычисленных пятиугольных чисел просто по порядку:
Массив is_pent[ ] будет хранить пятиугольные числа по их индексу:
Это позволяет легко определять статус числа (пятиугольное оно или нет) просто обращаясь к массиву по индексу.
Поскольку заранее не известно до каких чисел придется перебрать, прежде чем найдется ответ, потому в структуре используются именно не массивы, а именно ссылки на них. Массивы будем увеличивать по мере необходимости.
Уже привычно разбил функцию main() на два скриншота.
Вычисление пятиугольных чисел будем производить частями, по мере необходимости. Сначала вычислим первых 2500 пятиугольных чисел. Описание функции для инициализации структуры будет ниже.
Далее в вычисленном диапазоне – от 1-го до 1250-го пятиугольного числа (2500 / 2) будем в двух циклах перебирать их варианты сочетаний и проверять их соответствие условиям.
Если в заданном диапазоне пятиугольных чисел ответ не найден, то его границы изменяются. Начало диапазона принимает значение конца (1250), а значение конца удваивается (2500).
Поскольку при инициализации структуры выделяется место в памяти с помощью функций malloc() и calloc(), потому обязательно необходимо освобождать память с помощью free(). Далее структура инициализируется новым диапазоном чисел (до 5000) и вычисления повторяются.
Цикл будет повторяться до тех пор, пока в итоге не будет найден ответ. Поскольку перебор чисел идет от меньшего к большему, потому первый же найденный ответ будет минимальным.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Для хранения нужного количества чисел выделяем память под массив arr[ ] функцией malloc(). При этом необходимо учитывать, что храниться будут int числа (по 4 байта).
Для массива is_pent[ ], хранящего “статус” числа по его индексу, выделяем память с помощью функции calloc(). Она автоматически заполняет ячейки нулями, и потому в массиве достаточно будет только отметить пятиугольные числа как 1. Числа не являющиеся пятиугольными будут уже отмечены как 0.
Храниться в этом массиве будут значения char (1-байтовые), однако длину массива понадобится уже вычислить. К примеру, если будет храниться 2500 пятиугольных чисел, то его длины должно хватать для хранения последнего (2500-го) числа – 9373750.
Поскольку данная функция выделяет память, потому (чтобы избежать “утечки памяти”), после окончания работы со структурой, ее необходимо в последствии освобождать. Как напоминание об этом в названии функции использовалось слово malloc:
Если внимательно посмотреть на ряд пятиугольных чисел, приведенный в задании:
…то можно увидеть некоторую закономерность их изменения.
Числа отстоят друг от друга на шаг (step), который равномерно увеличивается. Первое число отстоит от второго на 4 (step = 4), второе от третьего на 7, третье от четвертого – на 11. Т.е. шаг каждый раз увеличивается на 3 (step +=3).
Это в итоге позволяет заменить вычисление пятиугольных чисел по формуле простым проходом по массиву.
Поскольку таким образом операция по заполнению массивов выполняется очень быстро, потому решил не «расширять» массивы, копируя ранее вычисленные значения, а просто вычислять и заполнять массив заново.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
