RAČUNALNIŠTVO Je vračanje kovancev res preprosto? •ir ^ ^ ANDREJ TARANENKO -> V vsakdanjem življenju se pogosto srečamo z vračanjem kovancev, pa naj bo to na avtomatu za kavo ali v trgovini. Običajno plačamo večji znesek, kot je potrebno, potem pa dobimo vrnjeno razliko. Vprašanje, ki si ga bomo zastavili je, kako dosežemo, da dobimo vrnjeno najmanjše možno število kovancev. Definirajmo problem bolj splošno. Za podano množico vrednosti kovancev K = {ki,..., kd} želimo določiti, koliko kovancev potrebujemo, da izplačamo znesek, recimo znesek n. Problem vračanja kovancev zahteva, da za podani znesek izplačamo najmanjše možno število kovancev. V vseh situacijah v nadaljevanju predpostavimo, da imamo vedno na voljo dovolj kovancev vsake vrste. Primer. Izplačati moramo znesek n = 4, na voljo imamo kovance naslednjih vrednosti {1,2,3}. Vse možne rešitve so naslednje: {1, 3}, {2, 2}, {1,1, 2} in {1,1,1,1}. Vidimo lahko, daje najmanjše število kovancev, ki jih v tem primeru potrebujemo, enako 2. Pri evrih imamo na voljo kovance naslednjih vrednosti (v centih): {1,2,5,10,20,50,100,200}. Kako bi s temi kovanci vrnili naslednje zneske? Koliko kovancev bi vrnili vi? ■ [25 centov] (rešitev: 20 + 5, dva kovanca) ■ [98 centov] ? 26 presek 40 (2012/2013) 5 RAČUNALNIŠTVO Prodajalčev algoritem Kako ste se v prejšnjem primeru odločili, katere kovance boste izbrali? Verjetno ste razmišljali na enak način, kot razmišlja prodajalec, ko vrača denar: na vsakem koraku izberemo kovanec najvišje vrednosti, ki ga še smemo izbrati. Postopek računa za 98 centov, bi bil torej naslednji: ■ Izberi kovanec za 50 centov. Ostane še 48 centov. ■ Izberi kovanec za 20 centov. Ostane še 28 centov. ■ Izberi kovanec za 20 centov. Ostane še 8 centov. ■ Izberi kovanec za 5 centov. Ostanejo še 3 centi. ■ Izberi kovanec za 2 centa. Ostane še 1 cent. ■ Izberi kovanec za 1 cent. Znesek smo izplacali. Na ta nacin smo torej vrnili šest kovancev. Metoda, ki smo jo uporabili, se v racunalništvu imenuje požrešna metoda. Za to metodo je znacilno, da rešitev gradimo korakoma iz množice kandidatov, na vsakem koraku pa Oberemo kandidata, ki trenutno najvei: doprinese k o^malm re&tvL S požrešno metodo pa ne doMmo nujno najboljše rešitve (v našem primeru najmanjše števtfo vrnjemh kovancev). Poglejmo si prime^ ko se to zgodi. Primer. Rerimo, da mamo na voj kovance vrednosti {1, 3,4, 5}. Vrmti žetimo znesek n = 7. S požrešno metodo bi prišli do nas^nje rešitve: ■ !zberemo kovanec vrednosti 5. Ostane še 2. ■ !zberemo kovanec vrednosti 1. °stane še 1. ■ !zberemo kovanec vrednosti 1. Znesek smo izplačali. S požrešno metodo smo izplacali tri kovance. Vendar obstaja boljša rešitev: izplacamo samo dva kovanca (kovanca vrednosti 4 in 3). Tudi v splošnem velja, da moramo pri uporabi po- žrešne metode hiti previdni, saj lahko na prvi po-gledmislimo,dat>omodobili najt>oljšo možnoreši-tev, jDotem pa sta izlo^o, c^ii temiai^ilt^k:o. Zogac^i lega je potreh>no za vsak prot>lem dokazati, ali je pristop s požrešno m^oe^cš mmcm na^azi^ Vggorroemprimeru,kos jic^^^^^e^gt metodo ne do-h)imo najboljše rešitve, smo spremenili množico vre-bnoatia:ovanšov,glede mL szkaže š^asa „la teivreaoovti tovarnev, totlih ^o-zaaSno pSl d0tslls ({1, 2, 5,10, 20, 50,100, 200>), e po-žaešoo metodovedlno vmemonajmai^jše m0Žn0 šlo- tuajdonazai° g>v-kaz bomo naredili za nekaj vrednosti kovancev, saj šazznstolaosddnozti Mejam Oanačimo soVsek, klgsžeiimzlzglačaSi, zn.Naj bo najboljša rešitev (z najmanjšim možnim številom tovanzevjobtike ■ n= 200a + 100b + 50c + 20d + 10e + 5f + 2g + h. Oolino jo b < 1, naj bl eloos laVbo b zmanjšali za 2 in a pooooall za 1; iabo bl zmanjšall šivollo osnjonlV bnoanodo- Iz poVobnlV sazlogoo oolja inVl, Va jo c < 1, d < 2, e < 1, f < 1, g < 2 ln h < 1. Šo ooo, oolja, Va jo 2g + h < 4, eloos bl laVbo zmanjšall šPoollo bnoanodo iabo, Va bl znoeob 5 lzplaoall e bnoanoom z osoVnoetjo 5. Zaplšlmn sošlioo, bl jo Voblmo e pngsošnlm algo-slimom, boi ■ n = 200a' + 100b' + 50c' + 20d' + 10e' + 5f' + 2g' + h'. Ponoono laVbo eblopamo, Vajo b' < 1, eaj požrešna moioVa, oo jo mogooo, lzboso booanoo z osoVnoetjo 200- Iz poVobnlV sazlogoo Voblmo: c' < 1, d' < 2, e' < 1, f' < 1, g' < 2, h' < 1 ln 2g' + h' < 4. Ker je n = 5 (40a + 20b + 10c + 4d + 2e + f) + 2g + h in velja 2g + h < 4, g < 2 in h < 1, dobimo pri deljenju števil n in 2g + h s številom 5 isti ostanek. To v matematiki zapišemo kot ■ n = 2g + h (mod 5). Na podoben nacin dobimo PRESEK 40 (2012/2013) 5 27 RAČUNALNI Š TV O Zaradi Tg + h < 4 in Tg' + h' < 4 velja g = g' in h = h'. Označimo z n-1 = (n- (Tg + h) + /55. Število n1 je naravno število, saj je (n - (Tg + h)) deljivo s 5. Ponovno lahko dobimo ■ m = f (mod T) in ni = f' (mod T). Ker je /< 1 in /'< 1 velja f = f'. S podobnimi razmisleki pokažemo, da jea = a', 0 = b', c = c', d = d' in e = e'. Torej s požrešno metodo zaevrske kovance vrnemo vedno najmanjše možno število kovancev. vrednosti 20). Vrednosti minKovancev(29), minKovancev(28), minKovancev(25), minKovancev(20) in minKovan-cev(10) izračunamo na enak nacin, torej rekurzivno. Ustavitveni pogoj rekurzivnega klicaje znesek 0, saj zanj ne vrnemo nobenega kovanca. Kako smo v prejšnjem primeru razmišljali? Naj bo n znesek, ki ga vracamo. Predpostavimo, da izberemo kovanec vrednosti k, torej smo vrnili en kovanec, moramo jih še vrniti toliko, kot jih vrnemo za znesek n - k. Za znesek 0 je rešitev, da ne vrnemo nobenega kovanca. Postopek bi lahko zapisali, kot je prikazano v algoritmu 1. Pravilna rešitevvvsakem primeru Kako bi izračunali optimalno rešitev za primeo s poljubnimi vrebnostmi kovencea? Eden od načinov je, epa se problema lotime s prideopom deli m vladaa. Ta 0?istop k reševanju problemop jen bil v Preseku lita opisaa (Prosek 4, T009dT010). distvo paisiopt je, da nalogo danego petblema razdelimo na manjae na-)ogjj istega problema, ki jih običajno rešimo rekurzivno. Primer. Recimo, da želimo s kovancr vrednoati {1, T, ?s 10, T0} (vcenoih) vrniti 30 centov. Veveda bi radi ponovno vrnbi najmanjše možno štovilo kovancev. Označimo z minKovancealn) najmanjše šievilo kdt dancev za rzplačano mrednosn n. Iščemo toroj minKovaacev(r0). Naomanjše možno štroilo kovan-nev izročunamotako, da izberemo najmanjšo izmed naslednjih rešitev: ■ V + minKovančev(T9) (če je v rešitvi kovaneč raeolnosti 1), ■ 1 a mrnKoganceg^S) (ce je g aešitgi koranec raeOnosti 2), ■ 1 + minaoganceg(25) (ce je g aešitgi koganec gaertaosti !j), ■ 1 + mmKoganceg(20) (ice je g aešitgi kogrnac raeOnosti 10) in ■ 1 + minKarpnašr(10) (aa ja r laeitri darpnaa Algorjtem 1: minKovancev(n) Vhod: znesek n, vrednorti kovancmv kovaaci Izhod: oajmaojše kovdooav za izplaZila znekkb n 1 if n = k thea 2 | oe^rn 0 3 enm 4 v 4- oo 5 for all /c na množice kovanci, kjer je k < n do 6 | v — min{v, mCaKoaanci(7^ — o)-- -L} T end 8 return v Rekurzivna reškev sevedani učinkovito, saj pogosto večkrat račun a rešitev za iste zsed nositi zne skov. Temu se lahkz izognemo takp, da si tešitve za že izračunane vrndnosti shranimo. Algofitem najprej preveri, če je želena rešitev že bila izšačunana. Če je bila, uporabi shranjeno vrednost, sičet jo izračuna. Torej v algbritmu potrebujemo polje, v katero si ze boe vrednosti od 0 do n shranimo rešipev, lav ja le-ta znanai. Na aa način dobrine učinkovitetši algoritem. ki je zapisan z algoritmom 2. V algoritmu 2 predpostavimo, da je vrednost shrknjeneVrednzsti[0] = 0. Prtatjitt sami, da za primtj zntska 7 in artdnzsti kzaancta {1, 3,4, 5} dzbimz zptimalnz jtiitta, ki jt Ari pjjžjtSni mttzdi nismz dzbili. Razmislite tudi, kakz bi prilagzdili prtdstaaljtnz jtiitta, ct bi žt- 28 PRESEK 40 (2012/2013)5 RAČUNALNIŠTVO Algoritem 1: minKovancev(n) Vhoeij znesek n, vrednosti kovancev kovanci Izhod: najmanjše število kovancev za izplačilo zneska m ifshranjeneVredncsti[n] ni prazno then | return sliranje;n(eVi/re(lnoi5ti[nl iend V <— OO for ali k iz množice kovanci, kjer je k < n | v — min{v,minKovvaci(n — k) + k} rnd shranjeneVrednosti [n] = v leli acleg števila venjenih kovancev vedeti še, katere kovance ieberemo. Predstavljeni aecblem lahkc še bclj zaostrimo, saj smc do sedaj aredacstavljali, da imamc kovancev vsake vrednosti dovolj na ealogi. Razmislite, kako bi se saremenil algoritem, ce imeli aoeajek, koliko kovancev aosameene vrednosti imamo na raeaolago. _ XXX REŠITEV POiSCi MINE S STRANI 25 Križne vsote • Naloga reševalca je, da izpolni bele kvadratke s števkami od 1 do 9, tako, da je vsota števk v zaporednih belih kvadratkih po vrsticah in stolpcih enaka številu, ki je zapisano v crnem kvadratku na začetku vrstice (stolpca) nad (pod) diagonalo. Pri tem pa morajo biti vse števke v posamezni vrstici (stolpcu) raz-licne. 14 10 8 9 6 13 16 11 8 10 \ 11 11 REŠITEV 1 m 2 m 2 2 m m m 4 m 2 1 m m 1 0 0 0 Z 6 LL L Z 6 - L E S LL 6 L E 0L S 9 \8 LL S 8 6 Z 9 \ 0L Pl XXX XXX PRESEK 40 (2012/2013) 5 29