sicp(6)m1.40〜m1.46まで（1章終了）

1章が終わった！

;;復習
;m1.39を何も見ないで解く。
(define (cont-frac n d k op)
  (define (iter result k)
    (let ((dk (d k))
           (nk (n k)))
     (cond ((= k 0)
            result)
           (else
            ;(display dk)
            ;(newline)
            (iter (/ nk (op dk result)) (- k 1))))))
  (iter 0 k))
;;opで演算子を換えられるようにした。
(define (tan-cf x k)
  (cont-frac (lambda (k)
               (if (= k 1)
                   ;((lambda (n) n) x)
                   ((lambda (n) n) x)
                   ((lambda (n) (* n n)) x)))
             (lambda (n) (- (* 2 n) 1))
             k
             -))
;昨日作ったのは間違っているかもしれない。
;	gosh> (tan-cf 1.0 10)
;	1.557407724654902
;	ruby -e 'p Math::tan 1.0' => 1.5574077246549

;1.3.4
(define (average-dump f)
  (lambda (x) (average x (f x))))
(define (square x) (* x x))
(define (average x y) (/ (+ x y) 2))
((average-dump square) 10)
;;-> 55

;平方根の手続き
(define (sqrt x)
  (fixed-point (average-dump (lambda (y) (/ x y)))
               1.0))

;Newton法
;	f(x) = x - (g(x) / Dg(x))
;	  Dg(x) = x->のfixed-point
;	Casion:newton法はいつも収束するとは限らない。（でも、収束した場合には区間二分法より高速)

(define dx 0.00001)
(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))
(define (cube x) (* x x x))
;	gosh> ((deriv cube) 5)
;	75.00014999664018
;;関数に関数を渡してできた関数を使って微分しているイメージ.

;;derivを使ったNewton法。
(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

;これを使って平方根の計算
(define (newton-method g guess)
  (fixed-point (newton-transform g) guess))

(define (sqrt x)
  (newton-method (lambda (y) (- (square y) x))
                    1.0))

(define (fixed-point f first-guess)
  (define (close-enogh? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enogh? guess next)
          next
          (try next))))
  (try first-guess))
(define tolerance (* dx dx)) ;だいたいこれぐらいの数なら十分。きっと。
(sqrt 2)
;	gosh> (sqrt 2)
;	1.4142135623730951

;;一読しただけでは分からない。何やらすごい関数。
(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))
;;これを使って平方根を求める
(define (sqrt2 x)
  (fixed-point-of-transform (lambda (y) (/ x y))
                            average-dump
                            1.0))
;	gosh> (sqrt2 2)
;	1.414213562373095
;;rubyはブロックによって2階関数までは記述できるけど、その先は無理。
;;関数に第１級の身分をあたえている言語だと、いくらでも高階関数を書けるということ？
;;（高階関数って関数に関数を渡せるようなイメージだと思ってます＞＜）

;;m1.40

(define (cubic a b c)
  (lambda (x)    
    (+ (* x x x) (* a x x) (* b x) c)))
;xを引数として受け取る関数にするところが重要。
(define (calc-cubic a b c x)
  (newton-method (cubic a b c) x))
;	gosh> (calc-cubic 1 2 3 1)
;	-1.2756822036509852
;	合っているかどうかは知らない。
;;確かめのためにsicp1.40で検索した。
;;http://www.dais.soft.iwate-pu.ac.jp/~miura/pukiwiki/index.php?SICP%2F%E8%87%AA%E5%88%86%E3%81%AE%E8%A7%A3%E7%AD%94%2F%E5%95%8F%E9%A1%8C1.40
;;この方がいいらしい。
(define (cubic a b c)
  (lambda (x) (+ (* x (+ (* x (+ x a)) b)) c)))
;	(x^3+ax^2+bx+c)
;	=(x(x^2+ax+b)+c)
;	=(x(x(x+a)+b)+c)
;;カッコで括れるものは括っといた方がいいみたい。
;;（計算回数が少なくなる。）

;;m1.41
(define (double f)
  (lambda (x) (f (f x))))
(define (inc x) (+ x 1))
((double inc) 1) ;=>3
;;(((double (double double)) inc) 5)
;	;;はじめに実行しないで考える(double=d)
;	(((d (d d)) inc) 5)
;	(((d 4f)) inc) 5)
;	((4f 4f) inc) 5)
;	((16f inc) 5)
;	((16inc 5)
;	(+ 16 5)
;	21
;	gosh> (((double (double double)) inc) 5)
;	21
;;合ってた！

;;m1.42
;;すごい簡単！
(define (compose f g)
  (lambda (x) (f (g x))))
((compose square inc) 6)
;	gosh> ((compose square inc) 6)
;	49

;m1.43
(define (repeated f n)
    (if (= n 1)
        f
        (compose f (repeated f (- n 1)))))
;;これで完成。
;	gosh> ((repeated square 2) 2)
;	16

;;m1.44
;;この辺はほとんどが類題のような感じなので慣れたのか簡単に解けた
(define (smooth f)
  (lambda (x dx) (/ (+ (f (- x dx))
                       (f x)
                       (f (+ x dx)))
                    3)))
(define (n-smooth f n)
  (repeated smooth n))

;;m1.45
(define (sqrt x)
  (fixed-point (average-dump (lambda (y) (/ x y)))
               1.0))
;;lambda (y)の部分以外は簡単につくれる。その先はどうやって作ったんだろ？
;	  y^2=x
;	 2y^2=x+y^2
;	    y=(x+y^2)/2*y
;	    y=((x/y)+y)/2
;	;3乗根の場合
;	  y^3=x
;	 2y^3=x+y^3
;	    y=((x/y^2)+y)/2
;;ということで、lambdaの部分も判明。
(define (n-count-rootx n count x)
  (define (f a n)
    (if (= n 0)
        1
        (* a (f a (- n 1)))))
  (fixed-point ((repeated average-dump count)
                (lambda (y) (/ x (f y (- n 1)))))
                1.0))
;できた
;       gosh> (n-count-rootx 3 2 27)
;	3.0000000000223412
;後は実験実験。
;;楽な方法が思いつかないのでパス。
;;(求まらないときにどうすればいいか分からないし…）
;	（「時間を計って何秒以内に求まらなければ次」みたいなループの作り方が分からない)

;;m1.46
(define (iterative-improve good-enough? improve)
  (lambda (guess)
    (define (f guess)
      (if (good-enough? guess)
          guess
          (f (improve guess))))
    (f guess)))
;	lambdaで作ったものを再帰的に使いたかった。
;	でもどうすればいいのか分かりませんでした。＞＜

;;fixed-point
(define tolerance 0.00001) ;てきとー
(define (fixed-point2 f first-guess)
  (define (good-enough? v)
    (< (abs (- v (f v))) tolerance))
  ((iterative-improve good-enough? f) first-guess))

(define (sqrt4 x)
  (fixed-point2 (lambda (y) (/ (+ y (/ x y)) 2)) 1.0))
;	gosh> (sqrt4 2)
;	1.4142156862745097
;;よし、ok
;;sqrt4の中でも間接的に iterative-improveを使っているからこれでいいよね？きっと。