이 문제는 2, 3, 5 외의 소수 인수를 가지지 않는 양의 정수를 찾는 문제입니다.

리차드 해밍(Richard Hamming)이 낸 유명한 문제라고 합니다.

해밍이라는 단어는 해밍 코드(Hamming code),

해밍 거리(Hamming distance) 등에서 자주 들은터라

혹시나 하는 생각에 살펴보니 관련있는 사람이군요.^^

그보다 20세기 수학자라니... 해당 개념이 20세기에 나왔군요.;;;;

살펴보니 맨하탄 프로젝트(Manhattan Project)에도 관여하였군요.;;;;

거기에 재미있는 말도 많습니다만...

일단 여기는 문제를 푸는 곳이니 다른 글에 적겠습니다.^^

여하튼 위와 같은 정수의 성질로

1. 1부터 시작한다.

2. 해당 스트림에 2를 곱한 스트림의 원소도 포함한다.

3. 해당 스트림에 3를 곱한 스트림의 원소도 포함한다.

4. 해당 스트림에 5를 곱한 스트림의 원소도 포함한다.

5. 이것이 전부다.

라고 합니다.

그리고 스트림을 정렬하는 merge 프로시저를 만들었습니다.

이제 저 정의에 맞는 스트림을 만들어야 합니다.

간단히 잘 나오네요.^^

살펴보니 맞는 듯싶습니다.^^

이렇게 간단하게 숫자를 구할 수 있다니... 정말 재미있네요.^^

참조

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

; 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.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 S (cons-stream 1 (merge (scale-stream S 2)
                                (merge (scale-stream S 3)
                                       (scale-stream S 5)))))

(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 S 30)

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

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