S.O.W - SICPお勉強Wiki

Exercises 1.3

最終更新：2010年03月01日 17:37

tar0_puzzle

- view

メンバー限定登録/ログイン

Chapter 1.3

Exercise 1.29

(define (simpson f a b n)
  (if (and (> n 0) (even? n)) (simpson-in f a b (/ (- b a) n))
    (simpson f a b (+ n 1))))
(define (simpson-in f a b h)
  (define (g x) (+ (f x) (* 2 (f (+ x h)))))
  (define (add-2h x) (+ x h h))
  (/ (* h
	(+ (f a)
	   (f b)
	   (* 4 (f (+ a h)))
	   (* 2 (sum g (add-2h a) add-2h (- b h)))))
     3))

simpson手続きはnが2以上の偶数になるまで, +1し続ける
sum手続きの中身は, n≧2のとき下のΣの中身と同じ. n=2のときはf(a)+4f(a+h)+f(b)になる.
シンプソンの公式

$\int_{a}^{b}f \approx \frac{h}{3} \left( f(a) + 4f(a+h) + 2\sum_{k=1}^{n/2-1} \left( f(a+2kh) + 2f\left( a+(2k+1)h \right) \right + f(b) \right)$

Exercise 1.30

(define (sum f a next b)
  (define (iter a result)
    (if (> a b) result
      (iter (next a) (+ result (f a)))))
  (iter a 0))
; 評価の順序は違う
; 和が可換なので結果は同じ
; recursive
;(sum identity 1 inc 5)
;(+ 1 (+ 2 (+ 3 (+ 4 (+ 5 0)))))
;= 1+(2+(3+(4+(5+0))))
; iterative
; result <-- (+ 0 1)
; result <-- (+ result 2)
; result <-- (+ result 3)
; result <-- (+ result 4)
; result <-- (+ result 5)
;=((((0+1)+2)+3)+4)+5

結合法則が成り立つなら結果は同じ

Exercise 1.31

;; recursive
(define (product f a next b)
  (if (> a b) 1 (* (f a) (product f (next a) next b))))
 
;; iterative
(define (product-iter f a next b)
  (define (iter a result)
    (if (> a b) result (iter (next a) (* result (f a)))))
  (iter a 1))
 
; Wallis Formula
(define (pi-product n)
  (define (square x) (* x x))
  (define (pi-term k) (/ (* 4.0 k (+ k 1)) (square (+ k k 1))))
  (define (pi-next x) (+ x 1))
  (* 4 (product pi-term 1 pi-next n)))

$\frac{\pi}{4} = \prod_{k=1}^{\infty} \frac{2k \left( 2k+1 \right) }{ \left( 2k+1 \right)^2 }$

Wallisの公式

$\prod_{k=1}^{\infty} \frac{(2k)^2}{(2k-1)(2k+1)} = \lim_{n \to \infty} \frac{1}{2n+1} \prod_{k=1}^{n} \frac{(2k)^2}{(2k-1)^2} = \frac{\pi}{2}$

$\lim_{n \to \infty} \frac{n+1}{2n+1} = \frac{1}{2}$

どちらも収束するから

$\lim_{n \to \infty} \frac{n+1}{(2n+1)^2} \prod_{k=1}^{n} \frac{(2k)^2}{(2k-1)^2} = \lim_{n \to \infty} \prod_{k=1}^{n} \frac{2k(2k+2)}{(2k+1)^2} = \frac{\pi}{4}$

Exercise 1.32

;; recursive
(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))))
;; iterative
(define (accumu-iter combiner initial-value f a next b)
  (define (iter a result)
    (if (> a b) result
      (iter (next a) (combiner result (f a)))))
  (iter a initial-value))
 
(define (sum f a next b) (accumulate (lambda (x y) (+ x y)) 0 f a next b))
(define (product f a next b) (accumulate (lambda (x y) (* x y)) 1 f a next b))

Exercise 1.33

長い...

(define (filter-accumu filter combiner null-value term a next b)
  (if (> a b) null-value
      (let ((fx (term a)))
        (if (filter fx) (combiner fx (filter-accumu filter combiner null-value term (next a) next b))
            (filter-accumu filter combiner null-value term (next a) next b)))))
(define (product-rel-prime n)
  (filter-accumu (lambda (x) (= (gcd x n) 1))
                 (lambda (x y) (* x y))
                 1
                 (lambda (x) x)
                 1
                 (lambda (x) (+ x 1))
                 n))

Exercise 1.36

