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の計算精度の問題っぽいかな。
ちゃんとした証明は大事ですね。

test