日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問７８「コインを山に分ける方法の数を調べ上げよ」
n 枚のコインを異なった方法で山に分ける場合の数を p(n) と表わす.
例えば, 5枚のコインを山に分ける異なったやり方は７通りなので 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)
問７６から３問連続で分割数の問題です。
それぞれ前の問を解決したロジックのままでは１分ルールに間に合いません。
ずいぶん考えたのですが、結果としてゼロから解法構築はできず、
ネット検索したロジックを実装しました。
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)を構成する各項の符号は、順に+, +, -, - の繰り返しです。
１．関数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
