Project Euler 009
Project Eulerを知る切っ掛けになった問題です。
009
ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.
a^2 + b^2 = c^2
例えば,
3^2 + 4^2 = 9 + 16 = 25 = 5^2
である.
a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.
->次の問題
考え方
aとbは入れ替え可能なのでa<bとする。
a^2 + b^2 = c^2\\
より a<b<cとなる。
よって
a + b + c = 1000 \\
\rightarrow 3a < 1000 \\
\rightarrow a < \frac{1000}{3}
b<c, c = 1000-a-bより
b < 1000 - a - b\\
\rightarrow 2b < 1000 - a \\
\rightarrow b < \frac{1000-a}{2}
となり、a,bが決まればcは定まるので、
a < 1000/3, b < (1000-a)/2の範囲を探索すれば良さそうです。
コード
euler009.py
def main():
n = 1000
for a in range(1, (n // 3)): # 切り捨て
for b in range((a + 1), -(-(n - a) // 2)): # 切り上げ
c = n - (a + b)
if c ** 2 == a ** 2 + b ** 2:
print(f"a={a}, b={b}, c={c}, abc={a * b * c}")
break
if __name__ == '__main__':
main()
結果
a=200, b=375, c=425, abc=31875000
main処理時間: 0.20030498504638672 sec.
余談ですが、nによっては解が複数あるようです。
10000以下で検索するとn=9240の時組み合わせが最大で、20通りのa,b,cの組み合わせがあります。
追記
コメントでご指摘いただきました。上記のコードだと内部のループをbreakで抜けたあと、外側のforループが再開してしまい無駄が生じます。
以下のように修正しました。
def main():
n = 1000
for a in range(1, (n // 3)): # 切り捨て
for b in range((a + 1), -(-(n - a) // 2)): # 切り上げ
c = n - (a + b)
if c ** 2 == a ** 2 + b ** 2:
print(f"a={a}, b={b}, c={c}, abc={a * b * c}")
break
else:
continue
break
for~elseの組み合わせではforループが全て終了した場合のみelse内の処理が実行されます。
これを利用して、forループが完了する=breakしなかった場合、else内のcontinueで外側のループを継続します。
forループが完了しない=breakした場合、else内の処理をスキップしその下のbreakが実行され外側のループも抜けます。