プロジェクトオイラー Problem9

「プロジェクト　オイラー」の問題をpythonでやってみます。

出典： Project Euler （日本語翻訳サイト）
参考： サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 9
ピタゴラスの三つ組(ピタゴラスの定理を満たす自然数)とはa<b<cで
a² + b² = c²
を満たす数の組である.
例えば, 3² + 4² = 9 + 16 = 25 = 5²である.
a + b + c = 1000となるピタゴラスの三つ組が一つだけ存在する.このa,b,cの積を計算しなさい.

私の解答例は以下のとおりです。
－－－－－

def f(n):
	for a in xrange(1, n//3):
		for b in xrange(a+1, (n-a)//2):
			c = n-a-b
			if (b<c) and (a**2 + b**2 == c**2):
				yield a, b, c

for a, b, c in f(1000):
		print a*b*c, ":", str(a)+"x"+str(b)+"x"+str(c)

－－－－－

・f(n)は、和がnであるピタゴラスの３つの数を返す関数です。
　求める値はこの戻り値の３つの数の積です。

・ループ変数a
　a<b<cかつa+b+c=nなので、aは最大でもn/3です。
　これを超えるとa,b,cの和がnを超えてしまいます。
　なお、「//」は切り捨て除算といって、整数までしか計算しない割り算の商です。今までの問題で「/」を使っていた部分は、この「//」演算子に取り替えても動作します。動作速度は、途中で計算をやめてしまう「//」演算子の方が速いです。

・ループ変数b
　a<b<cかつa+b+c=nかつaの値が決まってしまった後なので、bとcの和がn-aになり、bは最大でも(n-a)/2です。
　これを超えるとbとcの和が(n-a)を超えてしまいます。
　また最小候補値はa<bより、a+1　です。

・変数c = n-a-b
　a<b<cかつa+b+c=nかつ外側のループでa,bの値が決まってしまった後なので、cは一意に決まります。

・if (b<c) and (a**2 + b**2 == c**2):
　判定条件です。
　a<b<cの条件について、a<bはループ変数bの初期値で規定したので、b<cを入れておきます。あとはピタゴラス数の定義式そのものです。

・yield a, b, c
　pythonには関数の戻り値を返す命令語が２つあります。returnとyieldです。
　return文は戻り値を1度返したら終わりで、関数中の変数はクリアされます。
　yield文は戻り値を返すときに処理状況を一旦凍結しておいて、再度呼び出されたときに処理を再開して次の値を返し続けます。

　問題文では「答えは一つだけ存在する」とありますが、念のため、答えが複数あるときに備えてyield文で返しています。

・for a, b, c in f(1000):
　関数fの呼び出しは、yield文での返しに合わせ、for文の繰り返し元として呼び出しています。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
31875000 : 200x375x425

（追記）
・20120716
　ソースコード部分にSyntaxHighlighterを導入。