Använda mynt
Belopp hittills
Minsta möjliga

    Mynt (¢)

      Mer om myntväxlingsproblemet

      Myntväxlingsproblemet

      Med några få sorters mynt, hur betalar man ett exakt belopp med så få mynt som möjligt, och på hur många sätt går det över huvud taget? Det giriga svaret, största mynt först, fungerar för riktiga pengar men misslyckas för vissa myntuppsättningar. En tabell som bygger varje belopp av mindre belopp blir alltid rätt. Tryck på ett mynt i brickan för att lägga det på disken, och tryck på ett mynt på disken för att ta tillbaka det. Mätaren fylls upp mot beloppet: få ihop det exakt, med så få mynt som möjligt. Minst antal mynt visar det bästa svaret, och Girig visar vad man får genom att alltid ta det största myntet som får plats, vilket inte alltid blir minst antal. Ändra mynten (i cent) och beloppet i panelen. Vyn Tabell visar hur dynamisk programmering hittar minst antal mynt, eller räknar antalet sätt att få ihop beloppet: tryck på Spela för att se tabellen fyllas, eller på Steg och Bakåt för att gå ett steg i taget, och dra i stegreglaget för att hoppa vart som helst. Varje mynt kan användas hur många gånger som helst. När tabellen är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

      Hur det fungerar

      1. Tryck på mynt i brickan för att göra beloppet exakt och se mätaren fyllas i cent.
      2. Försök använda så få mynt som möjligt och tryck sedan på Minst antal mynt eller Girig för att jämföra.
      3. Öppna vyn Tabell och tryck på Spela för att se varje cell läsa det mindre belopp den beror på.

      Minst antal mynt

      Beloppet 0 kräver inga mynt. För varje större belopp provar man varje mynt som inte är större än beloppet: det som är kvar efter myntet är ett mindre belopp som redan står i tabellen, så ett mynt till ger en kandidat. Den minsta kandidaten hamnar i cellen, och myntet som gav den sparas i raden under. När tabellen är full läses mynten tillbaka från målet: ta dess sista mynt, gå till beloppet som är kvar och upprepa tills du når 0.

      Antal sätt

      För att räkna kombinationer i stället för ordningar lägger tabellen till ett mynt per rad. En cell räknar sätten att få ihop sitt belopp med mynten fram till sin rad: sätten utan det nyaste myntet, alltså cellen ovanför, plus sätten som använder det nyaste myntet minst en gång, alltså cellen lika många kolumner till vänster på samma rad. Eftersom mynten läggs till i en fast ordning är 1 + 2 och 2 + 1 samma sätt och räknas en gång.

      Ofta ställda frågor

      Varför misslyckas den giriga metoden?

      Den giriga algoritmen tar alltid det största myntet som får plats och omprövar aldrig sitt val. Med mynten 1, 3 och 4 och beloppet 6 tar den 4, sedan 1 och 1: tre mynt, när två treor hade räckt. För myntsystem som euron eller den amerikanska dollarn råkar girig vara optimal; sådana system kallas kanoniska.

      Vad är skillnaden mellan att räkna sätt och att räkna ordningar?

      Sätt behandlar 1 + 2 och 2 + 1 som samma kombination; ordningar räknar dem var för sig. Appen räknar sätt genom att lägga till mynten en rad i taget. För att i stället räkna ordningar går man igenom beloppen och provar varje mynt för vart och ett.

      Hur snabb är algoritmen för myntväxlingsproblemet?

      Båda tabellerna kräver antalet myntsorter gånger beloppet i steg. Det går snabbt för belopp i tusental, men ett belopp kan vara ett jättestort tal, så mätt i antalet siffror är problemet i allmänhet NP-svårt.

      Vad händer om ett belopp inte går att få ihop?

      Dess cell stannar på ∞, till exempel beloppen 1 och 3 med mynten 2 och 5. I läget Antal sätt är antalet helt enkelt 0.

      Skickas något någonstans?

      Nej. Allt räknas ut i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

      Redo att prova det?

      Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

      Gå till Editor