第6夜:にぎやかなウサギ時計

数の悪魔*1を題材にSchemeプログラミングの6回目です。今回は、フィボナッチのうさぎのつがいです。
「一ヶ月後、子うさぎのつがいは親うさぎのつがいになり、次の一ヶ月後、親うさぎのつがいは子うさぎのつがいを産むようになります。今、子うさぎが一つがい居ます。十二ヶ月後、うさぎは何つがいになるでしょうか。」という問題です。本では、数の悪魔が時間を操る時計を持ってきて、時間を加速させていくという話です。

このジャガイモ畑は、時間の進み方がじつに速い。1か月はたったの5分ですぎる。ほら、見てごらん。ウサギ時計をもってきたから - 数の悪魔

(define (hare-clock n)
	(define (move-hare h l nl)
		(if (null? l)
			(reverse (if (= 0 h) nl (cons (cons h 0) nl)))
			(move-hare (cdr (car l)) (cdr l)
				(cons (cons h (+ (car (car l)) (cdr (car l)))) nl))))

	(define (hare-iter n l)
		(if (< n 1)
			l
			(hare-iter (- n 1) (move-hare 0 l '()))))

	(hare-iter n '((1 . 0)))
)

(define (hare-to-string l)
	(define (dup n c l)
		(if (< n 1)
			l
			(dup (- n 1) c (cons c l))))

	(define (hare-str-iter l nl)
		(if (null? l)
			(reverse nl)
			(hare-str-iter (cdr l)
				(cons (string-join
					(dup (car (car l)) "v"
					(dup (cdr (car l)) "Y" '())) "") nl))))

	(hare-str-iter l '())
)

(define (main args)
	(print (hare-to-string (hare-clock 7)))
0)

プログラムでは、子うさぎのつがいを"v"で、親うさぎのつがいを"Y"で表しています。結果は以下のとおり。

(Y vYYYYY vvvvYYYYYY vvvY)

プログラムをちょっと変えて、0から9までを計算すると以下のようになります。

(define (main args)
	(let loop ((n 0))
		(if (< n 10)
			(begin (print n ": " (hare-to-string (hare-clock n)))
				   (loop (+ n 1)))))
0)

0: (v)
1: (Y)
2: (Y v)
3: (Y vY)
4: (Y vYY v)
5: (Y vYYY vvY)
6: (Y vYYYY vvvYYY v)
7: (Y vYYYYY vvvvYYYYYY vvvY)
8: (Y vYYYYYY vvvvvYYYYYYYYYY vvvvvvYYYY v)
9: (Y vYYYYYYY vvvvvvYYYYYYYYYYYYYYY vvvvvvvvvvYYYYYYYYYY vvvvY)

この隣り合ったうさぎの数の比は、黄金比(黄金率,golden ratio:φ)に収束していくそうです。
最後に、ウルフラム・アルファさんに聞いてみよう:http://www.wolframalpha.com/input/?i=fibonacci+number

*1:Hans Magnus Enzensberger,1997,Der Zahlenteufel,エンツェンスベルガー 丘沢静也(訳),2000,数の悪魔,晶文社