Mündivahetus: ahne ja optimaalne lahendus

Sisesta müntide nimiväärtused ja soovitud summa. Leht koostab selle summa kahel viisil: ahne algoritm võtab igal sammul suurima sobiva mündi, kuni jääk on null või ükski münt enam ei sobi; vähim võimalik müntide arv leitakse aga tabeli täitmisega alates 0-st kuni soovitud summani. Tabeli all kuvatakse kõik summad kuni sinu valitud piirini ning tähistatakse need, mille korral ahne algoritm kasutab vajalikust rohkem münte.

Näidisarvutus — Mündivahetus: ahne ja optimaalne lahendus

Ahne meetod, suurim münt esimesena	3 münti
Vähim müntide arv tabeli järgi	2 münti: 2×24
Ahne meetodi liigsed mündid	1
Summad 1-st kuni 240-ni, kus ahne meetod kaotab	42 / 240
Suurim liigsete müntide arv summadel 1 kuni 240	1
Kozeni–Zaksi piir: kahe suurima mündi summa	54
Väikseim summa, kus ahne meetod kaotab	48

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Mündivahetus: ahne ja optimaalne lahendus

Mündivahetusülesandes tuleb etteantud nimiväärtustega müntidest, mida igaüht on piiramatult, leida summa moodustamiseks vähim müntide arv. Ahne algoritm võtab suurima sobiva mündi ja kordab sama sammu. Dünaamiline programmeerimine lahendab ülesande täpselt, leides kõigepealt kõigi väiksemate summade lahendid: M(0) = 0 ja M(a) = 1 + min M(a − c) üle kõigi müntide c ≤ a. Mündisüsteemi, milles ahne meetod on iga summa korral optimaalne, nimetatakse kanooniliseks.

Mida iga sümbol tähendab

M(a): vähim müntide arv, millega saab moodustada summa a; arv tabeli lahtris a
G(a): müntide arv, mida ahne meetod summa a jaoks kasutab
cₘ, cₘ₋₁: suurim ja suuruselt teine münt; kui ahne meetod üldse kaotab, on esimene kaotusega summa nende summast väiksem

Eeldab: Iga münti on piiramatult, nimiväärtused on täisarvud ning ainus kulu on müntide arv. Kui kassas on floriinid otsas, on tegu teise ülesandega. Piiri kasutamiseks peab müntide seas olema 1. Ilma selleta ei saa mõnda summat üldse maksta ning ahne meetod võib takerduda enne summat, mille tabel suudab tasuda.

Vanas Briti rahas eksib ahne meetod nelja šillingi puhul 🖖

Vajuta Briti raha enne 1971. 48d ehk nelja šillingi maksmisel võtab ahne meetod esmalt suurima sobiva mündi: poolkrooni (30d), seejärel šillingi (12d) ja kuuepennise (6d), kokku kolm münti. Kaks 24d floriini annavad sama 48d kahe mündiga. Edasi kaotab ahne meetod igast kolmekümnest pennist kuuel summal: 48–53d, 78–83d ja nii edasi kuni 228–233d. See teeb 42 summat 240-st ehk ühest naelast. Iga kaotus on täpselt ühe mündi suurune, seepärast on kõik punased tulbad ribal ühe kõrgused. Need kuus summat jätavad ühe või mitme poolkrooni järel tasuda 18 kuni 23 penni. Kui üks poolkroon tagasi anda ja tasuda 48d kahe floriiniga, kulub münt vähem. Poolpenn ei paranda olukorda. Sisesta mündid poolpennides: 1, 2, 6, 12, 24, 48, 60. Kontrolli summasid kuni 480-ni. Esimene kaotus tuleb 96 poolpenni juures, mis on endiselt 48d. Ahne meetod kaotab 480 summast 84 puhul: needsamad 42 summat ja igaühele järgnev poolpennine summa.

Poolkroonita ei eksi ahne meetod kunagi 🖖

Vajuta Ilma poolkroonita. Samad mündid, kuid ühe võrra vähem: 1, 3, 6, 12 ja 24 penni. Riba jääb tühjaks, sest ahne meetod ei kaota ühelgi 240 summast. Iga mündi väärtus jagab järgmise mündi väärtust. Sellises ahelas ei saa ahne meetod kaotada, sest järgmise mündi väärtuse jagu väiksemaid münte saab alati selle ühe mündi vastu vahetada. Poolkroon lõhub ahela. Kolmkümmend ei ole kahekümne nelja kordne ning kaks floriini võrduvad poolkrooni ja veel 18d-ga, mille tasumiseks on vaja šillingit ja kuuepennist. Kõik esimese riba kaotused tulenevad sellest vahetusest. Ka uue mündi lisamine ei lahenda probleemi. Krooni ehk viie šillingi lisamiseks sisesta 1, 3, 6, 12, 24, 30, 60. Kaotuste arv väheneb 42-lt 24-le, kuid esimene kaotus on endiselt 48d, sest kroonist pole abi ühegi endast väiksema summa puhul.

Mündisüsteemi saab kontrollida lõpliku arvu sammudega 🖖

