Gebruikte munten
Gevormd bedrag
Minst mogelijk

    Munten (¢)

      Meer over het wisselgeldprobleem

      Wisselgeldprobleem

      Hoe betaal je met een paar soorten munten een exact bedrag met zo min mogelijk munten, en op hoeveel manieren kan dat eigenlijk? Het gretige antwoord, grootste munt eerst, werkt voor echt geld, maar faalt bij sommige sets munten. Een tabel die elk bedrag uit kleinere opbouwt, heeft het altijd goed. Tik op een munt in het bakje om hem op de toonbank te leggen, en tik op een munt op de toonbank om hem terug te nemen. De meter loopt vol tot het bedrag: maak het precies, met zo weinig mogelijk munten. Minste munten toont het beste antwoord, en Gretig toont wat je krijgt als je steeds de grootste munt neemt die past, en dat zijn niet altijd de minste. Verander de munten (in centen) en het bedrag in het paneel. De weergave Tabel laat zien hoe dynamisch programmeren de minste munten vindt, of het aantal manieren telt om het bedrag te vormen: druk op Afspelen om de tabel te zien vollopen, of op Stap en Terug om stap voor stap te gaan, en sleep de stapschuif om ergens heen te springen. Elke munt mag je zo vaak gebruiken als je wilt. Als de tabel geselecteerd is, gaan de pijltjestoetsen een stap verder, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het eind.

      Hoe het werkt

      1. Tik op munten in het bakje om het bedrag precies te maken en zie de meter vollopen in centen.
      2. Probeer zo min mogelijk munten te gebruiken en druk dan op Minste munten of Gretig om te vergelijken.
      3. Open de weergave Tabel en druk op Afspelen om elke cel het kleinere bedrag te zien lezen waarvan ze afhangt.

      Minste munten

      Bedrag 0 heeft geen munten nodig. Probeer voor elk groter bedrag elke munt die niet groter is dan het bedrag: wat er na die munt overblijft is een kleiner bedrag dat al in de tabel staat, dus één munt meer geeft een kandidaat. De kleinste kandidaat komt in de cel, en de munt die hem opleverde wordt bewaard in de rij eronder. Als de tabel vol is, worden de munten vanaf het doel teruggelezen: neem de laatste munt ervan, ga naar het bedrag dat overblijft en herhaal dat tot 0.

      Aantal manieren

      Om combinaties te tellen in plaats van volgordes, voegt de tabel per rij één munt toe. Een cel telt de manieren om zijn bedrag te vormen met de munten tot en met zijn rij: de manieren zonder de nieuwste munt, dat is de cel erboven, plus de manieren die de nieuwste munt minstens één keer gebruiken, dat is de cel zoveel kolommen naar links in dezelfde rij. Omdat de munten in een vaste volgorde worden toegevoegd, zijn 1 + 2 en 2 + 1 dezelfde manier en worden ze één keer geteld.

      Veelgestelde vragen

      Waarom faalt de gretige methode?

      Een gretig algoritme neemt altijd de grootste munt die past en komt nooit op een keuze terug. Met munten 1, 3 en 4 en een bedrag van 6 neemt het 4, dan 1 en 1: drie munten, terwijl twee munten van 3 genoeg zijn. Voor muntsystemen zoals de euro of de Amerikaanse dollar is gretig toevallig optimaal; zulke systemen heten canoniek.

      Wat is het verschil tussen manieren tellen en volgordes tellen?

      Bij manieren zijn 1 + 2 en 2 + 1 dezelfde combinatie; bij volgordes worden ze apart geteld. De app telt manieren, door de munten rij voor rij toe te voegen. Om in plaats daarvan volgordes te tellen, loop je de bedragen af en probeer je voor elk bedrag elke munt.

      Hoe snel is het algoritme voor het wisselgeldprobleem?

      Beide tabellen kosten het aantal muntsoorten maal het bedrag aan stappen. Dat is snel voor bedragen in de duizenden, maar een bedrag kan een enorm getal zijn, dus gemeten naar het aantal cijfers is het probleem in het algemeen NP-moeilijk.

      En als een bedrag niet gevormd kan worden?

      Dan blijft de cel op ∞, bijvoorbeeld voor de bedragen 1 en 3 met munten 2 en 5. In de modus Aantal manieren is het aantal gewoon 0.

      Wordt er iets verstuurd?

      Nee. Alles wordt in je browser berekend, en je laatste instellingen blijven in de lokale opslag van deze browser.

      Klaar om het te proberen?

      Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

      Ga naar Editor