Catalan number
Rosetta Code の方は公式を実装するだけだったので『数のマジック』の練習問題 7.4.1 を NxN 格子上にして出力することにする。
3x3 の場合
次の線上をSからGまで北か東に移動して辿り着くすべてのパスを表示する。
パスの総数はカタラン数になる。+--+--+--G | | | +--+--+ | | +--+ | S出力結果
N=1: NENENE +--G | +--+ | +--+ | S N=2: NENNEE +--+--G | + | +--+ | S N=3: NNEENE +--G | +--+--+ | + | S N=4: NNENEE +--+--G | +--+ | + | S N=5: NNNEEE +--+--+--G | + | + | S
数のマジック
発売日に『プログラミングコンテストチャレンジブック』(以下、アリ本)を買ったことが始まりだ。*1
2章まで読んだが漸化式がたてられないのでストップしまずは『C言語によるはじめてのアルゴリズム入門』を読んだ。アリ本を読んでいる人を見ると アリ充に近づくために「はじめての数論」を読んでる - EchizenBlog-Zwei そうなのだが現在のレベルでは難しそうなのでアリ充はあきらめて『数のマジック』にした。
倭算数理研究所 で Groovy で数学を勉強する方法を見て真似している。*2
// 6.2 新たな関係式 // 表にあるどの成分もすぐ上の行にある直近の2つの成分の和になっている for (n in 2..8) for (k in 0..n) assert comb(n,k) == comb(n-1,k-1) + comb(n-1, k) // ブリッジの可能な手札のすべてはスペードAを含む場合の数と含まない場合の数を足したもの assert comb(52,13) == comb(51,12) + comb(51,13)
7章で重複組合せとかアリ本の内容が出てきたところ。
カタラン数
カタラン数は『数学ガール』第7章 コンボリューションでも読んでいるはずなのだが忘れていた。
『数学ガール』の場合、漸化式まではすぐでてきて一般項を求める方がメインになっているのだが漸化式さえあればプログラムは書ける。
Wikipedia から引用
今回は E より先に対応する N があることが条件なので Ci を N と E で挟めば完成。*3
def catalan = { n -> if (n == 0) return [[]] def r = [] for (i in 0..<n) // Σ for (c1 in call(i)) // Ci NEの間の組合せ for (c2 in call(n-i-1)) // Cn-i-1 NEのあとの組合せ r << ['N',*c1,'E',*c2] r }.memoize() def path(c) { def path = ['S'] def e = 0 for (d in c) { if (d == 'N') { path << ' ' * e + '|' path << ' ' * e + '+' } else if (d == 'E') { path[-1] += '--+' e++ } } path[-1] = path[-1].replaceFirst(/\+$/,'G') path.reverse() } def p(cs) { def n = 1; for (c in cs) { println "N=${n++}: ${c.join('')}" path(c).each { println it } println() } } p(catalan(3)) p(catalan(4))
漸化式をたてるコツはつかめていないが数学への意味づけのパターンを意識しながらアリ本をもう一度始めることにする。
