연습문제 1.14

가장 깊은 단계는 동전의 단위가 1인 경우 발생한다. 따라서 기억공간은 O(n)으로 커진다.

프로세스 계산단계는 가능한 모든 단계를 검색하므로 지수함수적으로 증가하는 것으로 보인다.
(예: cc(11,5)를 계산하기위해서는 cc(11,1)에서 cc(6,1)이 중복되고 또 내부에서는 cc(1,1)이 중복된다.
또한 cc(1,3)과 cc(6,2)에서는 각각 cc(1,2)가 중복된다.

이 트리는 트리 오른쪽이 길어지는 형식을 취하게 된다.

연습문제 1.13

PI = (1 + sqrt(5)) / 2
PSI = (1 - sqrt(5)) / 2

일때 우선 힌트를 증명해보자..

Fib(n) = (PI^n - PSI^n)/sqrt(5)

임을 증명하자.

먼저 수학적 귀납법으로 증명하기위해 초기조건이 위의 식을 만족함을 보여야한다.

Fib(0) = (PI^0 - PSI^0) / sqrt(5) = (1 - 1) / sqrt(5) = 0 / sqrt(5) = 0
Fib(1) = (PI^1 - PSI^1) / sqrt(5) = ( (1+ sqrt(5))/2 - ((1-sqrt(5))/2) ) / sqrt(5) = (sqrt(5)) / sqrt(5) = 1

따라서 위의 식은 초기조건을 만족한다.
이제 Fib(n-1)항과 Fib(n-2)항이 위의 조건을 만족한다고 가정하고 Fib(n)을 구해보자

정의에 따라 Fib(n) 은

Fib(n) = Fib(n-1) + Fib(n-2) = (PI^(n-1) - PSI^(n-1)) / sqrt(5) + (PI^(n-2) - PSI^(n-2)) / sqrt(5)
= ( (PI+1)*PI^(n-2) - (PSI+1)*PSI^(n-2) ) / sqrt(5)

이다..

PI는 황금비를 나타내는 다음 공식임을 우리는 알고 있다.

PI^2 = PI + 1

또한 PSI또한 다음을 만족한다.

PSI^2 = PSI + 1

실제로 PI와 PSI 는 X^2 - x - 1 = 0 을 만족하는 X의 서로 다른 두 제곱근이다.
그러므로 Fib(n)은

Fib(n) = ( (PI+1)*PI^(n-2) - (PSI+1)*PSI^(n-2) ) / sqrt(5) = (PI^n - PSI^n) / sqrt(5)

 를 만족함을 알 수 있다.
해당하는 힌트를 이제 증명했다.
PSI값의 실제 값은

-0.61803398874989484820458683436564

이며 이 값의 절대값은 1보다 작으므로
n이 증가할 때 PSI^n은 0에 수렴한다.
따라서 n이 충분히 크다면

Fib(n) = PI^n / sqrt(5)

와 유사한 값을 가지게 된다.

연습문제 1.12

Pascal Triangle을 다음과 같이 변형해보자

0 1 0 0 0 0
0 1 1 0 0 0
0 1 2 1 0 0
0 1 3 3 1 0
0 1 4 6 4 1
...

각 행렬을 표시해보면 m번째 행의 n번째 열의 값은 m-1번째 행의 n번째 열과 n-1번째 열의 합임을 알 수 있다.
또한 0번째 열의 값은 0이며 n>m인 모든 m행의 n열의 값은 0 임도 알 수 있다.

이를 토대로 하면..

f(n, m) ->
    n < 1 이면 0
    n = 1 이면 1
    n > m 이면 0
    그 이외에는 f(n-1, m-1) + f(n, m-1)

이므로 해당하는 코드는

; ex 1.12
(define (pas_tri x y)
  (cond ((= x 1) 1)
        ((< x 1) 0)
        ((> x y) 0)
        (else (+ (pas_tri x (- y 1))
                       (pas_tri (- x 1) (- y 1))))))

이렇게 하면 행과 열을 알면 해당 배열의 값을 알아낼 수 있다.

연습문제 1.11

; ex 1.11
(define (f1_11 n)
  (cond ((< n 3) n)
        (else (+
               (f1_11 (- n 1))
               (* 2 (f1_11 (- n 2)))
               (* 3 (f1_11 (- n 3)))))))

반복(Iteration)형태의 문제는 초기조건, 반복조건, 반복 수를 명시해야하는 것을 명심해야한다.
여기서는 계산이 불가능한 f(0), f(1), f(2)를 모두 넣어두었다.

(define (f1_11_iter n)
  (define (iter a0 a1 a2 t)
    (cond ((= t 0) a0)
          ((= t 1) a1)
          ((= t 2) a2)
          (else
           (iter a1 a2 (+ a2 (* 2 a1) (* 3 a0)) (- t 1)))))
  (iter 0 1 2 n))

사실 이 방법보다도 좀 더 효율적인 방법이 있을 것이라고 생각은 드는데..
명확한 답은 안떠오른다... 난감.. ㅡ.ㅡ

연습문제 1.10

(A 1 10)
-> (A (- 1 1) (A 1 (- 10 1))) -> (A 0 (A 1 9))
-> (* 2 (A 1 9))
-> (* 2 (A (- 1 1) (A 1 8))) -> (* 2 (A 0 (A 1 8))
-> (* 2 (* 2 (A 1 8)))
....
-> (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 1 1))))))))))
-> (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 2))))))))
-> 1024

