Пифагорейские тройняшки
Исходную проблему можно найти здесь
Здесь утверждается:
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which a² + b² = c² For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
Мой друг Анил и я обсуждали это вчера вечером, и я думаю, что немного усложнили его, подняв множество других неупомянутых свойств пифагорейских троек, которые можно было бы использовать.
Однако то, что я сделал, оказалось довольно простым и работало очень эффективно.
Два факта, на которых я основывал свое решение:
- Из теоремы о неравенстве треугольника (ни одна сторона не может быть больше суммы двух других) я знал, что ни одна из сторон не может быть больше 500 без того, чтобы сумма трех сторон не превышала 1000.
- У нас есть три переменные (a, b, c), но только два уравнения (a² + b² = c² и a+b+c=1000. Этого недостаточно, чтобы решить для любой одной переменной, но нам достаточно, чтобы выразить задача как одно выражение с двумя переменными.
Если вы изолируете c и сведете к одному выражению a и b, вы получите:
1000-a-b = кв (а² + b²)
Все, что вам нужно сделать сейчас, это попробовать все комбинации a и b и найти ту, для которой это выражение верно.
Я знаю, что ни a, ни b не могут быть больше 500, поэтому я просто заполнил два массива числами от 1 до 500 и прогнал их через вложенный цикл for, пока не нашел пару, удовлетворяющую моему уравнению.
Код:
#c = sqrt(a**2 + b**2) #abc = a*b*sqrt((a**2) + (b**2) #c = 1000 — a — b # 1000 — a — b = sqrt(a**2 + b**2) import math x=[] y=[] for i in range(1,501): x.append(i) y.append(i) for a in x: for b in y: if 1000 — a — b == math.sqrt(a**2 + b**2): print “Triplet: “,a,b,(1000-a-b) print a*b*(1000-a-b)
Барабанная дробь Пожалуйста:
- Сам триплет: a=375, b=200 и c=425.
- Произведение abc=31 875 000
Если у вас есть какие-либо предложения о том, как я мог бы улучшить свой алгоритм, пожалуйста, дайте мне знать в комментариях!