A Pythagorean triplet is a set of three natural numbers, a b c, for which,
For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2
There exists exactly one Pythagorean triplet for which a + b + c = 1000.Find the product abc
http://projecteuler.net/problem=9.
和が1000となるPythagoras数の組を求め、その積を計算する問題。
素直に書くとこうなるだろうか:
----
print [a*b*c for a in xrange(1,1000) for b in xrange(1,1000) for c in xrange(1,1000) \
if a**2 + b**2 == c**2 and a+b+c == 1000]
----
これでも十分計算できるが、for文が3つもあるので結構時間がかかる。
ここでa+b+c =1000という性質を利用する。変数消去という受験でおなじみの常套手段である。c = 1000-(a+b) としてa^2 + b^2 = c^2に代入して整理すると
2(a-1000)(b-1000) = 1000^2
となる。
それを踏まえたソースは以下のようになる:
----
print = [[a,b,1000-(a+b)] for a in xrange(1,1000) for b in xrange(1,1000) \
if 2*(a-pow(10,3))*(b-pow(10,3)) == pow(10,6) and a < b]
----
"exactly one" であるのにリストを用いるのは冗長だろうか。