SICPゼミ第4回

読んでるpdf

github.com

練習問題1.29

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))
(define (sympthon f a b n)
  (define h (/ (- b a) (* n 1.0)))
  (define (sympthon-term x)
    (+ (* 2.0 (f x)) (* 4.0 (f (+ x h)))))
  (define (sympthon-next x)
    (+ x (* 2.0 h)))
  (* (/ h 3.0)
     (+ (f a) (f b) (* 4.0 (f (+ a h)))
        (sum sympthon-term (+ a (* 2.0 h)) sympthon-next b))))

by tube

(define (cube x) (* x x x))
(define (simpson n f a b)
  (define h (/ (- b a) (* n 1.0)))
  (define (even? x)
    (= (remainder x 2) 0))
  (define (y k) (f (+ a (* k h))))
  (define (simpson-iter k)
    (cond ((= k 0) (+ (y k) (simpson-iter (+ k 1))))
          ((= k n) (y k))
          ((even? k) (+ (* 2 (y k)) (simpson-iter (+ k 1))))
          (else (+ (* 4 (y k)) (simpson-iter (+ k 1))))))
  (* (/ h 3) (simpson-iter 0)))

by pine

(define (simpson f a b n)
	(define (h a b n)
		(/ (- b a) n))
	(define (hoge f a b n)
		(define (even? a) (= (remainder a 2) 0))
		(define (y count) (f (+ a (* count (h a b n)))))
		(define (iter count f a b n result)
			(cond
				((= count n) (+ result (y count)))
				((= count 0) (iter (+ count 1) f a b n (+ result (y count))))
				((even? count) (iter (+ count 1) f a b n (+ result (* 2 (y count)))))
				(else (iter (+ count 1) f a b n (+ result (* 4 (y count)))))))
		(iter 0 f a b n 0))
	(* (/ (h a b n) 3.0) (hoge f a b n)))

by 現実は厳しい

(define (simpson f a b n)
	(define h (/ (- b a) n))
	(define (add-kh n) (+ a (* h n)))
	(define (even? n) 
		(cond
			((= (remainder n 2) 0) #t)
			(else #f))
		)
	(define (hoge i) 
		(cond  ((= i 0) 1.0)
			   ((= i n) 1.0)
			   ((even? i) 2.0)
			   (else 4.0)
			)
		)
	(define (fuga n) 
		(* (hoge n) (f (add-kh n)))
		)
	(* (/ h 3.0) (sum fuga 0 inc n))
	)

by どりきゃす

実行結果

>(sympthon cube 0 1 100)
0.2500000000000003
> (sympthon cube 0 1 1000)
0.2500000000000006

丸め誤差はクソ。
by tube

gosh> (simpson 100 cube 0 1)
0.24999999999999992
gosh> (simpson 1000 cube 0 1)
0.2500000000000003

by pine

gosh> (simpson cube 0 1 100)
0.25000000000000006
gosh> (simpson cube 0 1 1000)
0.25000000000000006
gosh> (simpson cube 0 1 10000)
0.2500000000000001
gosh> (simpson cube 0 1 100000)
0.2500000000000001
gosh> (simpson cube 0 1 1000000)
0.2499999999999983
gosh> (simpson cube 0 1 10000000)
0.24999999999999906

by 現実は厳しい，丸め誤差はクソ

gosh> (simpson cube 0 1 100)
0.24999999999999992
gosh> (simpson cube 0 1 1000)
0.2500000000000002

by どりきゃす

練習問題1.30

(define (sum-iter term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ (term a) result))))
  (iter a 0))

練習問題1.31

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

(define (product-iter term a next b)
  (define (iter-product a result)
    (if (> a b)
        result
        (iter-product (next a) (* (term a) result))))
  (iter-product a 1))

(define (pi-product-term x)
    (* (/ (- x 1) (* x 1.0)) (/ (+ x 1) (* x 1.0))))
(define (pi-product-next x)
    (+ x 2))

(define (pi-product a b)
  (product pi-product-term a pi-product-next b))

(define (pi-iter a b)
  (product-iter pi-product-term a pi-product-next b))

(define (identity a) a)

(define (inc n) (+ n 1))

(define (factorial n)
  (product identity 1 inc n))

実行結果

> (* 4 (pi-product 3 10000))
3.141749737149242
> (* 4 (pi-iter 3 10000))
3.141749737149225

練習問題1.32

(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate combiner null-value term (next a) next b))))
(define (sum term a next b)
  (accumulate + 0 term a next b))
(define (product term a next b)
  (accumulate * 1 term a next b))

(define (accum-iter combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner (term a) result))))
    (iter a null-value))

練習問題1.33

(define (filter-accumulate conditioner combiner null-value term a next b)
	(define (hoge a)
		(if (conditioner a)
			(term a)
			null-value)
		)
	(define (iter a result)
	(if (> a b)
		result
		(iter (next a) (combiner result (hoge a)))))
	(iter a null-value)
	)

実行結果

gosh> (filter-accumulate even? + 0 identity 0 inc 6)
12
gosh> (filter-accumulate even? + 0 square 0 inc 6)
56

