- Wird gefüllt
- Wird gelesen
- Ergebnis
Münzwechselproblem
Wie zahlt man mit ein paar Münzsorten einen genauen Betrag mit möglichst wenigen Münzen, und auf wie viele Arten geht das überhaupt? Die gierige Antwort, größte Münze zuerst, funktioniert bei echtem Geld, scheitert aber bei manchen Münzsätzen. Eine Tabelle, die jeden Betrag aus kleineren aufbaut, liegt immer richtig. Tippen Sie auf eine Münze in der Schale, um sie auf den Tresen zu legen, und tippen Sie auf eine Münze auf dem Tresen, um sie zurückzunehmen. Die Anzeige füllt sich bis zum Betrag: Bilden Sie ihn genau, mit so wenigen Münzen wie möglich. Wenigste Münzen zeigt die beste Lösung, und Greedy zeigt, was herauskommt, wenn man immer die größte passende Münze nimmt – das sind nicht immer die wenigsten. Ändern Sie die Münzen (in Cent) und den Betrag im Bedienfeld. Die Ansicht Tabelle zeigt, wie dynamische Programmierung die wenigsten Münzen findet oder die Möglichkeiten zählt, den Betrag zu bilden: Drücken Sie Abspielen, um zuzusehen, wie sich die Tabelle füllt, oder Schritt und Zurück, um Schritt für Schritt vorzugehen, und ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Jede Münze kann beliebig oft verwendet werden. Wenn die Tabelle ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Tippen Sie auf Münzen in der Schale, um den Betrag genau zu bilden, und sehen Sie, wie sich die Anzeige in Cent füllt.
- Versuchen Sie, so wenige Münzen wie möglich zu verwenden, und drücken Sie dann Wenigste Münzen oder Greedy zum Vergleich.
- Öffnen Sie die Ansicht Tabelle und drücken Sie Abspielen, um zu sehen, wie jede Zelle den kleineren Betrag liest, von dem sie abhängt.
Wenigste Münzen
Betrag 0 braucht keine Münzen. Probieren Sie für jeden größeren Betrag jede Münze, die nicht größer ist als er: Was nach dieser Münze übrig bleibt, ist ein kleinerer Betrag, der schon in der Tabelle steht, also ergibt eine Münze mehr einen Kandidaten. Der kleinste Kandidat kommt in die Zelle, und die Münze, die ihn ergeben hat, wird in der Zeile darunter festgehalten. Wenn die Tabelle voll ist, werden die Münzen vom Zielbetrag aus zurückgelesen: Nehmen Sie seine letzte Münze, gehen Sie zum restlichen Betrag und wiederholen Sie das bis 0.
Anzahl der Möglichkeiten
Um Kombinationen statt Reihenfolgen zu zählen, nimmt die Tabelle pro Zeile eine Münze hinzu. Eine Zelle zählt die Möglichkeiten, ihren Betrag mit den Münzen bis zu ihrer Zeile zu bilden: die Möglichkeiten ohne die neueste Münze, also die Zelle darüber, plus die Möglichkeiten, die die neueste Münze mindestens einmal verwenden, also die Zelle so viele Spalten weiter links in derselben Zeile. Weil die Münzen in fester Reihenfolge hinzukommen, sind 1 + 2 und 2 + 1 dieselbe Möglichkeit und werden nur einmal gezählt.
Häufig gestellte Fragen
Warum scheitert das Greedy-Verfahren?
Greedy nimmt immer die größte passende Münze und überdenkt die Wahl nie. Mit den Münzen 1, 3 und 4 und dem Betrag 6 nimmt es 4, dann 1 und 1: drei Münzen, wo zwei 3er reichen würden. Bei Münzsystemen wie dem Euro oder dem US-Dollar ist Greedy zufällig optimal; solche Systeme heißen kanonisch.
Was ist der Unterschied zwischen dem Zählen von Möglichkeiten und dem Zählen von Reihenfolgen?
Bei Möglichkeiten gelten 1 + 2 und 2 + 1 als dieselbe Kombination; bei Reihenfolgen werden sie getrennt gezählt. Die App zählt Möglichkeiten, indem sie die Münzen Zeile für Zeile hinzunimmt. Um stattdessen Reihenfolgen zu zählen, geht man die Beträge durch und probiert für jeden jede Münze.
Wie schnell ist der Algorithmus für das Münzwechselproblem?
Beide Tabellen brauchen Anzahl der Münzsorten mal Betrag Schritte. Das ist schnell für Beträge im Tausenderbereich, aber ein Betrag kann eine riesige Zahl sein; gemessen an der Anzahl seiner Ziffern ist das Problem daher im Allgemeinen NP-schwer.
Was, wenn sich ein Betrag nicht bilden lässt?
Seine Zelle bleibt bei ∞, zum Beispiel bei den Beträgen 1 und 3 mit den Münzen 2 und 5. Im Modus Anzahl der Möglichkeiten ist sein Wert einfach 0.
Wird irgendetwas übertragen?
Nein. Alles wird in Ihrem Browser berechnet, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor