2012年8月7日火曜日

Project Euler - Probrem 32

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

出典: Project Euler(日本語 翻訳サイト)
       ProjectEuler.net(英語サイト)

Problem 32
7254は面白い性質を持っている. 39 × 186 = 7254と書け,
掛けられる数/掛ける数/積に1から9の数が1回ずつ出現する.

掛けられる数/掛ける数/積に1から9の数が1回ずつ出現するような積の総和を求めよ.

HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせ
を持つが1回だけ数え上げよ.

-----

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

def f(m, n):
	L = []
	for i in xrange(10**(m-1), 10**m):
		for j in xrange(10**(n-1), 10**n):
			k = i*j
			s = str(i)+str(j)+str(k)
			if (len(s)==9) and ("0" not in s) \
			and (len(s)==len(set(list(s)))):
				L.append([i, j, k])
	return L
	
L = f(1,4)+f(2,3)
print sum(set([s[2] for s in L]))
	


・問題の条件に合う掛け算の桁数は以下の組合せのいずれかになります。
 1桁×4桁=4桁、2桁×3桁=4桁。

1.関数f(m, n)
・m桁とn桁の掛け算において、掛けられる数/掛ける数/積に1から9の数が1回ずつ出現する場合の、掛けられる数/掛ける数/積の組合せのリストを返します。

・for i in xrange(10**(m-1), 10**m):
  for j in xrange(10**(n-1), 10**n):
 ループ変数i、jはそれぞれm桁、n桁の整数です。演算子**はべき乗です。

・k = i*j
 s = str(i)+str(j)+str(k)
 kは積、sは掛ける数/掛けられる数/積を構成する数字を文字扱いで連結したものです。
 
・if (len(s)==9) and ("0" not in s) \
and (len(s)==len(set(list(s)))):
  L.append([i, j, k])
 問題の条件に合えば、数/掛ける数/積の組合せリストをリストLに貯めていきます。問題の条件とは以下の3つで、順にandでつなぎました。
 1.掛けられる数/掛ける数/積を構成する文字列長は9。
 2.掛けられる数/掛ける数/積を構成する文字に0は含まれない。
 3.掛けられる数/掛ける数/積を構成する文字列と、これを重複削除した文字列が同じ長さ。
 なお、最後の部分は、list関数で構成文字列をリスト化し、set関数で要素を一意にして、len関数で要素数を求めています。
\演算子は継続行を示しています。

2.関数の外側
・L = f(1,4)+f(2,3)
 関数fで、「1桁×4桁」と「2桁×3桁」について問題に合う
 掛けられる数/掛ける数/積の組合せを求め、1つにまとめてリストLとします。
 
・print sum(set([s[2] for s in L]))
 上記のリストLから要素1つひとつを取り出しsとし、forの前に送り、sの中のインデックス値2の要素である積を取り出して、順にリストに収めます。(内包表記)
 さらにset関数で重複削除し、sum関数で合計を求めます。

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

0 件のコメント:

コメントを投稿