Brugte mønter
Opnået beløb
Færrest mulige

    Mønter (¢)

      Mere om byttepengeproblemet

      Byttepengeproblemet

      Hvordan betaler man med nogle få slags mønter et præcist beløb med så få mønter som muligt, og på hvor mange måder kan det overhovedet gøres? Det grådige svar, største mønt først, virker for rigtige penge, men fejler for nogle møntsæt. En tabel, der bygger hvert beløb op af mindre beløb, giver altid det rigtige svar. Tryk på en mønt i bakken for at lægge den på disken, og tryk på en mønt på disken for at tage den tilbage. Måleren fyldes op mod beløbet: lav det præcist med så få mønter som muligt. Færrest mønter viser det bedste svar, og Grådig viser, hvad man får ved altid at tage den største mønt, der passer, hvilket ikke altid giver færrest. Ret mønterne (i cent) og beløbet i panelet. Visningen Tabel viser, hvordan dynamisk programmering finder færrest mønter eller tæller antallet af måder at lave beløbet på: tryk på Afspil for at se tabellen blive fyldt, eller på Trin og Tilbage for at gå ét trin ad gangen, og træk i trinskyderen for at springe hvorhen du vil. Hver mønt kan bruges så mange gange, du vil. Når tabellen er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.

      Sådan virker det

      1. Tryk på mønter i bakken for at lave beløbet præcist, og se måleren fyldes op i cent.
      2. Prøv at bruge så få mønter som muligt, og tryk så på Færrest mønter eller Grådig for at sammenligne.
      3. Åbn visningen Tabel, og tryk på Afspil for at se hver celle læse det mindre beløb, den afhænger af.

      Færrest mønter

      Beløbet 0 kræver ingen mønter. For hvert større beløb prøver man hver mønt, der ikke er større end beløbet: det, der er tilbage efter mønten, er et mindre beløb, som allerede står i tabellen, så én mønt mere giver en kandidat. Den mindste kandidat kommer i cellen, og mønten, der gav den, gemmes i rækken nedenunder. Når tabellen er fuld, læses mønterne tilbage fra målet: tag dets sidste mønt, gå til det beløb, der er tilbage, og gentag, indtil du når 0.

      Antal måder

      For at tælle kombinationer i stedet for rækkefølger tilføjer tabellen én mønt pr. række. En celle tæller måderne at lave dens beløb på med mønterne op til dens række: måderne uden den nyeste mønt, som er cellen ovenover, plus måderne, der bruger den nyeste mønt mindst én gang, som er cellen lige så mange kolonner til venstre i samme række. Fordi mønterne tilføjes i en fast rækkefølge, er 1 + 2 og 2 + 1 den samme måde og tælles kun én gang.

      Ofte stillede spørgsmål

      Hvorfor fejler den grådige metode?

      Den grådige algoritme tager altid den største mønt, der passer, og genovervejer aldrig sit valg. Med mønterne 1, 3 og 4 og beløbet 6 tager den 4 og derefter 1 og 1: tre mønter, hvor to 3'ere ville være nok. For møntsystemer som euro eller amerikanske dollar er grådig tilfældigvis optimal; sådanne systemer kaldes kanoniske.

      Hvad er forskellen på at tælle måder og at tælle rækkefølger?

      Måder behandler 1 + 2 og 2 + 1 som samme kombination; rækkefølger tæller dem hver for sig. Appen tæller måder ved at tilføje mønterne én række ad gangen. For i stedet at tælle rækkefølger går man beløbene igennem og prøver hver mønt for hvert beløb.

      Hvor hurtig er algoritmen til byttepengeproblemet?

      Begge tabeller kræver antallet af møntslags gange beløbet i trin. Det er hurtigt for beløb i tusindvis, men et beløb kan være et kæmpe tal, så målt i antallet af cifre er problemet generelt NP-svært.

      Hvad hvis et beløb ikke kan laves?

      Dets celle bliver stående på ∞, for eksempel beløbene 1 og 3 med mønterne 2 og 5. I tilstanden Antal måder er dets antal simpelthen 0.

      Bliver der sendt noget nogen steder hen?

      Nej. Alt beregnes i din browser, og dine seneste indstillinger bliver i denne browsers lokale lager.

      Er du klar til at prøve?

      Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

      Gå til Editor