연습문제 1.44

smooth는 해당하는 함수 f의 인자를 각각 x-dx, x, x+dx를 넣고 이 결과값을 3으로 나눈 값을 돌려줄 수 있으면 된다.

(define (smooth f)
  (lambda (x)
    (/
     (+
      (f (+ x dx))
      (f x)
      (f (- x dx)))
     3.0)))

이제 n-fold-smooth는 repeated를 이용해서 smooth를 n번 반복하면 되므로

(define (n-fold-smooth f n)
  (repeated (smooth f) n))

같이 정의할 수 있다.

연습문제 1.43

repeated는 일정 갯수만큼 compose를 계속 호출하면 된다. 따라서..

(define (repeated f n)
  (if (= n 1)
      (lambda (x)
        (f x))
      (compose f (repeated f (- n 1)))))

연습문제 1.42

compose는 순차대로 g를 실행하고 f를 실행하는 프로시저를 돌려주면 되며, 이때 필요로 하는 인자는 하나이므로 lambda내의 인자는 하나면 된다.

(define (compose f g)
  (lambda (x) (f (g x))))

연습문제 1.41

double은 다음과 같이 정의된다.

(define (double f)
  (lambda (x) (f (f x))))

(double double)은 이전에 double을 두번더 반복하므로 총 4번의 double이 생긴다.
이제 (double (double double))은 총 4번의 double을 다시 한번 더 반복하므로 8번의 double이 생긴다.
마지막으로 inc를 다시 반복하므로 총 16번의 double이 생긴다.

> (((double (double double)) inc) 5)
21
/>

연습문제 1.40

cubic은 다음과 같이 정의 가능하다

(define (cubic a b c)
  (lambda (x)
    (+ (cube x)
       (* a (square x))
       (* b x)
       c)))

연습문제 1.39

(define (tan-cf x k)
  (define (inner-tan i)
    (/
     (if (= i 1)
         x
         (square x))
     (- (- (* i 2) 1)
        (if (= i k)
            0
            (inner-tan (+ i 1))))))
  (inner-tan 1))

연습문제 1.38

준식의 Ni는 모든 경우에 1이며
Di는 (n+1)항이 3의 배수인 경우 (n+1)과 3의 몫의 두배와 같다.

따라서 해당하는 식은

> (cont-frac-iter (lambda (i) 1.0)
                  (lambda (i)
                    (let ((i+1 (+ i 1)))
                      (if (= (remainder i+1 3) 0)
                          (* 2 (/ i+1 3))
                          1.0)))
                  10)
0.7182817182817183

이며 이 값은 e-2와 같다.

연습문제 1.37

a.
연속 분수 cont-frac는 다음과 같이 표시할 수 있다.

(define (cont-frac n d k)
  (define (inner-cont-frac i)
    (let ((ni (n i))
          (di (d i)))
      (if (= i k)
          (/ ni di)
          (/ ni (+ di (inner-cont-frac (+ i 1)))))))
  (inner-cont-frac 1))

또한 1/pi의 값은

> (/ 2 (+ 1 (sqrt 5)))
0.6180339887498948

이다.
소수점 4자리까지 맞아 떨어지려면 최소한 0.6180이 되어야한다.

> (cont-frac (lambda (i) 1.0)
             (lambda (i) 1.0)
             11)
0.6180555555555556

k가 11이면 소수점 4자리까지 맞아떨어지는 것을 알 수 있다.

b. cont-frac을 반복형으로 만들면

(define (cont-frac-iter n d k)
  (define (iter-cont-frac i result)
    (let ((ni (n i))
          (di (d i)))
      (if (= i 0)
          result
          (iter-cont-frac (- i 1)
                          (/ ni (+ di result))))))
  (iter-cont-frac k 0))

와 같다.

연습문제 1.36

