sicp(5)m1.34〜m1.39

(更新したのは26日です。upするの忘れてました＞＜)

;1.3.2
(define (sum term a b next)
  (if (> a b)
      0
      (+ (term a) (sum term (next a) b next))))
(define (integral f a b dx)
  (* (sum f
          (+ a (/ dx 2.0))
          b
          (lambda (x) (+ x dx)))
     dx))
	;;gosh> (integral (lambda (x) (* x x x)) 0 1 0.01)
	;;0.24998750000000042

(define (square x) (* x x))
(define (f x y)
  ((lambda (a b)
    (+ (* x (square a))
       (* y b)
       (* a b)))
  (+ 1 (* x y))
  (- 1 y)))
;;letを使うと↓のようになる。
(define (f2 x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
       (* y b)
       (* a b))))

;練習(本に書いてあるコードを写す）
(define boa 5)
(+ (let ((boa 3))
     (+ boa (* boa 10)))
   boa) ;=>38

;;m1.34
(define (f g)
  (g 2))
(f square)
;=> 4
(f (lambda (z) (* z (+ z 1))))
;=> 6

;どっちでも同じになった。
;;<1>作用的順序の場合
	;;(f f)
	;;(f 2)
	;;(2 2)
;;<2>正規順序の場合
	;;(f f)
	;;(f 2)
	;;(2 2)

;m1.3.3
(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enogh? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))
(define (close-enogh? x y)
  (< (abs (- x y)) 0.001))

(define (average x y) (/ (+ x y) 2))

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of opposite sign" a b)))))
	;;(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
	;;                      1.0
	;;                      2.0) ;=> 1.89306640625

;;search-fixed-point(x=f(x)) -> (till enough? f(f(x))); fを増やす
(define tolerance 0.00001)

(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))
	;;(fixed-point cos 1.0)
	;;=>0.8575532158463934

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y)) 1.0)) ;;収束しないので無限ループ
	;; y=√x => y^2=x
	;;            y=x/y
	;;           2y=x/y +y
	;;            y=(y + x/y)/2 ;;average damping
(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y))) 1.0))

;;m1.35
	;;θ=(1+√5)/2 ＝x->1+1/xの不動点
	;;(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
	;;=>1.6666666666666665
	;;  ruby -e '(1+Math::sqrt(5))/2' =>1.61803398874989

;;m1.36
	;;y=x^x => logx(y)=x
	;;     ln(y)/ln(x)=x
	;;               x=ln(y)/ln(x)
;;fixed-pointを修正
(define (fixed-point f first-guess)
  (define (close-enogh? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess count)
    (display count) (display " --- ") (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enogh? guess next)
             next
             (try next (+ 1 count)))))
  (try first-guess 1))
	;;gosh> (fixed-point (lambda (x) (/ (log 1000) (log x))) 4)
	;;1 --- 4
	;;...
	;;29 --- 4.555530430629037
	;;4.555539183677709
;;平均緩和を使う。
	;;x=ln(y)/ln(x)
	;;x=(ln(y)/ln(x)+x)/2
	;;(define (average a b) (/ (+ a b ) 2))
	;;(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 4)
	;;gosh> (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 4)
	;;1 --- 4
	;;2 --- 4.491446071165521
	;;...
	;;7 --- 4.5555268862194875
	;;4.5555342036887705
;;m1.37
;(a.)
(define (cont-frac n d k)
  (define (f i)
    (let ((nk (n i))
          (dk (d i)))
      (if (= k i)
          (/ nk dk)
          (/ nk (+ (f (+ i 1)) dk)))))
    (f 1))
;;0側から数える方法しか思いつかなかった。
;!ruby -e 'x=Math::sqrt 5; y=(1+x)/2; p 1/y' #=>0.618033988749895
;!gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 10)
;!0.6180555555555556
;!gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 9)
;!0.6179775280898876
;;だから、きっと10

;(b.)
;;反復的な方
(define (inc i) (+ i 1))
(define (cont-frac2 n d k)
  (define (iter k result)
    (let ((nk (n k))
          (dk (d k)))
      (if (= 0 k)
          result
          (iter (- k 1) (/ nk (+ dk result))))))
  (iter k 0))
;;m1.38
(define (euler-e k)
  (+ (cont-frac2 (lambda (i) 1.0) next-d k)
     2))
;;next-dで問題の数列を作る
(define (next-d i)
  (let ((x (- i 2)))
        (let ((a (remainder x 3))
              (b (/ x 3)))
          (cond ((= i 1) 1)
                ((= i 2) 2)
                ((= a 0) (+ (* 2 b) 2 ))
                (else 1)))))
;;next-dのテスト用の関数
(define (f from to)
  (cond ((= from to) "done")
        (else
         (display (next-d from)) (display " ")
         (f (inc from) to))))
;!gosh> (f 1 20)
;!1 2 1 1 4 1 1 6 1 1 8 1 1 10 1 1 12 1 1 "done"
;;できているみたいなので、これを使って計算。
;!(euler-e 100)
;!2.7182818284590455

;;m1.39
(define (tan-cf x k)
  (define (n i)
    (if (= i 1)
        x
        ((lambda (n) (* n n)) x)))
  (define (d i)
    (- (* 2 i) 1))
  (cont-frac n d k))

;;再びm1.38
;![1,2,1],[1,4,1]と考えれば良いじゃないか。
(define (euler-e2 k)
  (define (d k)
    (if (= (remainder k 3) 2)
        (* 2 k)
        1))
 (+ 2 (cont-frac (lambda (i) 1.0) d k)))