이 문제는 피보나치 수를 구하는데 얼마나 많은 덧셈을 하는지 확인하는 문제입니다.

위와 같은 방법으로 피보나치 수를 구합니다.

따라서 n번재 피보나치 수열을 구하려면 n-1번의 덧셈이 필요합니다.

살펴보니 10번째 값을 구할 때 add_execute가 9번 나왔습니다.

즉, 제 예상이 맞는 듯싶습니다.^^

재미있는 것은 10번째 값을 구할 때 0부터 9까지 모두 구합니다.

따라서 그 다음으로 20번째 값을 구할 때 10번만 덧셈합니다.

즉, 11번부터 20까지 덧셈을 행하는 것입니다.

그럼 이렇게 값을 저장하는 것이 아닌 방법이라면 어떻게 되는지 생각해보았습니다.

피보나치 수는 위와 같은 나무꼴(tree)를 그립니다.

이는 Full binary tree와 비슷합니다.

그리고 fibs(n)은 n-1 height를 가집니다.

따라서 2^(n-1)개의 terminal vertex를 가지고, 총 vertex의 개수는 (2^n) - 1입니다.

그렇기에 덧셈의 수가 지수 비례로 늘어납니다.

여전히 코드를 보고 수행 시간을 판단하는 것은 어렵습니다.

2학기 때 자료구조를 듣는데 걱정되네요.ㅜㅜ

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 432

; stream
(define true (= 0 0))
(define false (= 1 0))

(define (cons-stream a b)
  (cons a (delay b)))
(define the-empty-stream '())
(define stream-null? null?)
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

; section 3.5
(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x)
  (newline)
  (display x))

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))

(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

; exercise 3.50
(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
              (cons proc (map stream-cdr argstreams))))))

;;;SECTION 3.5.2
(define (add-streams s1 s2)
  ; print count add call
  (define (add a b)
    (display 'add_execute)
    (newline)
    (+ a b))
  (stream-map add s1 s2))

(define ones (cons-stream 1 ones))
(define integers (cons-stream 1 (add-streams ones integers)))

; exercise 3.54
(define (mul-streams s1 s2)
  (stream-map * s1 s2))

; exercise 3.56
(define (merge s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream s1car (merge (stream-cdr s1) s2)))
                 ((> s1car s2car)
                  (cons-stream s2car (merge s1 (stream-cdr s2))))
                 (else
                  (cons-stream s1car
                               (merge (stream-cdr s1)
                                      (stream-cdr s2)))))))))

; answer
(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))

(define (print-stream-n S n)
  (define (iter i)
    (if (= i n)
        'done
        (begin (display (stream-ref S i))
               (display "  ")
               (if (= (remainder (+ i 1) 10) 0)
                   (newline))
               (iter (+ i 1)))))
  (iter 0))

;(print-stream-n fibs 10)
(display (stream-ref fibs 10))
(newline) (newline)
(display (stream-ref fibs 20))

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.