변경된 fixed-point는 아래와 같다.

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (newline)
    (display guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

이제 주어진 식 x->log(1000)/log(x)의 고정점을 찾아보자.

> (fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)

2.0
9.965784284662087
3.004472209841214
6.279195757507157
3.759850702401539
5.215843784925895
4.182207192401397
4.8277650983445906
4.387593384662677
4.671250085763899
4.481403616895052
4.6053657460929
4.5230849678718865
4.577114682047341
4.541382480151454
4.564903245230833
4.549372679303342
4.559606491913287
4.552853875788271
4.557305529748263
4.554369064436181
4.556305311532999
4.555028263573554
4.555870396702851
4.555315001192079
4.5556812635433275
4.555439715736846
4.555599009998291
4.555493957531389
4.555563237292884
4.555517548417651
4.555547679306398
4.555527808516254
4.555540912917957

4.555532270803653

35단계를 거친다.

이제 평균을 구해 그 값을 통해 구해보면..

> (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2.0)

2.0
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.555599411610624
4.5555465521473675
4.555537551999825

10단계를 거치게된다.

연습문제 1.35

fixed-point 를 이용해 x->1+1/x 함수의 고정점을 구하면 다음과 같다.

/> (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)

1.6180327868852458

연습문제 1.34

(define (f g) (g 2))

로 하고

(f f)

를 실행기에서 계산하면

-> (f 2)

-> (2 2)

결국 2라는 함수를 찾을 수 없으므로 에러를 낸다.

연습문제 1.33

(define (filtered-accumulate predicate combiner null-value term a next b)
  (if (> a b)
      null-value
      (filtered-accumulate predicate
                           combiner
                           (cond
                             ((predicate a) (combiner (term a) null-value))
                             (else null-value))
                                          
                           term
                           (next a)
                           next
                           b)))

(define (square-of-prime a b)
  (filtered-accumulate prime? + 0 square a inc b))

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))


(define (seed? n i)
  (= (gcd n i) 1))

(define (product-of-seed n)
  (define (seed? i)
    (= (gcd n i) 1))
  (filtered-accumulate seed? * 1 identity 1 inc (- n 1)))

연습문제 1.32

a.

(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (accumulate combiner (combiner (term a) null-value) term (next a) next b)))
      
(define (sum2 term a next b)
  (accumulate + 0 term a next b))

(define (product2 term a next b)
  (accumulate * 1 term a next b))

b.

(define (acc-iter combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (term a)))))
  (iter a null-value))

연습문제 1.31

a. product는 sum을 흉내내어 만들면 다음과 같다.

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

존 월리스의 공식의 각 항은 (n-1)*(n+1)/n*n 으로 둘 수 있으며 초항은 3부터.. 다음항부터는 2씩 증가하는 형태로 볼 수 있다.
따라서 pi/4를 구하는 함수는

(define (square x) (* x x))

(define (leap-by-2 x) (+ x 2.0))

(define (pi-product-term x)
  (/ (* (- x 1) (+ x 1)) (square x)))

(define (quater-pi n)
  (product pi-product-term 3.0 leap-by-2 n))

처럼 구할 수 있다.
결과는 다음과 같다

> (* 4.0 (quater-pi 10))
3.302393550012597
/> (* 4.0 (quater-pi 100))
3.1573396892175642
/> (* 4.0 (quater-pi 1000))
3.143163842419204
/>

이 함수의 결과가 pi에 수렴함을 알 수 있다.

b. 반복형태로 product를 만들면 다음과 같다.

(define (product-iter term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (term a) result))))
  (iter a 1))

이제 만들어진 product로 pi 함수를 다시 작성하면

(define (quater-pi2 n)
  (product-iter pi-product-term 3.0 leap-by-2 n))

     
이며 이제 이전의 버전과 이번 버전을 비교해보면

> (quater-pi 10)
0.8255983875031493
/> (quater-pi2 10)
0.8255983875031493
/> (quater-pi 100)
0.7893349223043911
/> (quater-pi2 100)
0.7893349223043911

로서 동일한 결과를 얻음을 알 수 있다.

연습문제 1.30

(define (sum-iter term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a)
              (+ result (term a)))))
  (iter a 0))

연습문제 1.29

Simpson의 식을 Scheme으로 표현하면 다음과 같이 갈음할 수 있다.

(define (simpson f a b n)
  (define h (/ ( - b a ) n))
  (define (simpson-term k)
    (* (f (+ a (* k h)))
       (cond ((= k 0) 1.0)
             ((= k n) 1.0)
             ((even? k) 2.0)
             (else k 4.0))))
  (* (/ h 3.0) (sum simpson-term 0 inc n)))

이제 해당식을 n=100일 때와 n=1000일 때로 나누어 구해보면

> (simpson cube 0 1 100)
0.24999999999999992
/> (simpson cube 0 1 1000)
0.2500000000000002
/>

임이 됨을 볼 수 있다.

연습문제 1.27

