SICP faire des changements

Question

; Je suis un amateur qui essaie de travailler par SICP ( c'est gratuit! ) et il y a une procédure d'exemple dans le premier chapitre qui est destiné à compter les moyens possibles pour faire changer avec des pièces américaines; (Changement fabricant 100) => 292. Il est mis en œuvre quelque chose comme:

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

Quoi qu'il en soit; c'est une procédure récursive arbre, et l'auteur « laisse comme un défi » trouver une méthode itérative pour résoudre le même problème (espace fixe par exemple). Je n'ai pas eu la chance ou essayant de se faire trouver une réponse après avoir été frustré. Je me demande si c'est un fart de cerveau de ma part, ou si vissage avec moi l'auteur.

Answer 1

en général, plus simple / moyen le plus général d'éliminer récursion, est d'utiliser une pile auxiliaire - au lieu de faire les appels récursifs, vous poussez leurs arguments dans la pile, et itérer. Lorsque vous avez besoin du résultat de l'appel récursif afin de procéder, encore une fois dans le cas général, c'est un peu plus compliqué parce que vous allez aussi devoir être capable de pousser une « demande de continuation » (qui se détache l'auxiliaire pile lorsque les résultats soient connus); Cependant, dans ce cas, puisque tout ce que vous faites avec tous les résultats d'appels récursifs est une sommation, il suffit de garder un accumulateur et, chaque fois que vous obtenez un résultat numérique au lieu d'un besoin de faire plus appel, l'ajouter à la accumulateur.

Cependant, cela, en soi, est pas espace fixe, puisque cette pile va croître. Donc, une autre idée utile est: puisque c'est une fonction pure (sans effets secondaires), chaque fois que vous vous trouvez avoir calculé la valeur de la fonction d'un certain ensemble d'arguments, vous pouvez memoize la correspondance des arguments-résultat. Cela permettra de limiter le nombre d'appels. Une autre approche conceptuelle qui conduit à peu près les mêmes calculs est programmation dynamique [[aka DP]], bien que avec DP vous travaillez souvent bottom-up « préparer les résultats à memoized », pour ainsi dire, plutôt que de commencer par une récursion et de travailler pour l'éliminer.

Prenez bas vers le haut DP sur cette fonction, par exemple. Vous savez que vous allez finir à plusieurs reprises avec « combien de façons de faire changer pour le montant X avec juste la plus petite pièce de monnaie » (comme vous les choses rogner à X avec différentes combinaisons de pièces de la amount d'origine), de sorte que vous commencez à calculer ces valeurs amount avec une simple itération (f (X) = X / value si X est divisible par la value plus petite valeur-pièce, sinon 0, ici, value est 1, alors f (X) = X pour tout X> 0). Maintenant, vous continuez en calculant une nouvelle fonction g (X), des façons de faire le changement pour X avec deux plus petites pièces: à nouveau une itération simple pour augmenter X, avec g (x) = f (X) + g (X - value) pour la value de la deuxième plus petite pièce (ce sera une itération simple, car le temps que vous êtes calcul g (X) que vous avez déjà calculé et stocké f (X) et tous g (Y) Y trois les plus petites pièces de monnaie - h (X) = g (X) + g (X-value) comme ci-dessus - et de maintenant vous n'aurez pas f (X) plus, de sorte que vous pouvez réutiliser que espace. En tout, cela aurait besoin d'espace 2 * amount - pas « espace fixe » encore, mais se rapprocher ...

Pour faire le saut final à « l'espace fixe », demandez-vous: avez-vous besoin de garder autour de tous valeurs de deux tableaux à chaque étape (celui que vous avez calculé dernier et celui que vous êtes actuellement calcul), ou seulement certains de ces valeurs, en réorganisant votre boucle un peu ...?

Answer 2

La solution que je suis venu avec est de garder le nombre de chaque type de pièce que vous utilisez dans une « bourse »

La boucle principale fonctionne comme celui-ci; « Denom est la dénomination actuelle, » changé est la valeur totale des pièces de monnaie dans la bourse, « donné est la quantité de changement que je dois faire et » élucidation à prend toutes les pièces plus petites qu'une dénomination donnée sur la bourse .

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

Après avoir lu la réponse d'Alex Martelli je suis venu avec l'idée de la bourse, mais juste eu le temps de le faire fonctionner

Answer 3

est ma version de la fonction, en utilisant la programmation dynamique . Un vecteur de taille n + 1 est initialisé à 0, à l'exception que l'article est d'abord 0'th 1. Ensuite, pour chaque pièce de monnaie possible (la boucle do externe), chaque élément de vecteur (la boucle do intérieure) à partir de la kème , où k est la valeur de la pièce, est incrémenté de la valeur à la k indice courant négatif.

(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

Vous pouvez exécuter ce programme http://ideone.com/EiOVY .

Answer 4

Ainsi, ce fil , le demandeur d'origine de la question arrive avec une réponse sonore via la modularisation. Je suggère cependant que son code peut facilement être optimisé si vous remarquez que cc-pennies est tout à fait superflu (et par extension, est donc cc-nothing)

Voir, le problème avec la cc-pennies façon est écrit que, parce qu'il n'y a pas de dénomination plus bas pour aller, tout ce qu'il fera en imitant la structure des procédures de dénomination plus élevée est itérer vers le bas de (- amount 1) à 0, et il le fera chaque fois que vous le transmettre une quantité de la procédure de cc-nickels. Ainsi, au premier passage, si vous essayez 1 dollar, vous obtiendrez un amount de 100, donc (- amount 1) évalue à 99, ce qui signifie que vous subissez 99 cycles superflus du cycle de cc-pennies et cc-nothing. Ensuite, cinq cents vous passer 95 comme montant, vous obtenez 94 cycles plus gaspillées, ainsi de suite et ainsi de suite. Et c'est tout avant de vous déplacer même l'arbre à dix cents, ou quarts ou demi-dollars.

Au moment où vous arrivez à cc-pennies, vous savez déjà que vous voulez juste l'accumulateur par un, alors je vous suggère cette amélioration:

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

Espoir vous avez trouvé cela utile.

Answer 5

Vous pouvez résoudre de manière itérative avec une programmation dynamique en temps pseudo-polynomiale.