Problem 76 - Project Euler
アンチョコ見てしまったけれども今回は久しぶりに上手くできたと思う。
200msくらい。
そしてProblem 76はアレです。分割数! そう、数学ガール!
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2007/06/27
- メディア: 単行本
- 購入: 58人 クリック: 1,055回
- この商品を含むブログ (967件) を見る
いやまあ載ってると言えば載ってる。分割数の一般項が。ただ読んだ人なら分かると思うけど、ちょっと試行錯誤で思いつくのは厳しい。
見てしまったアンチョコはこれ。
概要はこんなかんじ。
ある数nについてr個に分割する方法を考えによって分割パターンの個数を表わすとすると、明かに
それ以外のとき、を含む分割パターンはの項を一つ減らすことでと等しくなり、を一つも含まない分割パターンでは各項から1ずつ引くことでと等しくなる。よって、
これは再帰を使ったら簡単に書ける。
pn.part <- function(n,r){ if(n==r || r==1) return(1) if(n < r) return(0) return(pn.part(n-1,r-1) + pn.part(n-r,r)) } ans <- 0 for(i in 2:100){ ans <- ans + pn.part(100,i) } ans
ただしこれは見易いだけで1時間回したって終わらない。
行列にメモって計算したらすぐ終わる。
pn.parts <- matrix(rep(0,1e4),100) for(n in 1:100){ for(r in 1:n){ if(n==r || r==1){ pn.parts[n,r] <- 1 }else{ pn.parts[n,r] <- pn.parts[n-1,r-1] if(n-r >= r) pn.parts[n,r] <- pn.parts[n,r]+pn.parts[n-r,r] } } } sum(pn.parts[100,1:99])