연습문제 1.17

일단 halve와 double을 임시로 만들자

(define (halve x) (/ x 2))
(define (double x) (* x 2))

b가 짝수인 경우 a*b = 2 * a * (b / 2)이고
b가 홀수인 경우 a*b = a + a*(b-1)과 같다.

이를 프로시저로 정의하면

(define (mul a b)
  (if (= b 0)
      0
      (cond ((even? b) (double (mul a (halve b))))
            (else (+ a (mul a (- b 1)))))))

과 같다

연습문제 1.16

b^n을 구할 때 n 이 짝수인 경우와 n이 홀수인 경우를 나누면 된다.
짝수인 경우는 다음 단계에 넘길 수는 현재 단계 밑수의 제곱과 그 단계수를 1/2로 나눈수면 된다.
따라서

(define (fast-expt b n)
  (define (fast-expt-iter b counter product)
    (cond ((= counter 0) product)
          ((even? counter) (fast-expt-iter (* b b)
                                     (/ counter 2)
                                     product))
          (else (fast-expt-iter b
                                (- counter 1)
                                (* product b)))))
  (fast-expt-iter b n 1))

가 된다.

연습문제 1.15

a.

(sine 12.15)
= (p (sine 4.05))
= (p (p (sine 1.35)))
= (p (p (p (sine 0.45))))
= (p (p (p (p (sine 0.15)))))
= (p (p (p (p (p (sine 0.05)))))

p 프로시저는 5번 쓰인다.


b.
위에서 보는 것처럼 해당하는 값은 3에 비례해서 감소한다. 또한 이 함수는 선형으로 증가하므로 기억공간과 계산 단계는 동일한 자람 함수를 보인다. 따라서 기억공간과 계산단계의 자람함수는 O(log3a)가 된다.

연습문제 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))

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