(define (full-fermat-test n)
  (define (iter a)
    (cond ((= a 1) #t)
          ((= (expmod a n n ) a) (iter (- a 1)))
          (else #f)))
  (iter (- n 1)))

> (full-fermat-test 561)
#t
/> (full-fermat-test 1105)
#t
/> (full-fermat-test 1729)
#t
/> (full-fermat-test 2465)
#t
/> (full-fermat-test 2821)
#t
/> (full-fermat-test 6601)
#t

연습문제 1.26

expmod는 원래대로라면 일반적인 선형적으로 증가하는 재귀호출 함수이다.
문제는 연습문제처럼 풀게된다면 두개의 가지로 구성된 트리 구조식으로 expmod를계산하게 된다.

따라서 자람수 logn 프로시져는 log(a^n)처럼 구성이 되어 결국 자람수 n을 가질 수 밖에 없다.

연습문제 1.25

기본 expmod

10000000000037***2438
10000000000051***2453
10000000000099***2437

Alyssa 버전

10000000000037***2390
10000000000051***2344
10000000000099***2391

기존의 소수가 그대로 출력되며 대략 1~2%정도의 성능 향상이 있다.

연습문제 1.24

start-prime-test를 다음과 같이 수정한다.

(define (start-prime-test n start-time)
  (if (fast-prime? n 10)
        (report-prime n (- (runtime) start-time))))

문제는 random이 받아들이는 수가 2147483647 까지라서 기껏 구한 소수를 넣을 수가 없다. OTL...
 이문제는 당분간 봉인해야겠다.

연습문제 1.23

next의 정의는 다음과 같다

(define (next n)
  (cond ((= n 2) 3)
        (else (+ n 2))))

> (search-for-primes 10000000000 100)

10000000019***63
10000000033***63
10000000061***109
10000000069***78
10000000097***78
/> (search-for-primes 100000000000 100)

100000000003***234
100000000019***266
100000000057***235
100000000063***265
100000000069***235
100000000073***281
100000000091***219
/> (search-for-primes 1000000000000 100)

1000000000039***797
1000000000061***797
1000000000063***1078
1000000000091***797
/>

로 줄어든다.

실제 비율은 0.51~0.54 정도가 걸린다. 정확히 0.5가 되지 않는 이유는 + 는 내장 함수인 반면  next는 사용자 정의 함수이기때문에 실제 실행시간에 의해 생기는 오차정도로 예상한다.

연습문제 1.22

PLT scheme에는 runtime이 없으므로 runtime을 급조

(define (runtime) (current-milliseconds))

(define (search-for-primes start span)
  (cond ((= span 0) (newline))
        ((odd? start)
         (begin
           (timed-prime-test start)
           (search-for-primes (+ start 1) (- span 1))))
        (else
         (search-for-primes (+ start 1) (- span 1)))))

1000에 대해서 3개의 소수 찾기

> (search-for-primes 1000 20)

1001
1003
1005
1007
1009 *** 0
1011
1013 *** 0
1015
1017
1019 *** 0

10000보다 큰 소수 찾기

> (search-for-primes 10000 40)

10001
10003
10005
10007 *** 0
10009 *** 0
10011
10013
10015
10017
10019
10021
10023
10025
10027
10029
10031
10033
10035
10037 *** 0
10039 *** 0

100000 보다 큰 소수 3개 찾기

> (search-for-primes 100000 100)

100003 *** 0
100019 *** 0
100043 *** 0
100049 *** 0
100057 *** 0
100069 *** 0

1000000 보다 큰 소수 3개 찾기

> (search-for-primes 1000000 100)

1000003 *** 0
1000033 *** 0
1000037 *** 0
1000039 *** 0
1000081 *** 0
1000099 *** 0

요즘 컴이 빠른건지 전부 0가 되고 있음.. 단위 키우기로 함.. -ㅇ-

/> (search-for-primes 10000000000 100)

10000000019***125
10000000033***125
10000000061***156
10000000069***125
10000000097***141
/> (search-for-primes 10000000000 100)

10000000019***125
10000000033***141
10000000061***125PLT scheme에는 runtime이 없으므로 runtime을 급조

(define (runtime) (current-milliseconds))

(define (search-for-primes start span)
  (cond ((= span 0) (newline))
        ((odd? start)
         (begin
           (timed-prime-test start)
           (search-for-primes (+ start 1) (- span 1))))
        (else
         (search-for-primes (+ start 1) (- span 1)))))

1000에 대해서 3개의 소수 찾기

> (search-for-primes 1000 20)

1001
1003
1005
1007
1009 *** 0
1011
1013 *** 0
1015
1017
1019 *** 0

10000보다 큰 소수 찾기

> (search-for-primes 10000 40)

10001
10003
10005
10007 *** 0
10009 *** 0
10011
10013
10015
10017
10019
10021
10023
10025
10027
10029
10031
10033
10035
10037 *** 0
10039 *** 0

100000 보다 큰 소수 3개 찾기

> (search-for-primes 100000 100)

100003 *** 0
100019 *** 0
100043 *** 0
100049 *** 0
100057 *** 0
100069 *** 0

1000000 보다 큰 소수 3개 찾기

> (search-for-primes 1000000 100)

1000003 *** 0
1000033 *** 0
1000037 *** 0
1000039 *** 0
1000081 *** 0
1000099 *** 0

요즘 컴이 빠른건지 전부 0가 되고 있음.. 단위 키우기로 함.. -ㅇ-

/> (search-for-primes 10000000000 100)

10000000019***125
10000000033***125
10000000061***156
10000000069***125
10000000097***141
/> (search-for-primes 10000000000 100)

10000000019***125
10000000033***141
10000000061***125
10000000069***156
10000000097***125

/> (search-for-primes 100000000000 100)

100000000003***453
100000000019***453
100000000057***453
100000000063***468
100000000069***422
100000000073***469
100000000091***453
/> (search-for-primes 1000000000000 100)

1000000000039***1469
1000000000061***1422
1000000000063***1438
1000000000091***1438
/>

이 나옴..

자리수가 한자리 증가할때마다 대략 3~3.5배 사이로 증가함을 알 수 있다.
10000000069***156
10000000097***125

/> (search-for-primes 100000000000 100)

100000000003***453
100000000019***453
100000000057***453
100000000063***468
100000000069***422
100000000073***469
100000000091***453
/> (search-for-primes 1000000000000 100)

1000000000039***1469
1000000000061***1422
1000000000063***1438
1000000000091***1438
/>

이 나옴..

자리수가 한자리 증가할때마다 대략 3~3.5배 사이로 증가함을 알 수 있다.

연습문제 1.20

인자먼저 계산법으로 해당하는 문제를 풀어보자..

이 경우 인자가 먼저 나와야하므로

(gcd 206 40) -> (if (= 40 0 ) 206 (gcd 40 (remainder 206 40))) -> (gcd 40 6) ; 한번
(gcd 40 6) -> (if (= 6 0 ) 40 (gcd 6 (remainder 40 6))) -> (gcd 6 4) ; 두번
(gcd 6 4) -> (if (= 4 0 ) 6 (gcd  4 (remainder 6 4))) -> (gcd 6 4) ; 세번
(gcd 4 2) -> (if (= 2 0 ) 4 (gcd 2 (remainder 4 2))) -> (gcd 6 4) ; 네번
(gcd 2 0) -> (if (= 0 0 ) 2 (gcd 0 (remainder 2 0))) -> 2

총 4번에 걸쳐 remainder가 호출된다. (가장 마지막의 remainder는 호출되지 않는다)

정의대로 계산법은..
이전에서 if의 계산은 정의대로나 인자먼저나 모두 같다고 했으므로...

Step1:

(gcd 206 40)
=
(if (= 40 0 ) 206 (gcd 40 (remainder 206 40)))
=
(gcd 40 (remainder 206 40))

Step2:

(gcd 40 (remainder 206 40))
=
(if (= 0 (remainder 206 40)) ; (= 0 6) 한번
    40
    (gcd (remainder 206 40)
            (remainder 40 (remainder 206 40))))
= (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))

Step 3:

(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
=
(if (= 0 (remainder 40 (remainder 206 40))) ; (= 0 4) 두번
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
            (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
= (gcd (remainder 40 (remainder 206 40))
        (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))

Step 4:

(gcd (remainder 40 (remainder 206 40))
        (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
=
(if (= 0 (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) ; (= 0 2) 네번
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))
=
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))

                    
Step 5:

(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))
=
(if (= 0 (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))) ; (= 0 0) 일곱번
    (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
    (gcd (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
         (remainder (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
                    (remainder (remainder 40 (remainder 206 40))
                               (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))))
=
(remainder (remainder 206 40) (remainder 40 (remainder 206 40))) = 2 ; 네번

remainder의 총 누적 갯수는 1 + 2 + 4 + 7 + 4 = 18번

연습문제 1.19

Tpq^2를 구해보자..

a <- bq + aq + ap 이고 b <- bp + aq 이므로

(bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
= bpq + aqq + bqq + aqq + apq + bpq + apq + app
= (2pq + qq)b + (2pq + qq)a + (pp + qq)a

(bp + aq)p + (bq + aq + ap)q
= bpp + apq + bqq + aqq + apq
= (pp + qq)b + (2pq + qq)a

가 된다.

따라서 p' = pp + qq이고 q' = 2pq + qq가 된다.

정의한 빈곳을 모두 채우면

(define (fib n)
  (fib-iter 1 0 0 1 n ))

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

연습문제 1.18

a*b를 구할때
b가 짝수인 경우는 2*a와 b/2 를 곱으로 치환한다.
b가 홀수인 경우 a+a*(b-1)을 구하면 된다.

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

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

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

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