NoSyu의 주저리주저리 :: SICP Exercise 연습문제 3.66

이 문제는 (pair integers integers)가 어떻게 배열되는지 알아보는 문제입니다.

아쉽게도 아직 스트림에 대한 이해가 올바르지 못해 DrScheme로 상황을 확인한 후

연습장에 하나씩 그려가며 수식을 얻어낼 수 있었습니다.

그렇게 수식을 구한 후 그 수식이 맞는지 확인하기위해

(99, 100)과 (100, 100)을 출력하고자 해당 번호를 집어넣었습니다.

(99, 100)의 앞에는 950737950171172051122527404030개의 쌍이 있고,

(100, 100)의 앞에는 1267650600228229401496703205374개의 쌍이 있습니다.

(어떻게 읽는지도 모르겠군요.;;;)

저 번호를 넣은 후 프로그램을 돌리니 이런 메시지가 나왔습니다.

보시다시피 에러가 났습니다.

혹시 메모리가 모자라서 그런가 싶어 128MB에서 1024MB로 늘렸지만 마찬가지였습니다.

아마도 숫자가 너무 커서 1GB는 한계가 있는 듯싶습니다.

따라서 이보다 작은 수인 (9, 10)과 (10, 10)을 수식에서 답을 유도하여 해보았습니다.

(9, 10)은 766, (10, 10)은 1022개의 쌍이 앞에 있습니다.

제대로 나오는군요.^^

그리고 (1, 100)의 앞에는 총 197개의 쌍이 있습니다.

그럼 수식을 얘기하겠습니다.

수식은 다음과 같습니다.

이보다 간단히 하려고 하였으나 잘 되지 않았습니다.OTL...

저 수식이 나온 이유는 다음과 같습니다.

1. 각 줄은 어떤 수열을 가지고 있다.

이 수열은 초항이 2이고 공비가 2인 등비수열이다.

2. (i, i)에서 (i, i+1)로 가는 사이에 i-1번째 줄에서의 수열을 더해야 한다.

3. (i, i+1)에서 (i+1, i+1)로 가는 사이에 i-1번째 줄에서의 수열을 더해야 한다.

4. (i, j)에서 (i, j+1)로 가는 사이에 i-1번째 줄에서의 수열을 두 번 더한 후 1을 더한다.

왜냐하면 그 사이에 i+1번째 줄에 있는 쌍을 출력하기 때문이다.

즉, (i, j) -> (i-1번째 줄에서의 수열) -> (i+1, k) -> (i-1번째 줄에서의 수열) -> (i, j+1)

위와 같은 성질을 발견하였기에 저 성질을 바탕으로 만든 수식입니다.

그래서 위에서 말한 엄청난 수가 나오는 것입니다.

2의 100제곱이라... 엄청나지 않습니까?^^;;

참조

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

; 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)
(stream-map + 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.55
(define (partial-sums S)
(cons-stream (stream-car S) (add-streams (stream-cdr S)
(partial-sums S))))

; 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)))))))))

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

; exercise 3.59
(define (div-streams s1 s2)
(stream-map / s1 s2))

(define (integrate-series coff_stm)
(let ((integrate_s (cons-stream 1 ; 상수 c
(div-streams coff_stm integers))))
(stream-cdr integrate_s)))

(define exp-series
(cons-stream 1 (integrate-series exp-series)))
(define cosine-series
(cons-stream 1
(integrate-series (scale-stream sine-series -1))))
(define sine-series
(cons-stream 0
(integrate-series cosine-series)))

; exercise 3.60
(define (mul-series s1 s2)
(cons-stream (* (stream-car s1) (stream-car s2))
               (add-streams (mul-series (stream-cdr s1) s2)
                            (scale-stream (stream-cdr s2) (stream-car s1)))))
; exercise 3.61
(define (invert-unit-series S)
(define X
    (cons-stream 1
                 (scale-stream (mul-series (stream-cdr S) X) -1)))
X)

; exercise 3.62
; s1 / s2
(define (div-series s1 s2)
(if (= 0 (stream-car s2))
(error "Divide by zero" s2)
(mul-series s1 (invert-unit-series s2))))

; exercise 3.63
(define (sqrt-improve guess x)
(average guess (/ x guess)))

(define (average x y)
(/ (+ x y) 2))

(define (sqrt-stream x)
(define guesses
    (cons-stream 1.0
                 (stream-map (lambda (guess)
                               (sqrt-improve guess x))
                             guesses)))
guesses)

; exercise 3.64
(define (stream-limit stm tolerance)
(let ((element1 (stream-car stm)) ; 앞의 원소
        (element2 (stream-car (stream-cdr stm)))) ; 뒤의 원소
    (if (< (abs (- element1 element2)) tolerance)
        element2
        (stream-limit (stream-cdr stm) tolerance))))
(define (sqrt x tolerance)
(stream-limit (sqrt-stream x) tolerance))

; exercise 3.65
(define ln2-stream
(partial-sums (ln2-summands 1)))
(define (ln2-summands n)
(cons-stream (/ 1.0 n)
(stream-map - (ln2-summands (+ n 1)))))

(define (euler-transform s)
(let ((s0 (stream-ref s 0))           ; Sn-1
        (s1 (stream-ref s 1))           ; Sn
        (s2 (stream-ref s 2)))          ; Sn+1
    (cons-stream (- s2 (/ (square (- s2 s1))
                          (+ s0 (* -2 s1) s2)))
                 (euler-transform (stream-cdr s)))))

(define (make-tableau transform s)
(cons-stream s
(make-tableau transform
(transform s))))

(define (accelerated-sequence transform s)
(stream-map stream-car
(make-tableau transform s)))

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

; section 3.5.3
(define (interleave s1 s2)
(if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (interleave s2 (stream-cdr s1)))))

(define (pairs s t)
(cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) (list (stream-car s) x))
                (stream-cdr t))
    (pairs (stream-cdr s) (stream-cdr t)))))

; exercise 3.66
(define a (pairs integers integers))

; exercise 1.16
(define (i-fast-expt b n)
(fast-expt-iter 1 b n))

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

(define (even? n)
(= (remainder n 2) 0))
; execute
(print-stream-n a 100) ; (1, 1) ~ (1, 51)
(newline)
(display (stream-ref a 101)) ; (1, 52)
(newline) (newline)
(display (- (* (i-fast-expt 2 0) (+ (* 2 (- 100 1)) 1)) 2)) ; (1, 100)
(newline)
(display (stream-ref a (- (* (i-fast-expt 2 1) (- 100 1 -1)) 3))) ; (1, 100)
(newline) (newline)
(display (- (* (i-fast-expt 2 98) (+ (* 2 (- 100 99)) 1)) 2)) ; (99, 100)
;(newline)
;(display (stream-ref a (- (* (i-fast-expt 2 98) (+ (* 2 (- 100 99)) 1)) 2))) ; (99, 100)
(newline) (newline)
(display (- (i-fast-expt 2 100) 2)) ; (100, 100)
;(newline)
;(display (stream-ref a (- (i-fast-expt 2 100) 2))) ; (100, 100)

(newline) (newline)
(display (- (* (i-fast-expt 2 8) (+ (* 2 (- 10 9)) 1)) 2)) ; (9, 10)
(newline)
(display (stream-ref a (- (* (i-fast-expt 2 8) (+ (* 2 (- 10 9)) 1)) 2))) ; (99, 100)
(newline) (newline)
(display (- (i-fast-expt 2 10) 2)) ; (10, 10)
(newline)
(display (stream-ref a (- (i-fast-expt 2 10) 2))) ; (20, 20)

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