2013年6月9日日曜日

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

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

問78「コインを山に分ける方法の数を調べ上げよ」
n 枚のコインを異なった方法で山に分ける場合の数を p(n) と表わす.
例えば, 5枚のコインを山に分ける異なったやり方は7通りなので p(5)=7 となる.

OOOOO

OOOO   O

OOO   OO

OOO   O   O

OO   OO   O

OO   O   O   O

O   O   O   O   O

p(n) が100万で割り切れる場合に最小となる n を求めよ.

-----


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






私の回答例は以下の通りです。
def f(n):
	L = [1]
	for j in xrange(1, n+1):
		r = 0
		for i in xrange(1, n+1):
			k = (i+1)//2 * ((i%2)*2-1)
			m = j - k*(k*3-1)//2
			if m<0: break
			r += ((i+1)%4//2*2-1) * L[m]
		if not r%n: return j, r
		L.append(r)
	return None
	
n=1000000
print f(n)



問76から3問連続で分割数の問題です。
それぞれ前の問を解決したロジックのままでは1分ルールに間に合いません。
ずいぶん考えたのですが、結果としてゼロから解法構築はできず、
ネット検索したロジックを実装しました。

wikipediaの「分割数」によれば以下のとおりです。
分割数の関数をpとして、
p(k) = p(k-1) + p(k-2) - p(k-5) - p(k-7) + p(k-12) + p(k-15) - p(k-22) - ...
p(0) = 1, 負の整数kに対してp(k)=0

関数pの引数の中で使用する値1, 2, 5, 7, 12, 15, ...は、
n=1, -1, 2, -2, 3, -3, 4, -4, ...に対する五角数n(3n-1)/2です。
また、p(k)を構成する各項の符号は、順に+, +, -, - の繰り返しです。

1.関数p(n)
・nで割り切れる最小の分割数を持つ整数とその分割数を返します。
・リストLは分割数の配列です。0以上の整数iの分割数をi番目の要素として持ちます。
・分割数リストLの初期値は、0の分割数で、定義により、1をセットします。
・ループ変数jごとに変数rに上記の各項の和rをためます。このrが整数jの分割数です。
・ループ変数iが分割数の式の各項に対応します。
 整数kの分割数は、k未満の分割数から計算できるので、
 ループ変数iは1からnまでの範囲内で負の数の分割数が必要になったところまでです。

ループ変数i
 1, 2, 3, 4, 5, 6, 7, 8, ... (A)

(i+1)//2
 1, 1, 2, 2, 3, 3, 4, 4, ... (B)

(i%2)*2 -1
 1,-1, 1,-1, 1,-1, 1,-1, ... (C)

よって、五角数を求めるための整数kは、(B)と(C)の積で、
k
 1,-1, 2,-2, 3,-3, 4,-4, ... (D)

そして上記(D)に対応する五角数は、
k*(3*k-1)//2
 1, 2, 5, 7,12,15,22,26, ... (E)

nから上記(E)の五角数を引いた値をmとして、mの分割数を求めます。
ループ変数j未満の分割数はすでに分割数リストLにあります。

求める分割数を構成する各項の和を求める際の、各項の符号は以下の通りです。
(i+1)%4//2*2-1
 1, 1,-1,-1, 1, 1,-1,-1, ... (F)

・分割数rがnで割り切れるか判定します。
  r%nでrをnで割った余りを求め、割り切れると余り0で論理的にFalseになります。
  このFalseになったときが割り切れたときで、整数jとその分割数rを返します。


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