Проект Эйлера (39 задача). Несложная задача на стишок про “Пифагоровы штаны”. По сути, легко решается перебором, однако и его можно ускорить.
Узнать больше в телеграм-канале: ProjectEuler++
Если p – периметр прямоугольного треугольника с целочисленными длинами сторон {a,b,c}, то существует ровно три решения для p = 120:
{20,48,52}, {24,45,51}, {30,40,50}
Какое значение p ≤ 1000 дает максимальное число решений?
Все решение уместилось в функции main(), потому чтобы не “мельчить”, решил разбить ее на два скриншота.
Данный стишок в школе помогал запомнить теорему Пифагора:
Треугольник, у которого сумма квадратов длин двух сторон равна квадрату длины третьей стороны, является прямоугольным.
Действительно, если нарисовать, получается очень похоже.
Данная теорема дает нам формулу для проверки удовлетворения условий задачи:
Можно не перебирать все возможные треугольники и выбирать из них прямоугольные, как описано выше, а сразу получать прямоугольные треугольники. Для этого будем перебирать только катеты треугольника a и b, а гипотенузу c будем вычислять:
При этом условиям задачи треугольник будет соответствовать, если гипотенуза целочисленная.
Это сразу уменьшит объем вычислений на три порядка, однако как вычислять квадратный корень? Стандартная функция sqrt() работает с вещественными числами типа double, и потому не дает нам возможности понять, целое ли число или нет.
В программе я решил вычислить квадраты натуральных чисел и сохранить их в массив по индексу.
Поскольку остальная часть массива заполнена нулями, потому достаточно обратиться к нему, чтобы понять целочисленный ли квадратный корень из числа или нет.
Кроме того, нам понадобится массив для подсчета ответов. Индексом массива будет являться периметр треугольника, а значением ячейки – количество возможных решений для данного периметра (смотрите выше).
В программе перебираются два катета a и b в двух циклах for(). При этом:
После нахождения целочисленной гипотенузы (c), также учитываем только те ответы, при которых периметр треугольника (a+b+c) меньше 1000.
Каждый найденный ответ увеличивает количество решений для данного конкретного периметра – индекса в массиве ответов.
После перебора всех катетов и подсчета всех возможных вариантов, остается в итоге только пройтись по массиву и выбрать периметр с максимальным количеством решений.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
