Project Euler - Probrem 33

Project Euler(プロジェクト　オイラー）の問題をpythonでやってみます。

出典： Project Euler（日本語 翻訳サイト）
　　　　　　 ProjectEuler.net（英語サイト）

Problem 33

49/98は面白い分数である.「分子と分母からそれぞれ9を取り除くと、49/98 = 4/8 となり、簡単な形にすることができる」と経験の浅い数学者が誤って思い込んでしまうかもしれないからである. (方法は正しくないが，49/98の場合にはたまたま正しい約分になってしまう．)

我々は 30/50 = 3/5 のようなタイプは自明な例だとする.

このような分数のうち、1より小さく分子・分母がともに2桁の数になるような自明でないものは、4個ある.
その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.

－－－－－

私の解答例は以下です。畳んでいます。

def gcd(a, b):
	if a<b: a, b = b, a
	if b: return gcd(b, a%b)
	else: return a

def h(i, s):
	L = [t for t in str(i) if t!=s]
	return float("".join(L))

def g(m, n):
	for s in str(m):
		for t in str(n):
			if s==t: return s

def f():
	si = sj = 1
	for i in xrange(10, 100):
		if not i%11: continue
		for j in xrange(10, i):
			if not j%11: continue
			s = g(i, j)
			if s>"0" and h(i, s) \
			and float(j)/float(i)==h(j, s)/h(i, s):
				si *= i
				sj *= j
	return si//gcd(si, sj)

print f()

４つの関数を使っています。

１．gcd(a, b)
・「ユークリッドの互除法」を使用して最大公約数を返します。
　説明はProblem5を参照してください。

２．関数g(m, n)
・n,m両方にある同じ文字を返します。
　「正しくない約分」で削除する１文字を探す操作に相当します。

・for s in str(m):
　　for t in str(n):
　m,nそれぞれをstr関数で文字型にして、１文字ずつループ変数s,tとして取り出します。

・if s==t: return s
　上記のようなs,tで値が等しい場合、その値を返します。
　等しくない場合は何も記述していませんが、初期値Noneが返ります。
　

３．関数h(i, s)
・引数iの構成文字から文字sを取り除き、浮動小数点型にして返します。
　正しくない約分で１文字削除する操作に相当します。

・L = [t for t in str(i) if t!=s]
　内包表記で記述しています。
　まず中ほどのfor文を実行し、引数iをstr関数で文字型にしてから１文字ずつ取り出しループ変数tにセットします。
　次に後ろのif文を実行し、先ほどのtと引数sが異なるか判定し、判定に通った場合のみ、forの前に引渡します。
　forの前に引き渡されたそのようなtをリストLにためます。

・return float("".join(L))
　上記リストLの要素を連結し、float関数で不動小数点型に変換します。
　イテレータの要素を連結するjoinメソッドは区切り文字のメソッドです。
　区切り文字無しの場合は、今回のように""のメソッドを使います。
　pythonを始めた頃は、連結するデータ側のメソッドでなく、
　区切り文字のメソッドというところに違和感を感じていましたが、
　今ではすっかり慣れました。
　
４．f()
・主処理です。

・si = sj = 1
　問題に合う分数の分母と分子をsi,sjとして、掛け算累積するため初期値は1とします。

・for i in xrange(10, 100):
　if not i%11: continue
　ループ変数iは分母です。10から99までの２桁の整数を範囲です。
　ただし、「正しくない約分」をするためには異なる数字で構成される必要がありますので、11で割り切れない値だけを対象にします。
　直後のif文で11で割った余りがない、つまり余り0、論理判定でFalseとなる場合は次の値へ進みます。

・for j in xrange(10, i):
　if not j%11: continue
　ループ変数jは分子です。1より小さい分数の分子なので、分子は分母より小さな値になります。
　範囲は10からi-1までの整数となります。if文の考え方は上記の分母のときと同じです。

・s = g(i, j)
　「正しくない約分」で消去対象となる数字をsとします。

・if s>"0" and h(i, s) \
　and float(j)/float(i)==h(j, s)/h(i, s):
　　si *= i
　　sj *= j
　問題に合う分数かチェックします。
　チェック条件は以下の３つで順ににandでつないでいます。
　条件に合えば、分母分子それぞれを掛け算累積します。
　1.「正しくない約分」で消去対象となる数字が0でないこと。0は「自明な約分」になるため。
　2.「正しくない約分」をした場合の分母が0でないこと。
　3.「正しくない約分」をした場合の値が約分前の値と等しいこと。
　
・return si//gcd(si, sj)
　「問題に合う分数の積を正しく約分したときの分母」を返します。
　「問題に合う分数の積」の分母、分子はそれぞれsi,sjです。
　このsiを、分母分子の最大公約数で割った値が、戻す値となります。
　

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