プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問76 「2つ以上の正整数の和としての100の表し方は何通りか」
5は数の和として6通りに書くことができる:
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
2つ以上の正整数の和としての100の表し方は何通りか.
－－－－－
注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。
def g(n, m, d):
if (n,m) in d: r = d[(n,m)]
elif n<m or n<1 or m<1: r = 0
elif n==m: r = 1
else:
d[(n-1,m-1)] = g(n-1, m-1, d)
d[(n-m, m)] = g(n-m, m, d)
r = d[(n-1,m-1)]+d[(n-m, m)]
return r
def f(n):
d = {}
return sum([g(n,m,d) for m in xrange(2, n+1)])
n = 100
print f(n)
自然数nを異なるm個の自然数の和で表示するパターン数p(n, m)を求め、
mを2分割からn分割まで足せばいいと考えました。
問題文中のn=5の場合のパターンをよく見ると
「末尾が+1」のパターンは、5より1つ小さいn=4の場合のパターンに+1しただけで、パターン数としてはn=4の場合と全く同じです。
あとは、「末尾に+1が来ないパターン」ですが、この規則性がなかなかわからず長考に入ってしまいました。
どうしてもやり方がわからず、ネット検索したところ、
以下のことがわかりましたので参考にしました。
・自然数nを異なるm個の自然数の和に分割するパターン数は「分割数」と呼ばれている。
・自然数ｎnを異なるm個の自然数の和に分割するパターン数は以下の再帰的な記述ができる。
p(n, m) = p(n-1, m-1)+ p(n-m, m)...(1)
(1)式の「p(n-1, m-1)」部分は、
構成する項を値の大きい順に並べたときに末尾が1のパターン数です。
これは私も気づいていた、nより１つ小さい自然数を、mより１つ小さい個数に分けた場合のパターン数です。
最後の末尾に+1の項を付加することで、自然数nをm個に分割したパターンになります。
次の「p(n-m, m)」の部分ですが、これは
構成する項を値の大きい順に並べたときに末尾が1以外のパターンです。
m個の項すべてが1より大きいパターンなので、m個の項すべてから1ずつ引いてみると、
自然数(n-m)がm個に分割されている状態とまったく同じです。
(1)式のように分割する自然数や分割個数を小さくした再帰呼び出しで数量が確定します。
１．関数g(n, m, d)
・自然数nをm個の自然数の和に分割するパターン数を返します。
・dはキー(n,m)に対応するパターン数を格納する辞書（連想配列）です。
一度計算した(n,m)のパターン数は辞書に格納して繰り返し参照することで速度向上を目指します。
・elif n<m or n<1 or m<1: r = 0
elif n==m: r = 1
再帰呼び出しの終了条件です。
n<mの場合、自然数nよりも多くの部分には分けられないので、そのようなパターンは0件です。
n,mいずれも1未満では分けられないので、そのようなパターンは0件です。
n=mの場合、自然数nを同数の部分に分けるので全項目1+1+...+1にするパターン1つだけです。
２．関数f(n)
自然数nを異なるm個の自然数の和で表示するパターン数を関数g(n, m)を求め、
mを2分割からn分割まで足します。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
190569291
