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

이 문제는 1.2.2절에서 배웠던 동전 바꾸기 프로그램을

US 동전와 UK 동전으로 바꿀 때 리스트를 이용하여 쓰는 문제입니다.

먼저 cc 프로시저를 리스트에 맞게 변형시켰고,

여기서 새롭게 나오는 first-denomination, except-first-denomination,

no-more? 프로시저를 정의하는 문제입니다.

그리고 coin-values 리스트 원소의 차례는 cc 프로시저에 영향을 주는지 살펴야합니다.

이와 관련된 연습문제로 1.14가 있습니다.

먼저 cc 프로시저를 소개하겠습니다.

이 프로시저는 리스트를 인자로 받아 처리하기에 1.2.2절의 것과 차이가 납니다.

여기에 맞춰 새롭게 나타난 프로시저를 정의하여 실행시켰습니다.

각각의 프로시저는 너무 쉽게 답이 나왔습니다.^^

1.2.2절의 프로시저를 보시면 각각의 자리에 어떤 내용이 들어가야하는지 알 수있습니다.

그 다음으로 리스트 원소의 순서를 바꿨을 때의 얘기입니다.

오름차순이냐 내림차순이냐에 따라 결과는 같지만, 속도 차이가 3~4배 정도 차이납니다.

혹시 뒤에 적어 이런 일이 발생하지 않았나 싶어

순서를 바꾼 것을 먼저 실행하게 하였습니다.

하지만 결과는 비슷하였습니다.

즉, 리스트 원소의 차례가 cc 프로시저 결과에는 영향이 없지만,

그 속도는 엄청난 영향을 줍니다.

이 이유로 이렇게 생각합니다.

cc 프로시저를 보면 마치는 경우가 amount가 0 이하입니다.

따라서 amount가 많을수록 처리량이 많아지는데,

amount를 깎는 방법으로 coin-values의 첫 번째 원소만큼 빼고 있습니다.

('(cc (- amount (first-denomination coin-values)) coin-values)' 부분)

원 리스트의 첫 원소보다 수정(reverse)한 리스트의 첫 원소가 작기에

amount 프로시저를 부르는 횟수 역시 늘어나서 이런 일이 발생하는 듯싶습니다.

전에 cc 프로시저를 접했을 때 무엇인가 부족한 느낌이 들었는데,

후에 리스트와 연관해서 다시 사용하는군요.

앞에서 고생한 덕분에 이번 문제는 쉽게 풀렸습니다.^^

참조

Structure and Interpretation of Computer Programs 2/E - Page 134

; Reverse - exercise 2.18
(define (reverse items)
(if (null? (cdr items))
      items
      (append (reverse (cdr items)) (list (car items)))))
(define (append list1 list2)
(if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

; Counting change
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(define (count-change amount)
(cc amount 5))

(define (cc amount coin-values)
(cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else (+ (cc amount
                     (except-first-denomination coin-values))
                 (cc (- amount
                        (first-denomination coin-values))
                     coin-values)))))

; answer
(define (first-denomination coin-values)
(car coin-values))

(define (except-first-denomination coin-values)
(cdr coin-values))

(define (no-more? coin-values)
(null? coin-values))

; execute
(define (execute-cc amount coin-values start-second)
   (display "amount : ")
   (display amount)
   (display " coin-values : ")
   (display coin-values)
   (newline)
   (display "answer : ")
   (display (cc amount coin-values))
   (display " milliseconds : ")
   (display (- (current-milliseconds) start-second))
   (newline))

(execute-cc 100 (reverse us-coins) (current-milliseconds))
(execute-cc 100 (reverse uk-coins) (current-milliseconds))
(newline)
(execute-cc 100 us-coins (current-milliseconds))
(execute-cc 100 uk-coins (current-milliseconds))

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