SICP(Structure and Interpretation of Computer Programs) Exercise 1.11~1.20

Exercise 1.11

(define (exam n)

  (cond ((< n 3) n)

        (else (+ (exam (- n 1)) (* 2 (exam (- n 2))) (* 3 (exam (- n 3)))))))

(exam 10)

(define (exam-iter a b c count)

  (if (< count 3)

      a

        (exam-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

(define (exam2 n)

  (exam-iter 2 1 0 n))

(exam2 10)

Exercise 1.12

(define (f a b)

  (cond ((= b 1) 1)

        ((= a b) 1)

        (else (+ (f (- a 1) (- b 1)) (f (- a 1) b)))))

(f 2 2)

(f 4 3)

(f 4 1)

(f 5 3)

Exercise 1.13

f(n)이 phi^n/sqrt(5)에 근사함을 증명하라

힌트 : phi = (1+sqrt(5))/2, psi = (1-sqrt(5))/2, 귀납법을 사용하라, 피보나치 정의를 이용해 f(n)= (phi^n-psi^n)/sqrt(5) 를 증명

피보나치 수열 정의에 따라 f(n+2) = f(n+1) + f(n) 이므로

(phi^(n+1)-psi^(n+1))/sqrt(5) + (phi^n-psi^n)/sqrt(5)

=[(phi^(n+1)-psi^(n+1))+(phi^n-psi^n)]/sqrt(5)

=[(phi*phi^n-psi*psi^n)+(phi^n-psi^n)]/sqrt(5)

=[(phi+1)*phi^n-(psi+1)*psi^n)]/sqrt(5) 이다.

또한 (phi^(n+2)-psi^(n+2))/sqrt(5) 

= (phi^2*phi^n-psi^2*psi^n)/sqrt(5) 이고, 이것이 위 식과 같아야 한다.

따라서 phi+1 = phi^2 와 psi+1=psi^2가 성립해야 한다.

그런데 직접 계산해보면 성립 한다.

따라서 f(n)= (phi^n-psi^n)/sqrt(5) 가 합당하다.

여기서  |psi| < 1 이므로 psi^n에서 n이 무한대라면 0으로 수렴한다.

따라서 f(n)이 phi^n/sqrt(5)에 근사한다.

Exercise 1.16

(define (even? n)

  (= (remainder n 2) 0))

(define (exp_iter b n a)

  (cond ((= n 0) a)

        ((even? n) (exp_iter (square b) (/ n 2) a))

        (else (exp_iter b (- n 1) (* a b)))))

Exercise 1.17

(define (even? n)

  (= (remainder n 2) 0))

(define (exp_iter b n a)

  (cond ((= n 0) a)

        ((even? n) (exp_iter (square b) (/ n 2) a))

        (else (exp_iter b (- n 1) (* a b)))))

Exercise 1.18

  (define (fast2* a b n) 

   (cond ((= n 0) a) 

         ((even? n) (fast2* a (double b) (halve n)))

         (else (fast2* (+ a b) b (- n 1)))))

Exercise 1.19

(+ (square p) (square q)) 

                    (+ (* 2 p q) (square q)) 

Exercise 1.20

normal:18번

applicative:4번