SICPを読もう3
大学生は好きに使える時間が多いなあと思う。12:10から16:15まで空きコマという。
問題1.12、1.13をやった。
問題1.12
(define (ptri a b c) (ptri a (+ a b) (+ b c)) (ptri (+ a b) (+ b c) c))
よくわからんが、こういうことだろうか。リストとかはまだなんだからこれでいいんじゃね?
いやもちろんこれを走らせたところで何も返さないが。たしかに要素の計算はしてると思うな!
要素の値が欲しいというのなら、以下のように。
(define (ptri line n) (cond ((or (> n line) (< n 1)) 0) ((= n 1) 1) (else (+ (ptri (- line 1) (- n 1)) (ptri (- line 1) n))))) (ptri 2 2) ; 1 (ptri 3 2) ; 2 (ptri 5 4) ; 4 (ptri 10 5) ; 126
問題1.13
「証明せよ」、ですね。fib(k)の場合なりたつと仮定してfib(k+1)の場合はこうやってほげほげでなりたってfib(0)のときなりたつから帰納法により□
ということになると思う。計算機にチェックさせてみよう。
(define (fib n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2))))) (define (fibx n) (define a (/ (+ 1 (sqrt 5)) 2)) (define b (/ (- 1 (sqrt 5)) 2)) (/ (- (expt a n) (expt b n)) (sqrt 5))) (fib 8) ; 21 (fibx 8) ; 21.000000000000004 ; 1
よし。つかfibの計算時間かかりまくるので、(most-near? fib fibx 100)
とかやると沈黙されるんですけど。ので、
(define (fibr n) (define (iter n-1 n-2 n) (if (= n 1) (+ n-1 n-2) (iter (+ n-1 n-2) n-1 (- n 1)))) (if (<= n 1) n (iter 0 1 n))) (most-near? fibr fibx 50) ; 1 (most-near? fibr fibx 100) ; -1
末尾再帰で書いて、ああ速いなあと喜びます。って、-1返ってきてるなあ。
どこで違ってきてるのか。
(define (most-near? fib fibx last) (define (iter n) (if (= n last) 1 (if (>= (abs (- (fib n) (fibx n))) 0.5) n (iter (+ n 1))))) (iter 0)) ; 71 (fibx 71) ; 3.080615211701297e14 (fibr 71) ; 308061521170129
なんか切り捨てられてんのかなあ。っつうか黄金比によりフィボナッチ数を求める方のfibxの計算精度の問題っぽいかな。
ちゃんとした証明は大事ですね。