SICP den Wandel

Question

So; Ich bin ein Bastler, der durch SICP zu arbeiten versucht ( es ist kostenlos! ), und es ist ein Beispiel Verfahren im ersten Kapitel, die die möglichen Wege zählen sollten zu ändern mit amerikanischen Münzen zu machen; (Ändern Macher 100) => 292. Es implementiert etwas wie:

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

Wie auch immer; dies ist eine Baum-rekursive Prozedur, und der Autor „verläßt als Herausforderung“ ein iteratives Verfahren zu finden, das gleiche Problem (dh fester Raum) zu lösen. Ich habe keine Antwort dieses Glück herauszufinden, oder die Suche nach frustriert habe. Ich frage mich, ob es ein Gehirn Furz auf meiner Seite ist, oder wenn der Autor des mit mir zu schrauben.

Answer 1

Die einfachste / allgemeinste Art und Weise Rekursion zu beseitigen, in der Regel ist ein Hilfsstapel zu verwenden - anstatt die rekursive Aufrufe zu machen, Sie schieben ihre Argumente in den Stapel, und iterieren. Wenn Sie das Ergebnis des rekursiven Aufrufs benötigen, um wieder in dem allgemeinen Fall zu gehen, das ist ein bisschen komplizierter, weil Sie auch gehen, um eine „Fortsetzung Anforderung“ zu drücken, um die Lage zu sein (dass die Hilfs abgehen wird stapeln, wenn die Ergebnisse bekannt sind); aber in diesem Fall, da alles, was Sie mit all den rekursiven Aufruf Ergebnissen tun eine Summe ist, dann ist es genug, um einen Akkumulator zu halten, und jedes Mal, wenn statt einer Notwendigkeit, eine Reihe Ergebnis zu erhalten, um mehr Anruf zu tun, fügen sie die Akkumulator.

Dies ist jedoch per se ist nicht fester Raum, da dieser Stapel wird wachsen. Also eine weitere hilfreiche Idee ist: da dies eine reine Funktion (keine Nebenwirkungen), jederzeit Sie selbst finden den Wert der Funktion berechnet zu haben für einen bestimmten Satz von Argumenten, können Sie memoize die Argumente Ergebnis Korrespondenz. Dadurch wird die Anzahl der Anrufe begrenzen. Ein weiterer konzeptioneller Ansatz, der die gleichen Berechnungen zu viel führt, ist dynamische Programmierung [[aka DP]], obwohl mit DP arbeiten Sie oft bottom-up „Ergebnisse der Vorbereitung memoized werden“, so zu sprechen, anstatt mit einer Rekursion und arbeiten Sie es zu beseitigen.

Nehmen Sie von unten nach oben DP zu dieser Funktion, zum Beispiel. Sie wissen, dass Sie immer wieder mit „wie viele Möglichkeiten zu ändern für Menge X nur mit der kleinsten Münze zu machen“ am Ende (wie Sie whittle Dinge nach unten zu X mit verschiedenen Münzkombinationen aus dem ursprünglichen amount), so dass Sie die Berechnung diese Werte amount starten mit einer einfachen Iteration (f (X) = X / value wenn X von der kleinsten Münze Wert value, sonst 0 genau teilbar ist, hier value 1, so f (X) = X für all X> 0). Nun geht es weiter durch eine neue Funktion g Berechnung (X), Wege Änderung für X mit den zwei kleinsten Münzen zu machen: wieder eine einfache Iteration zur Erhöhung X, mit g (x) = f (X) + g (X - value) für die value der zweitkleinste Münze (es wird eine einfache Iteration sein, weil durch die Zeit sind Sie g (X) Berechnen Sie haben bereits berechnet und f (X) gespeichert und alle g (Y) für Y drei kleinsten Münzen zu machen - h (X) = g (X) + g (X-value), wie oben - und von jetzt werden Sie nicht f benötigen (X) nicht mehr, so dass Sie , die wiederverwenden können Raum. Alles in allem würde dieser Raum 2 * amount braucht - nicht „festen Platz“ noch nicht, aber, immer näher ...

Um den endgültigen Sprung zu „festen Platz“ zu machen, fragen Sie sich: Sie braucht um zu halten alle Werte von zwei Arrays bei jedem Schritt (die, die Sie zuletzt berechneten und dem einen du bist zur Zeit der Berechnung) oder nur einige dieser Werte, indem Sie Ihre Schleife ein wenig neu anordnen ...?

Answer 2

Die Lösung kam ich mit ist Zählung jeder Art von Münze zu halten Sie in einem ‚Geldbeutel‘

verwenden

Die Hauptschleife funktioniert wie folgt; ‚Denom ist die aktuelle Bezeichnung,‘ geändert wird, der Gesamtwert der Münzen in den Geldbeutel ‚gegeben ist der Betrag der Änderung muss ich machen und‘ clear-up-to nimmt alle Münzen kleiner als eine gegebene Stückelung aus dem Geldbeutel .

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

Nachdem Alex Martelli Antwort Lesen kam ich mit der Handtasche Idee, bekam aber nur um zu machen es funktionieren

Answer 3

Hier ist meine Version der Funktion mit dynamischer Programmierung . Ein Vektor der Größe n + 1 auf 0 initialisiert wird, außer, dass das 0-ten Elemente anfänglich 1 dann für jede mögliche Münze (das äußerte do-Schleife), wobei jedes Vektorelement (die inneren do-Schleife), ausgehend von dem k-ten , wobei k der Wert der Münze ist, die durch den Wert an der aktuellen Index minus k inkrementiert wird.

(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

Sie können dieses Programm laufen unter http://ideone.com/EiOVY .

Answer 4

Also, in dieses Thema , die ursprünglichen Fragesteller von der Frage kommen mit einer soliden Antwort auf über Modularisierung. Ich würde vorschlagen, Sie jedoch, dass sein Code kann leicht optimiert werden, wenn Sie feststellen, dass cc-pennies völlig überflüssig ist (und durch Erweiterung, so ist cc-nothing)

Sehen Sie, das Problem mit der Art und Weise cc-pennies geschrieben wird, ist, dass, weil es kein niedrigerer Nennwert ist zu gehen, alles was man durch die Nachahmung der Struktur des höheren Nennwert Verfahrens tun wird iterieren unten von (- amount 1) 0, und es wird dies tun, jedes Mal, wenn es passieren eine Menge von dem cc-nickels Verfahren. Also, auf dem ersten Durchgang, wenn Sie 1 Dollar versuchen, erhalten Sie eine amount von 100 erhalten, so (- amount 1) 99 auswertet, was bedeutet, werden Sie 99 überflüssig Zyklen des cc-pennies und cc-nothing Zyklus durchlaufen. Dann Nickels wird übergeben Sie als Menge 95, so dass Sie 94 mehr verschwendete Zyklen erhalten, so weiter und so fort. Und das ist alles, bevor Sie selbst den Baum zu Dimes nach oben, oder Viertel oder Halb Dollar.

Durch die Zeit, die du cc-pennies bekommen, Sie bereits wissen, Sie wollen einfach nur auf den Speicher nach der anderen, so würde ich diese Verbesserung vorschlagen:

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

Hoffe, dass Sie dies nützlich gefunden.

Answer 5

Sie können es iterativ mit dynamischer Programmierung in Pseudopolynomiell lösen.