Задача
Если p - периметр прямоугольного треугольника с целочисленными длинами сторон {a,b,c}, то существует ровно три решения для p = 120:
{20,48,52}, {24,45,51}, {30,40,50}
Какое значение p ≤ 1000 дает максимальное число решений?
Решение
Переберу каждую пару катетов треугольника a, b, и вычислю для них гипотенузу c. Так как периметр не может быть больше 1000, то предел длины для a или b это 998. Ну, типа 998+1+1. Но и такого быть не может, так как гипотенуза всегда длиннее любого из двух катетов. Значит, можно взять примерно 498 и на этом успокоиться.
Чтобы выяснять, целочисленная ли гипотенуза, возможно существует какой-то более быстрый способ, но я просто вычисляю целочисленный квадратный корень из a^2 + b^2, а затем снова возвожу его в квадрат. Если совпало с изначальным значением, значит гипотенуза целочисленная.
Если различные значения a и b дают один и тот же периметр, значит они являются решениями для этого периметра, которые надо подсчитывать.
Для этого я сделал массив счётчиков solutions длиной 1001 элемент (1000 + индекс 0, который не используется), где индекс это собственно периметр, а значение – количество решений.
Также я экономлю на циклах: если в какой-то момент периметр стал больше 1000, значит дальше он будет ещё больше, поэтому цикл прекращается досрочно.
Ссылка на онлайн-компилятор языка C с текстом программы
P.S. Дополнительно в переборе можно учесть, что пары значений (a, b) и (b, a) дают один и тот же результат.
Подборка всех задач