•  18-09-2019
  •  | 
  •  

문제

그래서; 나는 SICP를 통해 일하려는 애호가입니다.무료입니다!) 그리고 첫 번째 장에서는 미국 동전으로 변화 할 수있는 가능한 방법을 계산하기위한 예제 절차가 있습니다. (Change-Maker 100) => 292. 그것은 다음과 같은 것과 같은 구현되었습니다.

(define (change-maker amount)
  (define (coin-value n)
    (cond ((= n 1) 1)
          ((= n 2) 5)
          ((= n 3) 10)
          ((= n 4) 25)
          ((= n 5) 50)))

  (define (iter amount coin-type)
    (cond ((= amount 0) 1)
          ((or (= coin-type 0) (< amount 0)) 0)
          (else (+ (iter amount
                         (- coin-type 1))
                   (iter (- amount (coin-value coin-type))
                         coin-type)))))

  (iter amount 5))

그래도; 이것은 나무 수수료 절차이며, 저자는 동일한 문제를 해결하기위한 반복적 인 절차를 찾는 "도전으로 잎을 떠난다"(즉, 고정 된 공간). 나는 좌절 한 후 이것을 알아 내거나 대답을 찾는 운이 없었습니다. 나는 그것이 내 뇌 방귀인지 또는 저자가 나와 망쳐 놓고 있는지 궁금합니다.

도움이 되었습니까?

해결책

재귀를 제거하는 가장 간단한 / 가장 일반적인 방법은 일반적으로 보조 스택을 사용하는 것입니다. 재귀를 호출하는 대신 인수를 스택으로 밀고 반복합니다. 다시 진행하기 위해 재귀 콜의 결과가 필요할 때, 일반적인 경우 다시, "연속 요청"(보조에서 나올 것입니다. 결과가 알려져있을 때 스택); 그러나이 경우 모든 재귀 통화 결과로 수행하는 모든 것이 합산이므로 축합기를 유지하는 것으로 충분하며, 더 많은 호출을 수행 할 필요가있는 대신 숫자 결과를 얻을 때마다 추가하십시오. 축합기.

그러나 이것은 그 자체로는입니다 ~ 아니다 고정 된 공간은 스택이 자라기 때문에 고정 된 공간입니다. 따라서 또 다른 유용한 아이디어는 다음과 같습니다. 이것은 순수한 기능 (부작용 없음)이므로 특정 인수 세트에 대한 기능의 값을 계산할 때마다 할 수 있습니다. 메모에 인수-소문 서신. 이것은 통화 수를 제한합니다. 동일한 계산으로 이어지는 또 다른 개념적 접근법은 동적 프로그래밍 [AKA DP]] DP를 사용하면 재귀로 시작하고 제거하기 위해 노력하기보다는 말하자면 "MEMOIZING"을 준비하는 경우가 종종 있습니다.

