S.O.W - SICPお勉強Wiki

Exercises 1.2

最終更新：2010年02月18日 01:03

tar0_puzzle

- view

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

Chapter 1.2

Exercise 1.9

;; former=>recursive
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (int (inc (+ 1 5))))
(inc (inc (inc (inc 5))))
;; latter=>iterative
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)

Exercise 1.10

(A 1 10)=>1024
(A 2 4)=>65536
(A 3 3)=>65536
;;  hが面倒なのでSchemeで表記
(define (f n) (* 2 n))
(define (g n) (expt 2 n))
(define (h n) (if (> n 1) (expt 2 (h (- n 1))) 2))

A(1,n)=A(0,A(1,n-1))=2A(1,n-1)
A(1,1)=2
から
$A(1,n)=2^n = 2 \uparrow n = \underbrace{2 \times 2 \times \cdots \times 2}_{n}$

A(2,n)=A(1,A(2,n-1))=2^A(2,n-1)
A(2,1)=2
から
$A(2,n)=\underbrace{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}_{n} = 2 \uparrow \uparrow n$

同じように
$A(3,n) = \underbrace{2 \uparrow \uparrow 2 \uparrow \uparrow \cdots \uparrow \uparrow 2}_{n} = 2 \uparrow \uparrow \uparrow n$

Wikipedia:テトレーション参照

Exercise 1.11

(define (f n)
  (iter-f 2 1 0 n))
(define (iter-f a b c n)
  (if (= n 0)
      c
      (iter-f (+ a (* 2 b) (* 3 c)) a b (- n 1))))

Exercise 1.12

(define (pascal-triangle n)
  (if (= n 1)
      (cons 1 '())
      (map + (chain (pascal-triangle (- n 1))) (cons 0 (pascal-triangle (- n 1))))))
(define (chain ls)
  (if (eqv? (cdr ls) '())
      (cons (car ls) '(0))
      (cons (car ls) (chain (cdr ls)))))

Exercise 1.13

方針だけメモ
fib(n+2)-B*fib(n+1) = A*(fib(n+1)-B*fib(n))
と変形できたとすれば
fib(n+1)-B*fib(n) = (fib(2)-B*fib(1))*A^(n-1) = A^n
両辺をB^nで割ると G(n) = fib(n)/B^(n-1) とおいて
G(n+1)-G(n) = (A/B)^n
Σ[k=1,n-1]G(k) = G(n) - G(1)
を解けばよいはず

Exercise 1.14

Exercise 1.19

(define (fib-iter a b p q cnt)
  (cond ((= cnt 0) b)
        ((even? cnt) (fib-iter a b (p2 p q) (q2 p q) (/ cnt 2)))
        (else (fib-iter
                (+ (* b q) (* a q) (* a p))
                (+ (* b p) (* a q)
                p q (- cnt 1)))))
(define (p2 p q) (+ (* p p) (* q q)))
(define (q2 p q) (+ (* 2 p q) (* q q)))

(a',b') = Tpq * (a,b) = (bq + a(p+q), bp + aq) とすると, Tpqは線形変換.
Tpq は2x2の行列として表せるのでTpq^2を計算すればよい

$\left( \begin{array}{c} a' \\ b' \\ \end{array} \right) = T_{p,q} \left( \begin{array}{c} a \\ b \\ \end{array} \right) = \left( \begin{array}{cc} x & y \\ z & w \\ \end{array} \right) \left( \begin{array}{c} a \\ b \\ \end{array} \right)$