Countinuation Passing to reduce the count of beans
和田栄一先生のブログが大好きです。淡々とした静かな文章の間々に、計算機への愛情が見え隠れする様はたまりません。
そんな和田先生が、節分に関するエントリにて、以下のような問題を取り上げていました。
年の数が多いと, 10の桁の数と1の桁の数を足したものにする. それでも多いときは? もう一度このようにする. たとえば78歳なら78粒は多いので7+8=15とする. それでも多ければ1+5=6とする. 繰り返すのはいやなので閉じた式にする.つまり(modulo n 9)となる.
パラメトロン計算機: 節分
9歳の子供は9粒だから, (+ (modulo (+ n 8) 9) 1)というべきである. でも今度は0歳が9粒になってしまった. はて? それはさておき...
先生のアプローチは繰り返しを避けるということでしたが、この問題は継続渡し形式(continuation passing style)でコードを書くよい題材であるように思い、Schemeで書いてみました*1。Schemeの処理系にはGaucheを用いています。
(define (reducebeans x cont) (if (>= x 10) (reducebeans (modulo x 10) (lambda (n) (reducebeans (quotient x 10) (lambda (m) (reducebeans (+ n m) cont))))) (cont x)))
結果もよいようです。
gosh> (reducebeans 78 values) 6 gosh> (reducebeans 15 values) 6 gosh> (reducebeans 9 values) 9 gosh> (reducebeans 0 values) 0
*1:2009/2/8修正。>を>=とした