Ahne meetodi kaotus summal 48d ei ütle veel midagi summa 4 800d kohta. Kõigi summade küsimuse lahendab Dexter Kozeni ja Shmuel Zaksi 1994. aastal avaldatud teoreem. Kui müntide seas on 1 ja ahne meetod üldse kaotab, jääb väikseim kaotusega summa rangelt väärtuste c₃ + 1 ja c_m + c_m−1 vahele. Siin on c₃ suuruselt kolmas münt ning c_m ja c_m−1 kaks suurimat. Vajuta USA sendid. Kaks suurimat münti on 100 ja 50 ning alla 150 pole ühtki kaotust. Sellest lõplikust kontrollist piisab kõigi võimalike summade jaoks; euro puhul ulatub kontroll 300-ni. Piiri ei saa vähendada. Vajuta 1, 3, 4: 5 ja 7 vahel on ainult üks summa, 6, ning just 6 puhul ahne meetod kaotab. Katkendjoon ribal tähistab piiri. Kui müntide seas on 1, jääb esimene punane tulp alati sellest vasakule.

Ülesanne täielikult lahendatud

Milline kolmas münt sobib 1 ja 5 kõrvale? 3 sammu
Riigis on käibel mündid väärtusega 1 ja 5 ning kolmanda mündi d väärtus soovitakse valida vahemikust 6 kuni 30. Milliste d väärtuste puhul annab ahne meetod alati optimaalse vahetusraha? Leht kontrollib korraga üht süsteemi, kuid Kozeni ja Zaksi kolme mündi reegel lahendab kõik 25 juhtu korraga. Vajuta 1, 3, 4, et proovida reeglit esmalt süsteemil, mida leht on juba kontrollinud.

Ava see ülesanne tööriistas
1. Müntide 1 < c < d korral kirjuta d = qc + r, kus 0 ≤ r < c. Süsteem ebaõnnestub mõne summa puhul parajasti siis, kui 0 < r < c − q. Süsteemis 1, 3, 4 kehtib d = 4 = 1 × 3 + 1, seega q = 1 ja r = 1 ning võrratus 0 < 1 < 2 kehtib. Süsteem ebaõnnestub ja leht leiab esimese kaotuse summal 6:
  
  $4 = 1 \times 3 + 1 : q = 1, r = 1, 0 < 1 < 3 - 1 = 2$
2. Nüüd on c = 5, seega d = 5q + r ning kontrollitav tingimus on 0 < r < 5 − q. Mida suurem on q, seda vähem võimalusi jääb r-ile:
  
  $d = 5 q + r, 0 \leq r < 5 : 0 < r < 5 - q$
3. Kui q = 1 (d vahemikus 6 kuni 9), võib r olla 1, 2 või 3, seega ebaõnnestuvad d = 6, 7 ja 8. Kui q = 2 (10 kuni 14), sobivad r = 1 või 2: 11 ja 12. Kui q = 3 (15 kuni 19), sobib ainult r = 1: 16. Alates q = 4 on 5 − q väärtus 1 või väiksem ning ükski r enam ei sobi:
  
  $q = 1 : d \in {6, 7, 8} q = 2 : d \in {11, 12} q = 3 : d = 16 q \geq 4 : 5 - q \leq 1$
Vastus

Ebaõnnestuvad kuus väärtust: 6, 7, 8, 11, 12 ja 16. Ülejäänud üheksateist töötavad, nende seas kõik d väärtused 17-st kuni 30-ni. Sisesta 1, 5, 12, et jälgida üht kuuest ebaõnnestuvast juhust. Ahne meetod tasub 15 kujul 12 + 1 + 1 + 1 ehk nelja mündiga, kuigi piisaks kolmest viiesest.

$d \in {6, 7, 8, 11, 12, 16} 15 = 12 + 1 + 1 + 1 = 5 + 5 + 5$

Õpitee

Miks on algoritm õige

Allikad (3)

The bound the page draws as a dashed line and settles every system with: if greedy is ever beaten, the smallest amount where it is beaten lies strictly between c₃ + 1 and cₘ + cₘ₋₁; the three-coin rule the worked problem uses; the {1, 3, 4} example and the US system 1, 5, 10, 25, 50, 100 as canonical: D. Kozen and S. Zaks, "Optimal bounds for the change-making problem." Theoretical Computer Science 123(2), 1994, pp. 377-388. DOI 10.1016/0304-3975(94)90134-1
The pre-decimal coins and their values in pence (threepence, sixpence, shilling of 12d, florin of two shillings, half-crown of two shillings and sixpence, crown of five shillings), and the halfpenny's end as legal tender on 31 July 1969: Wikipedia contributors, "£sd", Wikipedia, The Free Encyclopedia, accessed 3 October 2026.
Which coins made up the circulating set at the end, as the Royal Mint itself issued them in 1970: half-crown, florin, shilling, sixpence, threepence, penny and halfpenny: The Royal Mint, "1970 Pre-Decimal UK Proof Set", product description, accessed 3 October 2026.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.