예를 들어이 기능에서 상향식 DP를 사용하십시오. 당신은 당신이 당신이 "가장 작은 동전만으로 x를 x를 변화시키는 몇 가지 방법"으로 반복적으로 끝나는 것을 알고 있습니다 (원본의 다양한 동전 조합으로 x로 with x로 whittle을 때 amount), 그래서 당신은 그것들을 컴퓨팅하기 시작합니다 amount 간단한 반복이있는 값 (f (x) = X/value 만약에 X 가장 작은 코인 값으로 정확히 나눌 수 있습니다 value, 또 다른 0; 여기, value 모든 x> 0의 경우 1, 그래서 f (x) = x). 이제 새로운 기능 g (x)를 계산하여 둘 가장 작은 동전 : x를 증가시키기위한 간단한 반복, g (x) = f (x) + g (x- value) value 두 번째로 작은 동전 중 (G (x)를 계산할 때 이미 계산하고 저장했기 때문에 간단한 반복이 될 것입니다. f (x) 그리고 y <x의 모든 g (y) - 물론 모든 x <= 0의 경우 g (x) = 0). 그리고 다시 H (x)의 경우 x를 변경하는 방법 삼 가장 작은 동전 -H (x) = g (x) + g (x-value위와 같이 - 그리고 지금부터 당신은 더 이상 f (x)가 필요하지 않으므로 재사용 할 수 있습니다. 저것 우주. 모두, 이것은 공간이 필요할 것입니다 2 * amount - 아직 "고정 된 공간"은 아니지만 점점 가까워지고 있습니다 ...

"고정 된 공간"으로의 마지막 도약을하려면 스스로에게 물어보십시오. 모두 각 단계에서 두 개의 배열 값 (마지막으로 계산 한 것과 현재 계산중인 배열 값) 또는 약간 그 값 중에서, 당신의 루핑을 약간 재배치함으로써 ...?

다른 팁

내가 생각해 낸 해결책은 '지갑'에 사용하는 각 유형의 동전을 유지하는 것입니다.

메인 루프는 이와 같이 작동합니다. '분만은 현재 명칭입니다.'는 지갑에서 동전의 총 값입니다. .

#lang scheme
(define (sub changed denom)
  (cond
   ((> denom largest-denom)
    combinations)

   ((>= changed given)
    (inc-combinations-if (= changed given))

    (clear-up-to denom)
    (jump-duplicates changed denom)) ;checks that clear-up-to had any effect.

   (else
    (add-to-purse denom)
    (sub
     (purse-value)
     0
     ))))

(define (jump-duplicates changed denom)
  (define (iter peek denom)
    (cond
     ((> (+ denom 1) largest-denom)
      combinations)

     ((= peek changed)
      (begin
        (clear-up-to (+ denom 1))
        (iter (purse-value) (+ denom 1))))

      (else
       (sub peek (+ denom 1)))))
  (iter (purse-value) denom))

Alex Martelli의 답변을 읽은 후 나는 지갑 아이디어를 생각해 냈지만 방금 작동하게했습니다.

여기 동적 프로그래밍을 사용하는 내 함수의 내 버전입니다. 크기 N+1의 벡터는 0 '번째 항목이 처음에 1이라는 점을 제외하고 0으로 초기화됩니다. 그런 다음 각 가능한 동전 (외부 DO 루프)에 대해 각각의 벡터 요소 (내부 DO 루프)에 대해 k'th부터 시작합니다. , 여기서 k는 동전의 값이며, 전류 지수 마이너스 k의 값에 의해 증가된다.

(define (counts xs n)
  (let ((cs (make-vector (+ n 1) 0)))
    (vector-set! cs 0 1)
    (do ((xs xs (cdr xs)))
        ((null? xs) (vector-ref cs n))
      (do ((x (car xs) (+ x 1))) ((< n x))
        (vector-set! cs x (+ (vector-ref cs x)
          (vector-ref cs (- x (car xs)))))))))

> (counts '(1 5 10 25 50) 100)
292

이 프로그램을 실행할 수 있습니다 http://ideone.com/eiovy.

그래서 이 스레드,이 질문의 원래 질문자는 모듈화를 통한 건전한 답변을 제시합니다. 그러나 나는 당신이 눈에 띄면 그의 코드를 쉽게 최적화 할 수 있다고 제안합니다. cc-pennies 전적으로 불필요합니다 (그리고 확장별로 cc-nothing)

그 방법에 대한 문제를 참조하십시오 cc-pennies 갈 교파가 낮기 때문에, 더 높은 명칭 절차의 구조를 모방함으로써 할 수있는 모든 것이 반복되는 것입니다. (- amount 1) 에게 0, 그리고 그것은 당신이 그것을 통과 할 때마다 이것을 cc-nickels 절차. 따라서 첫 번째 패스에서 1 달러를 시도하면 amount 100의 (- amount 1) 평가합니다 99, 당신은 99 개의 불필요한주기를 겪을 것임을 의미합니다. cc-pennies 그리고 cc-nothing 주기. 그러면 니켈이 당신을 통과 할 것입니다 95 금액으로, 당신은 94 번 더 낭비되는주기를 얻습니다. 그리고 그것은 당신이 나무를 올라 가기 전에 다임, 쿼터 또는 반 달러로 이동하기 전에 모든 것입니다.

당신이 도착할 때까지 cc-pennies, 당신은 이미 당신이 축합기를 하나씩 올리려고한다는 것을 알고 있으므로, 나는 이것을 제안 할 것입니다.

(define (count-change-iter amount)
    (cc-fifties amount 0))

(define (cc-fifties amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-fifties (- amount 50)
                (cc-quarters amount acc)))))

(define (cc-quarters amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-quarters (- amount 25)
                (cc-dimes amount acc)))))

(define (cc-dimes amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-dimes (- amount 10)
                (cc-nickels amount acc)))))

(define (cc-nickels amount acc)
    (cond ((= amount 0) (+ 1 acc))
        ((< amount 0) acc)
        (else (cc-nickels (- amount 5)
                (cc-pennies amount acc)))))

(define (cc-pennies amount acc)
    (+ acc 1))

이것이 유용하다는 것을 알았기를 바랍니다.

유사성 시간에 동적 프로그래밍으로 반복적으로 해결할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top