スターン数列は，f(0)=0、f(1)=1と二つの再帰的関係f(2n)=f(n)およびf(2n+1)=f(n)+f(n+1)で定義される．これを計算すると，数列は0,1,1,2,1,3,2,1,4,3,5,2,5,3,4と続く．
マーク・チャンバーランド「ひとけたの数に魅せられて」 P11
何をいっているのか、わからない。
スターン数列でググってみたけれど、ヒットしたサイトは本の説明をくりかえしているだけで何のとっかかりにもならなかった。日本語のwikiも見当たらない。
まぁ、f(0)とf(1)はわかる。でもf(2n)=f(n)って何だ？ イコールじゃないじゃないか。
しばし、じっと見つめる。
あれ？
もしかしたらf(2n)って偶数のことじゃないか？
すると、f(2n+1)は奇数か。
じゃ、コードはこうか？
(require 'cl) (defun wrk(n) (cond ((= n 0) 0) ((= n 1) 1) ((evenp n)(wrk (/ n 2))) ((oddp n)(+ (wrk (/ n 2))(wrk (+ (/ n 2) 1)))))) (mapcar 'wrk '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)) (0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4)
おっ、正しいみたいだぞ1。
プログラミングができてよかった。
エレン、マフラーを巻いてくれてありがとうって気分だ。
そういえば、フィボナッチ数のコードはよく見かけるけど2、実際に自分で組んでみたことはなかった。たしか、こんな感じ？
(defun wrk(n) (cond ((= n 0) 0) ((= n 1) 1) (t (+ (wrk (- n 1))(wrk (- n 2)))))) (mapcar 'wrk '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)) (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610)
0から15ぐらいならすぐだけど、0から100までにしたら延々、もどってこない……。