따라서 (A 1 10)은 2^n 이다

(A 2 4)
-> (A (- 2 1) (A 2 (- 4 1)) -> (A 1 (A 2 3))
-> (A 1 (A (- 2 1) (A 2 (- 3 1)))) -> (A 1 (A 1 (A 2 2)))
-> (A 1 (A 1 (A (- 2 1) (A 2 (- 2 1)))) -> (A 1 (A 1 (A 1 (A 2 1))))
-> (A 1 (A 1 (A 1 2)))
(위에서 (A 1 n)은 2^n임을 알므로
-> (A 1 (A 1 4))
-> (A 1 16)
-> 65536

(A 3 3)
-> (A (- 3 1) (A 3 (- 3 1))) -> (A 2 (A 3 2))
-> (A 2 (A 2 (A 3 1))
-> (A 2 (A 2 2))
-> (A 2 (A 1 (A 2 1)))
-> (A 2 (A 1 2))
-> (A 2 4)
-> 65536

(define (f n) (A 0 n)) 은 2n이다.
(define (g n) (A 1 n)) 은 2^n이다.
(define (h n) (A 2 n)) 은 초항이 2이며 a(n) = 2^a(n-1)인 급수와 같다.
즉 (A 2 4)는 a(4) = 2^a(3)
a(3) = 2^a(2)
a(2) = 2^a(1) = 2^2 =  4
A(3) = 2^4 = 16
a(4) = 2^16 = 65536 이다.

연습문제 1.9

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

의 경우부터 보자면..

(+ 4 5)
-> (inc (+ (dec 4) 5)) -> (inc (+ 3 5))
-> (inc (inc (+ (dec 3) 5))) -> (inc (inc (+ 2 5)))
-> (inc (inc (inc (+ (dec 2) 5)))) -> (inc (inc (inc (+ 1 5))))
-> (inc (inc (inc (inc (+ (dec 1) 5 ))))) -> (inc (inc (inc (inc (+ 0 5)))))
-> (inc (inc (inc (inc 5))))
-> (inc (inc (inc 6)))
-> (inc (inc 7))
-> (inc 8)
-> (inc 9)

따라서 이는 되도는 형태이다.

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

의 경우는

(+ 4 5)
-> (+ (dec 4) (inc 5)) -> (+ 3 6)
-> (+ (dec 3) (inc 6)) -> (+ 2 7)
-> (+ (dec 2) (inc 7)) -> (+ 1 8)
-> (+ (dec 1) (inc 8)) -> (+ 0 8)
-> 8

따라서 이는 반복하는 형태이다.

연습문제 1.8

뉴튼 메서드에 관련된 사항이 잘못된것 같다.

(x + y*y + 2y) / 3 이 아니고

(x/y*y + 2y) / 3이 맞는거 같음

이 경우 해법은

(define (cube x) (* x x x))

(define (cube-root guess x)
  (if (good-enough-cube? guess x)
      guess
      (cube-root (improve-cube guess x) x)))

(define (improve-cube guess x)
  (/  ( + (/ x (square guess)) (* 2 guess)) 3))

(define (good-enough-cube? guess x)
  (< (abs (- (cube guess) x)) 0.001))

과 같이 풀 수 있음