(define (fixed-point-print f guess)
  (define (print-line i x)
    (display i) (display ":") (display x) (newline))
  (define (try cnt x)
    (let ((next (f x)))
      (if (close-enough? x next) next
	((lambda ()
	   (print-line cnt x)
	   (try (+ cnt 1) next))))))
  (try 1 guess))
(define (average x y) (/ (+ x y) 2))
(define (average-dump f) (lambda (x) (/ (+ x (f x)) 2)))
(define (ex136a)
  (fixed-point-print (lambda (x) (/ (* 3 (log 10)) (log x))) 2.0))
(define (ex136b)
  (fixed-point-print
   (average-dump (lambda (x) (/ (* 3 (log 10)) (log x))))
   2.0))
;;(136a)
;;=> 33step 4.555532270803653
;;(136b)
;;=> 8step 4.555537551999826

Exercise 1.37

; continued fraction
;; (cf n d k) = (/ n1 (+ d1 (/ n2 (+ d2 ... (/ nk (+ dk 0))...))))
;
(define (cf n d k)
  (define (cf-helper i)
    (if (> i k) 0
      (/ (n i) (+ (d i) (cf-helper (+ i 1))))))
  (cf-helper 1))
;; iterative
;; (cf n d k)
;; result <-- (/ (n k) (+ (d k) 0))
;; result <-- (/ (n (- k 1)) (+ (d (- k 1)) result))
;; result <-- (/ (n (- k 2)) (+ (d (- k 2)) result))
;; ...
;; result <-- (/ (n 1) (+ (d 1) result))
;; accumulateでもよさそう?
(define (cf-iter n d k)
  (define (iter i result)
    (if (< i 1) result
      (iter (- i 1) (/ (n i) (+ (d i) result)))))
  (iter k 0))
 
(define (inversed-golden-ratio k)
  (cf (lambda (i) 1.0) (lambda (i) 1.0) k))
;;(inversed-golden-ratio 100)
;;=> 0.6180339887498948

Continued-Fractionのページ

Exercise 1.38,39

;-- ex.1.38
;; Euler's contnued-fraction expansion of e
;
(define (euler-e k)
  (+ 2 (cf (lambda (i) 1.0) 
	   (lambda (i) (if (= (remainder i 3) 2)
			   (* (+ (quotient i 3) 1) 2.0)
			 1.0))
	   k)))
 
;-- ex.1.39
;; continued-fraction expansion of tan(x)
; by J.H.Lambert (1770)
;
;http://mathworld.wolfram.com/Tangent.html
(define (tan-cf x k)
  (/ x (+ 1 (cf (lambda (i) (* x x -1))
		(lambda (i) (+ i i 1))
		k))))

Exercise 1.41

; (double arg)はargを2回適用する手続きを返す
; (double double)はdoubleを2回適用する手続きを返す == argを4回適用する手続きを返す手続き
;; (define (quadruple arg) (lambda (x) (arg (arg (arg (arg x)))))) と同じ
; (double (double double)) は (double double)を2回適用する手続きを返す
;
;--訂正:2010-3-1
;= (lamda (proc) (quadruple (quadruple proc)))と同じ
;= (lambda (proc) (lambda (x) (quadruple (proc (proc (proc (proc x))))))
;= (lambda (proc) (lambda (x) (proc (proc (… (proc x) …)))))
;= procを16回適用する手続きを返す手続き
;
;**ここからウソついた. ので上に訂正 2010-3-1
; (quadruple (quadruple (quadruple (quadruple arg)))) と同じ
;**ここまで.
; (((double (double double)) inc) 5)
;=> 5+16=21

Exercise 1.46

(define (iterative-improve good-enough? improve)
  (define (iter f guess)
    (if (good-enough? guess) guess
      (iter f (improve guess))))
  ((lambda (x) x) iter))
 
(define (fixed-point-2 f guess)
  (define tolerance 0.00001)
  (define (close-enough? guess) (< (abs (- guess (f guess))) tolerance))
  ((iterative-improve close-enough? f) f guess))

「Exercises 1.3」をウィキ内検索

S.O.W - SICPお勉強Wiki

記事メニュー

リンク

Today: 2026-07-01 00:22:51 (Wed)

更新履歴

取得中です。

最近更新されたスレッド

+新規スレッドを作成する

最近更新されたページ

急上昇Wikiランキング

急上昇中のWikiランキングです。今注目を集めている話題をチェックしてみよう！

新規Wikiランキング

最近作成されたWikiのアクセスランキングです。見るだけでなく加筆してみよう！

人気Wikiランキング

atwikiでよく見られているWikiのランキングです。新しい情報を発見してみよう！

全体ページランキング

最近アクセスの多かったページランキングです。話題のページを見に行こう！