2012年4月29日日曜日

プロジェクトオイラー Problem4

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

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

Problem 4
左右どちらから読んでも同じ値になる数を回文数という。
2桁の数の積で表される回文数のうち、最大のものは 9009 = 91 × 99 である。
では、3桁の数の積で表される回文数のうち最大のものはいくらになるか。

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

m = 0
for i in xrange(100,1000):
	for j in xrange(i,1000):
		k = i*j
		L = list(str(k))
		if L==L[::-1] and m<k:
			x, y, m = i, j, k
			
print m, "=", x, "x", y
-----

変数iとjで3桁の数を2個用意します。
変数iのxrange(100,1000)は、100,101,102,・・・,998,999を返します。
変数jのxrange(i,1000)は、i,i+1,i+2,・・・,998,999を返します。
123×456と456×123は同じ扱いとする組み合わせの積を求めています。

L = list(str(k))
数値kを文字型に変換し、さらに1文字ずつのlist型に変換しています。

123456 → ['1', '2', '3', '4', '5', '6']

L==L[::-1]
リストとその逆順リストの比較をしています。
list型の添え字部分の[]は「:」で区切るとリスト内インデックスを表します。
L=[開始位置:終了位置:刻み]
開始位置、終了位置を省略すると、リストの最初から最後までの全要素のことです。
また、刻みをマイナス値にすると、要素内を逆順に扱います。
なので、L[::-1]は、リストLの全要素を逆順並べたリストです。
L==L[::-1]で、回文数かの判定をしてます。

回文数最大値mを超える回文数kが出現した場合、
2つの3桁の数i,jと回文数kを、x,y,mとして保存します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
906609 (= 913 x 993)

(追記)
・20120716
 ソースコード部分にSyntaxHighlighterを導入

0 件のコメント:

コメントを投稿