InfoC adventi naptár
Visszalépő keresés
A Mikulás idén univerzális ajándékokat osztogat: egyszerűen pénzt ad. :)
Segítsünk neki: mondjuk meg, hogy egy adott összeg hogyan fizethető
ki a legkevesebb pénzdarabbal. Vegyük figyelembe azt is,
hogy lehet, egy adott fajta pénzből (pl. ötezresből) nincs elegendő!
A gyakon, a ciklusok és a tömbök magasságában szerepelt egy program,
amely egy egyszerű bankautomatát valósít meg. Az automata a megadott
összeget úgy próbálja meg kiadni, hogy minél kevesebb bankjegyet használjon
közben. Vagyis úgy, hogy a nagyobb címleteket részesíti előnyben:
CIKLUS, AMÍG összeg > 0 ÉS van még címlet
db = összeg/címlet (egész osztás, lefelé kerekít)
HA db > amennyi van
db = amennyi van
kiír: "kiadva", db, címlet
összeg = összeg - db * címlet
következő iterációban: következő kisebb címlet
CIKLUS VÉGE
HA összeg > 0
kiír: "nem lehetett kiadni"
FELTÉTEL VÉGE
Ha nincsen végtelen sok bankjegy, akkor ez az algoritmus hibázhat. Tegyük fel, hogy 6000
forintot kell kiadni, és van egy rakat 5000-es, egy rakat 2000-es, de nincs 1000-es (lásd a
táblázatot). Ilyenkor a program azt írja ki, hogy egy 5000-est kiad, és utána kiírja, hogy nem
tudja kiadni a többit. Pedig megoldható lenne a feladat 3×2000 Ft kiadásával. Többen meg is
oldották ezt a feladatot szorgalmiként – nézzük meg, hogyan!
Hogyan javítható a program? Az alábbi ötlettel.
Tegyük fel, hogy kiadtunk egy 5000-est, ezek után kiderül, hogy úgy nem oldható meg a probléma.
Vegyük akkor vissza azt az 5000-est, és próbáljuk meg újra úgy, hogy abból nem adunk. Akkor a
következő címlet a 2000-es. Abból van bőven, 6000/2000=3, kiadunk hármat, és kész is vagyunk.
Ez az algoritmus mindannyiunk fejében lejátszódhat, csak nem nagyon figyelünk rá.
A keresésnek ezt a módszerét úgy nevezik, hogy backtrack (backtracking search), magyarul
visszalépő keresés. Megvalósítani ezt is rekurzióval lehet.
FÜGGVÉNY backtrack(részmegoldás)
HA a részmegoldás teljes, és helyes 1
kiír: megoldás
VISSZATÉRÉS a fv-ből.
FELTÉTEL VÉGE
HA a részmegoldás nem jó 2
VISSZATÉRÉS a fv-ből.
FELTÉTEL VÉGE
CIKLUS, AMÍG (tippek halmaza)
backtrack(részmegoldás + tipp) 3
CIKLUS VÉGE
FÜGGVÉNY VÉGE
A fenti függvény egy általános séma a visszalépő kereséssel megoldható
problémák megoldására. Működésének lényege a következő. Paraméterként egy részmegoldást kap,
amelyet be kell fejezni. (Részmegoldás természetesen az el sem kezdett megoldás,
és a teljes megoldás is.) Először
megnézi, hogy a részmegoldás teljes és helyes megoldása-e
a feladatnak; 1 ha igen, akkor kiírja azt. Ha a
részmegoldáson látszik, hogy nem vezet majd eredményre,
2 akkor nem ír ki semmit, csak visszatér a függvényből.
Ha ezen a két feltételen túljutunk, akkor az azt jelenti, hogy van egy
részmegoldásunk, amiről még nem tudjuk, hogy végül lehet-e helyes.
Ezért sorba vesszük a tippjeinket, amelyek közelebb
vezethetnek a célhoz, és végigpróbáljuk mindegyiket. 3
Ehhez a paraméterként kapott
részmegoldást kiegészítjük a tippünkkel, és meghívjuk a függvényt
saját magát, hogy ellenőrizze azt, és egészítse ki további lépésekkel (tippekkel), ha kell.
Hogyan adaptálható ez a bankautomatás példára? 6000 forintot kell kiadni.
A tipp az, hogy ha adunk egy 5000-est, az eredményre vezethet, hiszen
közelebb kerülünk a megoldáshoz (már csak 1000-et kell majd kiadni). Vagyis a
backtrack(6000) függvényhívás után lesz egy backtrack(1000) függvényhívás.
Ez azonban nem fog eredményre vezetni, mivel nincs 1000-es az automatában.
Ezért meg kell próbálnunk úgy, hogy nem adjuk ki az 5000-est. Végülis ennyi az egész.
Annyiban más a helyzet, hogy most nem az összes lehetséges megoldást
keressük, hanem a legegyszerűbbet. Pl. nem lényeges, 100000 forint kiadható
100 darab 1000 forintossal, ha van 5 darab 20000-es is. Ha a függvénynek
adunk visszatérési értéket is (IGAZ: helyes megoldás, HAMIS: helytelen
megoldás), akkor meg tudjuk azt is oldani, hogy a megoldás megtalálása esetén
rögtön leálljon a keresés. Ha a preferált megoldásoktól (tippektől) haladunk
a kevésbé preferáltak felé, akkor pont a számunkra legkedvezőbbet fogjuk
megkapni először.
FÜGGVÉNY fizet(összeg, rekesz)
HA összeg=0, AKKOR
VISSZATÉRÉS: sikerült!
HA nincs több címlet
VISSZATÉRÉS: ebből nem lesz megoldás.
db=összeg/címlet
HA db > amennyi van abból a címletből
db = amennyi van
FELTÉTEL VÉGE
sikerült = fizet(összeg - db * címlet, következő rekesz) rekurzió
AMÍG nem sikerült ÉS db >= 0
db = db - 1
sikerült = fizet(összeg * címlet, következő rekesz) rekurzió
CIKLUS VÉGE
HA sikerült ÉS db > 0
kiír: "kiadva: db, címlet"
rekeszben bankjegyek = bankjegyek - db
FELTÉTEL VÉGE
FÜGGVÉNY VÉGE
A visszatérési érték azért is hasznos, mert a függvény meghívása után
a legfelső szinten is látjuk, hogy a feladat megoldható-e. Pl. az 5000 forintos
kiadása után a „sikerült” változó értéke hamis lesz, ezért nem írunk
ki semmit, és az adott rekeszben lévő bankjegyek számát sem csökkentjük
le. Ha igazzal tért volna vissza, akkor kiírhatnánk, hogy ki lett adva;
a függvény ezen a ponton nem tudja, hogy a fennmaradó pénzösszeg hogyan
lett kifizetve, csak azt, hogy az 5000-es kiadása jó tipp volt.
A maradék pénz kifizetésének módját a rekurzió lentebbi szintjein
már kiírta, ezért itt nem is kell vele foglalkozni.
Egyéb, backtrackkel megoldható problémák:
- Nyolc királynő: hogyan lehet sakktáblán elhelyezni nyolc királynőt úgy,
hogy azok ne üssék egymást?
- Sudoku: a legnehezebb sudoku feladványok nem oldhatók meg szisztematikusan,
hanem elérkezünk néha egy olyan ponthoz, ahol tippelnünk kell. Ilyenkor
tippelünk, és folytatjuk a megoldást; ha a tipp rossz volt, akkor kiradírozunk
mindent a tippelés pontjáig visszamenőleg, és mással próbálkozunk.
- Keresztrejtvények (megoldása és kitalálása is).
- Útkereső algoritmusok.
A lenti program kétszer ad ki 6000 forintot. A bankautomatában 1 db 1000-es
van, ezért először az 5000+1000 még megoldás, másodjára már nem az,
csak a 3×2000. Harmadjára pedig már sehogyan nem lehet kiadni 6000 forintot.
#include <stdio.h>
typedef struct {
int ft;
int db;
} Rekesz;
int kifizet(int osszeg, Rekesz rekeszek[], int melyiktol) {
int db, sikerult;
/* ha nem kell fizetni semmit, akkor sikerult, ki van fizetve. */
if (osszeg==0)
return 1;
/* ha kene meg fizetni, de nincs tobb lehetseges banjegy, akkor nem megy */
if (rekeszek[melyiktol].ft<0)
return 0;
/* kene adni a mostani rekeszbol? mennyit? */
db=osszeg/rekeszek[melyiktol].ft;
if (db>rekeszek[melyiktol].db)
db=rekeszek[melyiktol].db;
/* probaljunk meg ennyit adni (es utana tovabb a kovetkezo rekeszre) */
sikerult=kifizet(osszeg-db*rekeszek[melyiktol].ft, rekeszek, melyiktol+1);
while (!sikerult && db>=0) {
/* ha nem sikerul, probaljuk meg kevesebbel. */
db--;
sikerult=kifizet(osszeg-db*rekeszek[melyiktol].ft, rekeszek, melyiktol+1);
}
/* kijottunk a ciklusbol. vagy mert sikerult kifizetni az adott modon,
* vagy mert nem jo, hogy ebbol a ftbol adni probalunk. */
if (sikerult && db>0) {
printf(" %d db %d Ft-os kiadva\n", db, rekeszek[melyiktol].ft);
rekeszek[melyiktol].db-=db;
}
return sikerult;
}
int main() {
Rekesz rekeszek[]={
{ 20000, 10 }, /* ft, db */
{ 10000, 8 },
{ 5000, 1 },
{ 2000, 5 },
{ 1000, 1 }, /* 1 db ezres */
{ -1 } /* tomb veget jeloli */
};
int siker, o;
o=6000;
printf("%d-t adok:\n", o);
siker=kifizet(o, rekeszek, 0);
printf("%s\n\n", siker?"Sikerult!":"Nem sikerult!");
printf("%d-t adok:\n", o);
siker=kifizet(o, rekeszek, 0);
printf("%s\n\n", siker?"Sikerult!":"Nem sikerult!");
printf("%d-t adok:\n", o);
siker=kifizet(o, rekeszek, 0);
printf("%s\n\n", siker?"Sikerult!":"Nem sikerult!");
return 0;
}