by どりきゃす

練習問題1.35

(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2))
       tolerance ))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next ))))
  (try first-guess))

実行結果

> (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
1.6180327868852458

練習問題1.36

#lang racket
(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2))
       tolerance ))
  (define (try guess)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))
(define (report x)
  (newline)
  (display x))

実行結果
平均緩和法なし

> (fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)
2.0
9.965784284662087
3.004472209841214
6.279195757507157
3.759850702401539
5.215843784925895
4.182207192401397
4.8277650983445906
4.387593384662677
4.671250085763899
4.481403616895052
4.6053657460929
4.5230849678718865
4.577114682047341
4.541382480151454
4.564903245230833
4.549372679303342
4.559606491913287
4.552853875788271
4.557305529748263
4.554369064436181
4.556305311532999
4.555028263573554
4.555870396702851
4.555315001192079
4.5556812635433275
4.555439715736846
4.555599009998291
4.555493957531389
4.555563237292884
4.555517548417651
4.555547679306398
4.555527808516254
4.555540912917957
4.555532270803653

平均緩和法使う

> (fixed-point (lambda (x) (/ (+ x (/ (log 1000) (log x))) 2)) 2.0)
2.0
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.555599411610624
4.5555465521473675
4.555537551999825

めっちゃはやい。

練習問題1.37

(define (cont-frac n d k)
	(define (bubun count)
		(cond 
			((= count k) (/ (n count) (d count)))
			(else (/ (n count) (+ (d count) (bubun (+ count 1)))))))
	(bubun 0))

実行結果

gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 1)
0.5
gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 2)
0.6666666666666666
gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 3)
0.6000000000000001
gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 4)
0.625
gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 5)
0.6153846153846154
gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 6)
0.6190476190476191
gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 7)
0.6176470588235294
gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 8)
0.6181818181818182
gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 9)
0.6179775280898876
gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 10)
0.6180555555555556

反復ver.

(define (cont-frac n d k)
	(define (iter n d i result)
		(cond 
			((= i 0) result)
			(else (iter n d (- i 1) (/ (n i) (+ (d i) result)))
			)
			)
		)
	(iter n d k 0)
	)

実行結果

gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 3)
0.6666666666666666
gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 100)
0.6180339887498948
gosh> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 1000)
0.6180339887498948

by どりきゃす

練習問題1.38

> (+ (cont-frac (lambda (i) 1.0)
                (lambda (i)
                  (if (= (remainder i 3) 1)
                      (+ (* (/ i 3) 2) 2)
                      1))
                100)
     2)
2.7625003620428394

練習問題1.39

(define (tan-cf x k)
  (cont-frac
   (lambda (i)
     (if (= i 0) x (* x x -1)))
   (lambda (i) (+ 1 (* 2 i)))
   k))

実行結果

gosh> (tan-cf 1.0 100)
1.557407724654902
gosh> (tan-cf 2.0 100)
-2.185039863261519
gosh> (tan-cf 3.0 100)
-0.14254654307427775
gosh> (tan-cf 4.0 100)
1.1578212823495773

練習問題1.40

(define (deriv g)
  (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
(define dx 0.00001)
(define (newton-transform g)
  (lambda (x) (- x (/ (g x) (( deriv g) x)))))
(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess ))
(define (cubic a b c)
  (lambda (x) (+ (* x x x) (* a x x) (* b x) c)))

実行結果

gosh> (newtons-method (cubic 5 29 37) 1)
-0.7142824489634352
-1.5041120923441227
-1.5662776172915056
-1.566357081511304
-1.5663570816147325
-1.5663570816147325

練習問題1.41

(define (double method)
	(lambda (x) (method (method x))))

練習問題1.42

(define (compose method1 method2)
	(lambda (x) (method1 (method2 x))))

練習問題1.43

(define (repeated method n)
	(cond 
		((= n 1) (lambda (x) (method x)))
		(else (compose method (repeated method (- n 1))))))

計算資源がもったいないお化けが怖い人用

(define (repeated f n)
	(define (even? n) (= 0 (remainder n 2)))
	(define (halve n) (quotient n 2))
	(define (iter f n result)
		(cond
			((= n 0) result)
			((even? n) (iter (double f) (halve n) result))
			(else (iter f (- n 1) (compose f result)))
			)
		)
	(iter f n identity)
	)

練習問題1.46

(define (iterative-improve enough? improve)
  (define (try guess)
    (if (enough? guess)
        guess
      (try (improve guess))))
  (lambda (x) (try x)))
(define (sqrt x)
  (define (improve guess)
    (average guess (/ x guess)))
  (define (average x y)
    (/ (+ x y) 2))
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (square a) (* a a))
  (iterative-improve good-enough? improve) )
(define (good? guess)
  (< (abs (- (square guess) x)) 0.001))
(define (fixed-point f first-guess)
  ((iterative-improve good? f) first-guess))

実行結果

gosh> (sqrt 2)
1.4142156862745097
gosh> (sqrt 4)
2.0000000929222947
gosh> (sqrt 5)
2.2360688956433634
gosh> (sqrt 16)
4.000000636692939

|