2017年3月20日月曜日

プロジェクトオイラー 問125

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。


問125「連続する平方数の和で表せる回文数の和」
回文数 595 は連続する平方数の和で表すことができるという面白い性質を持つ:
62 + 72 + 82 + 92 + 102 + 112 + 122


1000 未満で連続する平方数の和で表せる回文数はちょうど 11 あり, その合計は 4164 である.
正の整数の平方のみをこの問題では扱うため, 1 = 02 + 12 は含めないことに注意せよ.

回文数でありかつ連続する平方数の和で表せる, 108 未満のすべての数の合計を求めよ.



注意!!!
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。




私の回答例は以下の通りです。
def f(nmax):
	L = []
	M = [i*i for i in xrange(1, int(nmax ** 0.5)+1)]
	
	for i in xrange(len(M)):
		s = M[i]
		for j in M[i+1:]:
			s += j
			if s >= nmax: break
			t = str(s)
			if t == t[::-1]: L.append(s)
			
	L = set(L)
	return sum(L), len(L)
	
if __name__=="__main__":
	nmax = 10**8
	s, k = f(nmax)
	print "値n <", nmax, "の場合:合計 =", s, "、個数 =", k



平方数の和で表せる数を計算し、それが回文数ならためるようにします。

1.関数f(nmax)
・値nの最大値を受け取り、平方数の和で表せる回文数の合計値と個数を返します。


・M = [i*i for i in xrange(1, int(nmax ** 0.5)+1)]
 Mは、必要な平方数の二乗値のリストです。
 二乗値がnmax以下なので、二乗する値iはnmaxの平方根の整数部分までです。
 forループ上の終端値はこの値を +1 した値となります。


・for i in xrange(len(M)):
 ループ変数iは、二乗値リストMの要素のうち、和の計算で使用する最初の値のインデックス値です。


・s = M[i]
 sは二乗値の和です。初期値は二乗値リストMのi番目の値です。


・for j in M[i+1:]:
  s += j
 ループ変数jは、二乗値リストMのインデックスi番目より後の値です。
 sにjを累積していきます。


・if s >= nmax: break
 二乗値の和sの最大値チェックです。nmax以上になったら処理終了です。
  
・t = str(s)
 if t == t[::-1]: L.append(s)
 二乗値の和sの回文数チェックです。
 二乗値の和sを文字型に変換してtとし、各桁を逆順に並べた文字列と一致するかを判定します。この回文数判定は問36のときと同じです。

 回文数の場合、リストLにためます。

・L = set(L)
 リストLをset文で集合型にすることで、その要素の値をユニークにします。


・return sum(L), len(L)
 リストLの合計値と個数を返却します。



解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
値n < 100000000 の場合:合計 = 2906969179 、個数 = 166

0 件のコメント:

コメントを投稿