Generikus algoritmusok

2. Menürendszer I. – a feladat

Írjunk programot, amelyben menüből választhatjuk ki a teendőt!

1. Összeadás
2. Szorzás
3. Hatványozás
0. Kilépés
Melyik? _
printf("1. Összeadás\n"); // 1. sorminta
printf("2. Szorzás\n");
printf("3. Hatványozás\n");
printf("0. Kilépés\n");
scanf("%u", &valasztas);
if (valasztas < 4) {
    switch (valasztas) {
        case 1: eredm = osszead(a, b); break; // 2. sorminta
        case 2: eredm = szoroz(a, b); break;
        case 3: eredm = hatvanyoz(a, b); break;
    }
    printf("E = %d\n", eredm);
}

A sormintákkal mindig az a baj, hogy nehezen módosítható, nehezen karbantartható programkódot eredményeznek.

Itt, hogy a switch(), ahol a beírt szám alapján kiválasztjuk a teendőt, ne legyen túl áttekinthetetlen, az egyes lépéseket eleve függvénybe tettük. Ez jó is – egészen addig, amíg nem kell módosítani a menüt. Tegyük fel, hogy a 2-es menüponthoz szeretnénk beszúrni a kivonást. A teendők:

  • Beszúrunk egy printf()-et az összeadás és a szorzás közé.
  • Ezek után a többit is átszámozzuk (szorzás, hatványozás).
  • A switch() előtti if()-nél átírjuk a számot (amely a menüpontok számával van összefüggésben) 5-re.
  • Beírjuk a switch()-be az új case 2-t.
  • Átszámozzuk a többi case-t is.

Ennél biztosan van jobb megoldás is. A sorminta mindig elkerülhető. Például a menüpontok nevei betehetőek tömbbe, és akkor egy ciklussal elvégezhető a kiírás és a beszámozás. Vajon a menüpontok maguk, azaz a függvények is betehetőek a tömbbe? Ha igen, meg tudjuk szüntetni a második kódduplikációt is!

3. Ismétlés: a függvényhívás menete

A függvényhívás menetéről már volt szó régebben. Ismétlésként foglaljuk ezt össze!

#include <stdio.h>
#include <math.h>

double negyzet(double a) {
    return a * a;
}

int main(void) {
    double x = negyzet(5.9);
    double y = sin(6.1);

    printf("%g", x + y);
    return 0;
}

Minden függvényhíváskor lefoglalódik egy terület a veremben, amely az adott híváshoz tartozik, és visszatéréskor megszűnik: ez a keret (stack frame).

A függvényhívás előtt a fenti példában a következő történik:

  • A hívó, azaz a main() beteszi a verembe a paramétereket.
  • Helyet csinál a visszatérési értéknek is.
  • Meghívja a függvényt, ami által bekerül a verembe a visszatérés címe (vagyis hogy hol kell folytatni a programot a függvényből visszatérvén).

A negyzet() függvényben a működés:

  • A paramétereit a veremben találja.
  • A visszatérési értéket a verembe teszi, a megfelelő memóriaterület felülírásával.
  • Amikor visszatér, akkor a hívóhoz ugrik vissza, az eltárolt visszatérési cím alapján.

A függvényhívás után a hívó:

  • A veremben megtalálja a visszatérési értéket. Ezt felhasználja, ha szeretné.
  • Kitörli a veremből az általa betett dolgokat, hiszen azokra már nincsen szükség.

Mi lenne, ha egy másik függvényt hívnánk meg ugyanolyan kerettel?

4. Függvényre mutató pointer: a háttérben…

Ha két függvénynek egyforma a fejléce, akkor egyformán kezelik a vermet, és ezért kompatibilisek egymással.

double negyzet(double a);
double sin(double alfa);

függvényre
mutató pointer
int main(void) {
  double (*fptr)(double);   // ptr létrehozása
  double x;

  fptr = negyzet;           // ptr beállítása
  x = fptr(3);  /* negyzet(3) */

  fptr = sin;
  x = fptr(5);  /* sin(5) */

  return 0;
}

Mi is történik itt? Tegyük fel, hogy van egy függvényünk, amelyik egy darab double paramétert vár, és egy darab double paramétert ad vissza. Ha meghívjuk ezt a függvényt, akkor a hívó felépít hozzá egy keretet, amelyben ezeknek az értékeknek meglesz a megfelelő helye. A hívott fogja tudni, hogy a verem tetejéhez képest hol találja a paramétereket és hova kell tennie a visszatérési értéket. (Ennek technikai részleteiről természetesen a fordító gondoskodik.)

Ha van egy másik függvényünk, amelynek ugyanilyen a prototípusa, akkor a hívási keret megfelelő felépítése után meghívhatjuk azt is. Hiszen az a függvény a veremben ugyanott fogja keresni az ugyanolyan típusú értékeket. Vagyis ha a keretet megfelelően építjük föl, meghívható akár a negyzet(), akár a sin() függvény. Ennek pedig semmi akadálya nincs, ha a két függvény prototípusa megegyezik.

Így bevezethetjük a függvényre mutató pointer típust. Ez azt a memóriacímet tárolhatja, ahol a függvény található a memóriában. Ez a cím képezhető, akár elmenthető egy függvénypointer típusú változóba, és egy függvénypointer segítségével meghívható a függvény. A függvény hívása ilyenkor az alábbi módon fog történni:

  • Felépítjük a hívási keretet a megfelelő módon.
  • Arra a memóriacímre ugrunk a végrehajtással, amire a pointer hivatkozik.
  • Miután visszatért, a veremből kivesszük a visszatérési értékét, és töröljük a keretet.

Mivel azt tudni kell, hogy mi legyen a hívási keret felépítése, ezért a függvénypointer típusában benne kell legyen az általa hivatkozott függvény prototípusa. Ezért néz így ki fent az fptr változó definíciója:

double (*fptr)(double);

5. A függvénypointer típus szintaktikája

Hogyan definiálunk egy függvényre mutató pointert?

Függvényre mutató pointer típusú változó:

Fontos a *-ot
és a nevet
körbevevő zárójel!
Minek van
a zárójel?
VisszaTíp (*változónév)(ParamTíp, /*...*/);
double (*fptr)(double);
fptr = sin;

Egy számra mutató pointernél is a pointer típusából tudja a fordító, hogy a dereferálása esetén milyen típusú értéket vehetünk ki a memóriából (pl. int* egy egész számra mutat, double* valósra). A függvényre mutató pointereknél ugyanez a helyzet: a pointer típusából tudja a fordító, hogy mik a hívott függvény paraméterei és mi a visszatérési értéke. Vagyis hogy hogyan kell számára a hívási keretet felépíteni. Tehát a függvényre mutató pointer típusú változónak a típusa két információt kell magában hordozzon: 1) hogy egy pointerről van szó, 2) hogy milyen paraméterezésű függvényre mutat.

A jobb oldali zárójel és a benne lévő (double) mutatja, hogy egy függvényről van szó, amelynek egy double paramétere van. A bal oldali double pedig azt, hogy ha meghívjuk a függvényt, egy valós számot kapunk vissza. A változónév előtti * jelzi, hogy az fptr változó egy pointer, amely az előbb részletezett fejlécű függvényre mutat.

Már csak egy a kérdés: miért van a (*fptr) zárójelben? Azért, mert a kifejezés a változódeklarációknál megszokott logikát követi: úgy deklaráljuk a változót, ahogy használni fogjuk, és a deklaráló kifejezésben az operátorok szokásos precedenciája érvényes. Itt a változó neve fptr. Az első zárójelpár a precedenciát adja meg: (*fptr) miatt a * operátor az fptr-hez tartozik, nem pedig a bal szélső double-höz. Emiatt fptr egy olyan pointer, ami... Mire is mutat? A deklaráció maradék része a double ___(double) – vagyis egy olyan függvényre, amit double paraméterrel meghívva double-t kapunk vissza.

Amit tehát fontos megjegyezni:

  • Zárójel veszi körül a változó nevét a csillaggal.
  • Az argumentumoknál csak a típusokat soroljuk fel, vesszővel elválasztva.

Legegyszerűbben így tudjuk ezt észben tartani: ha egy függvénydeklarációban a név elé teszünk egy *-ot, majd azt és a függvény nevét bezárójelezzük, függvénypointert kapunk.


Hogyan segít ebben a typedef?

A típust a typedef is megadhatja:

Emlékezzünk vissza: a typedef után írt dolog szintaxisa tökéletesen megegyezik a változódeklaráció szintaxisával. Tehát ha típusként szeretnénk definiálni egy függvényre mutató pointert, ugyanazt kell csinálnunk, mint a változóknál, csak a sor elejére még a typedef kulcsszó is odakerül. A fenti példában az EgyvaltozosFvPtr nevű típus lett definiálva függvénypointerként.

typedef VisszaTíp (*ÚjTípusNév)(ParamTíp, /*...*/);
typedef double (*EgyvaltozosFvPtr)(double);
EgyvaltozosFvPtr f;
f = sin;

A typedef a bonyolult típudefiníciók megalkotásában sokat segíthet, ugyanis lehetővé teszi azt, hogy lépésenként építsük meg a típusnevet. Például a függvényre mutató pointer típus „megépíthető”, előbb a függvény, utána pedig a pointer típus definíciójával:

typedef double EgyvaltozosFv(double);
typedef EgyvaltozosFv *EgyvaltozosFvPtr;

Ennek az első sora a double ___(double) alakú, egyváltozós matematikai függvények típusát definiálja EgyvaltozosFv néven. A második sor pedig egy ilyenre mutató pointer típust definiál, EgyvaltozosFvPtr néven. Látszik, hogy ilyenkor a zárójelre már nincsen szükség, mivel a függvény típus össze lett vonva egy szóvá.

Miért kell a zárójel a csillag köré?

Lássunk ellenpéldákat! Ha a deklarációban a név elé nem tennénk *-ot, akkor nem is változót, hanem egy függvényt deklarálnánk. Leírva azonnal látjuk:

double f(double);

Ha pedig nem tennénk az így becsillagozott kifejezést zárójelbe, akkor is függvényt deklarálnánk. Ez esetben a * operátor a visszatérési érték része lenne, tehát olyan függvényről lenne szó, amelyik egy pointerrel tér vissza:

double * f(double);

A függvénypointer típus különálló deklarációja sokat segíthet a szintaxis érthetőbbé tételében. Különösen akkor, ha olyan függvényünk van, amelyik maga is függvénypointert vesz át paraméterként, vagy ad a visszatérési értékében. Erre legjobb példa a szabványos signal() függvény, amelyik függvénypointert kap, és függvénypointert is ad vissza:

typedef void (*sighandler_t)(int);
sighandler_t signal(int signum, sighandler_t handler);

Ezen egyből látjuk, hogy a függvény második paramétere ugyanolyan típusú, mint a visszatérési értéke. Ellenben ugyanez typedef nélkül ilyen lenne:

void (*signal(int signum, void (*handler(int)))(int);

6. Menürendszer II. – a mutató típus

A menüpontok függvényei:

int osszead(int a, int b) {
    return a + b;
}

int szoroz(int a, int b) {
    return a * b;
}
int hatvanyoz(int a, int b) {
   int eredmeny = 1;
   for (int i = 0; i < b; ++i)
      eredmeny *= a;
   
   return eredmeny;
}

Vagyis minden függvény megkap két számot és elvégez rajtuk egy műveletet, aminek az eredményét a visszatérési értékben közli.


Ezekre a függvényekre egy ilyen pointer tud mutatni:

typedef int (*MatFv)(int, int);

7. Menürendszer III. – a tömb és használata

typedef int (*MatFv)(int, int);

typedef struct {
    char const *nev;
    MatFv pfv;
} MenuPont;
MenuPont menupontok[] = {
    { "Összeadás", osszead },
    { "Szorzás", szoroz },
    { "Hatványozás", hatvanyoz },
    { NULL, NULL }   /* végjel */
};

Mivel mutatókat tárolnak, ezért utolsó elemnek betehető egy NULL érték, ami jelzi a végét – így biztonságosan kezelhető. Ez egy végjel: amikor egy ciklus fut a tömbön, a tömb tartalma alapján tudni fogja, hol van a vége. Nem kell majd külön szerepelnie a programban a tömbméret megadásának sem. Ezt a trükköt már rengetegszer használtuk.


A menüpontok kiírása:

menü kiírása
és a hívás
for (i = 1; menupontok[i-1].nev != NULL; ++i)
    printf("%d. %s\n", i, menupontok[i-1].nev);
meret = i;

A for ciklus indexváltozójának utolsó értéke a NULL elem indexe, vagyis a tömbben lévő értékes elemek száma. Ezzel az értékkel tudjuk ellenőrizni, hogy a felhasználó által bevitt menüpont értéke érvényes-e.

A kiválasztott menüpont végrehajtása:

if (val >= 1 && val <= meret) {
    eredmeny = menupontok[val-1].pfv(a, b); // fv pointer
    printf("Eredmény: %d\n", eredmeny);
} else {
    printf("Nincs ilyen menüpont\n");
}

A fenti kifejezés működése részletesen:

Kifejezéstípus
menupontokstruktúrák tömbje, a menüpontok leírása
menupontok[index]egy struktúra, menüpont leírása
menupontok[index].fvegy függvényre mutató pointer
menupontok[index].fv(2.6, 3)2.6, 3 paraméterekkel meghívva az egyik függvény

Ezzel a függvénypointereket a hozzájuk tartozó leírással egy tömbbe tettük. Így az egy új menüpont hozzáadása nagyon egyszerű, csak a tömböt kell módosítani. A működés automatizált, ha új menüpontunk van, csak kiegészítjük a tömböt, és minden további programrész helyesen kezeli.

8. Az év eleji tételek generikus változata

Mivel a függvények értékként kezelhetőek, és paraméterként adhatóak át, egyes algoritmusok működése megfogalmazható általánosságban is. Gondoljunk a programozási tételekre a félév eleji anyagból – ezek mind generikus algoritmusok:

  • Számlálás tétele: adott tulajdonságú elemek darabszáma
  • Maximumkeresés tétele: legvalamilyenebb elem megkeresése

Megfogalmazhatók általánosságban is, hogy a kód szintjén is generikusak legyenek.

generikus
számlálás
int szamlal(long *tomb, int n, bool (*pred)(long)) {
    int db = 0;
    for (int i = 0; i < n; ++i)
        if (pred(tomb[i]))     // adott tulajdonságú?
            ++db;
    return db;
}

A program forráskódja is így nagyon szemléletes. Akárhány függvényt írhatunk, amelyek tulajdonságokat vizsgálnak. Ezek a predikátumok:

unáris
predikátumok
bool negativ(long x) {
    return x < 0;
}

bool paros(long x) {
    return x % 2 == 0;
}

A függvényeket pedig egyszerűen paraméterként átadjuk:

long tomb[10] = {………};
printf("%d negativ van.\n", szamlal(tomb, 10, negativ));
printf("%d   paros van.\n", szamlal(tomb, 10, paros));

A függvény tehát paraméterként kapja a vizsgálandó számsort, továbbá egy másik függvényt, a predikátumot. Ezt a függvényt meghívja minden elemre – ez a függvény mondja meg, hogy az adott elemeket bele kell-e épp számolni, vagy nem. Hogy épp a negatív számok esetén növeljük a számlálót, vagy a páros számok esetén.

9. Generikus rendezés

A rendezőalgoritmusokat is meg tudjuk fogalmazni generikusan. Ott ugyanez a helyzet, mint a számlálásnál vagy a keresésnél. Az algoritmus maga ugyanaz, csak az változik, hogy melyik tömbelem kisebb, melyik nagyobb – egész pontosan, hogy melyik való a tömb elejére, és melyik a végére, mert kisebbről és nagyobbról itt már nem beszélhetünk.

void rendez(double *t, int n, bool (*p)(double, double)) {
    for (int i = 0; i < n-1; ++i) {
        int leg = i;
        for (int j = i+1; j < n; ++j)
            if (p(t[j], t[leg]))  // !
                leg = j;
        if (i != leg)
            csere(&t[i], &t[leg]);
    }
}

A függvénynek adott predikátum most nem egy-, hanem kétparaméterű. Ugyanis nem egy elemről kell megmondania, hogy rendelkezik-e valamilyen tulajdonsággal, hanem két elemet kell összehasonlítania; előrébb való-e az egyik a rendezett tömbben, mint a másik. Ha a kisebb elemekre mondjuk azt, hogy előrébb való, akkor növekvő sorrendet kapunk. Ha a nagyobb elemek kerülnek előre, akkor csökkenő lesz a sorrend.

bináris
predikátumok
bool kisebb(double a, double b) {
    return a < b;
}

bool nagyobb(double a, double b) {
    return a > b;
}

Az előző pont egyparaméterű predikátumait unáris predikátumnak nevezzük (unary predicate). Az összehasonlító, kétparaméterű predikátumokat pedig binárisnak (binary predicate).

10. Állapotgépek függvényre mutató pointerrel

A tevékenység egy függvény:

typedef struct AllapotPont {
    Allapot kovetkezo;
    void (*tevekenyseg)(void);
} AllapotPont;

Az állapotgépet kezelő program:

Esemeny esemeny;
Allapot allapot;

while ((esemeny = uj_esemenyre_var()) != -1) {
    /* meghívjuk az adott tevékenység függvényét */
    tabla[allapot][esemeny].tevekenyseg();
    /* lépünk a következő állapotba */
    allapot = tabla[allapot][esemeny].kovetkezo;
}

Hogy ne legyen túl sok állapotunk, a tevékenységeket érdemes paraméterezni. Például a tevékenységnek paramétere lehet az aktuálisan beolvasott karakter, vagy egy kiírandó szöveg is. Így egyszerűsödhet az állapotgép.

Generikus algoritmusok tömbökön

12. Sztringek rendezése: qsort() és strcmp()

A rendezés megvalósítására a C szabványos könyvtára tartalmaz egy qsort() nevű generikus algoritmust. Ennek az összehasonlítás kritériuma, azaz a rendezési reláció megadható. Ha sztringeket szeretnénk rendezni, könnyű a dolgunk: az szintén szabványos strcmp() függvény lehet a paraméter:

alma barack korte szilva 
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main(void) {
    char szavak[4][20] = {
        "barack", "alma", "szilva", "korte",
    };
    qsort(szavak, 4, 20, strcmp);   // db = 4, meret = 20
    for (int i = 0; i < 4; ++i)
        printf("%s ", szavak[i]);
    return 0;
}

Vegyük észre, hogy itt a függvénynek két paramétert is kell adni a tömbhöz. Egyrészt tudnia kell, hány eleme van (hány sztringet kell sorbaraknia). Ez itt db = 4. Másrészt pedig azt is látnia kell, hogy egy elem mekkora, vagyis hogy hány karakterből álló sztringeket kell cserélgetni. Ez meg meret = 20.

Tehát „mindkét irányban” változhat a méret, az elemszám és a sztringek hossza is tetszőleges. A qsort() paramétere ezért nem két dimenziós tömbre mutató pointer (amelybe bele kellene írni a tömb méretét is, pl. int (*p)[20]), hanem inkább egy void *. A void *-ként átadott mutatót lehetne (void*) szavak formában írni, kiemelve azt, hogy ott egy mutató konvertálásról van szó, de ezt nem szokás megtenni. A pointerek konverziója void *-ra, típus nélküli pointerre a C nyelvben automatikus, éppen ezek miatt az algoritmusok miatt.

A qsort() negyedik paramétere az összehasonlító függvény, amelyet meg fogja hívni minden elempárra, amit a rendezés közben össze kell hasonlítania.

13. Generikus tömbök: stdio, stdlib

A void * technika olyan hasznos, hogy a C könyvtár is alkalmazza:

/* fájlkezelés */
fwrite(void const *ptr, size_t meret, size_t db, FILE *fp);
fread(void *ptr, size_t meret, size_t db, FILE *fp);
/* gyorsrendezés, bináris keresés */
void qsort(void *tomb, size_t db, size_t meret,
           int (*hasonlit)(void const *, void const *));
void *bsearch(void const *kulcs, void const *tomb,
              size_t db, size_t meret,
              int (*hasonlit)(void const *, void const *));
/* dinamikus memóriakezelés */
void *malloc(size_t meret);
free(void *ptr);

Látjuk, hogy ez az ötlet végigvonul mindenhol. Az fread() és fwrite() megkapják a tömbök elemszámát, és az egyes elemek méretét. A gyorsrendezést és bináris keresést végző függvény szintén. Sőt még a malloc()free() páros is ilyen volt. A malloc() megkapja a foglalandó terület méretét bájtban, és void*-ot ad vissza; a free() is void*-ot vár. Egyik függvénynek sem kell tudnia, hogy tulajdonképp milyen típusú adattal dolgoznak.

14. qsort() és bsearch(): hasonlító függvény

A qsort() valójában nem foglalkozik vele, nem is tudja, hogy milyen típusú elemeket rendez. Az egyes elemeket meg tudja cserélni enélkül is (nyers adatot másol, mindig annyi bájtot, amennyi egy elem mérete). Az összehasonlítást pedig a paraméterként átvett függvényre bízza. Ennek a függvénynek a visszatérési értéke pont olyan kell legyen, mint ahogy azt a szabványos strcmp() is használja:

mint a
strcmp()
hasonlit(a, b) =
   negatív: ha a < b
     nulla: ha a == b
   pozitív: ha a > b

Vegyük észre, hogy ez egy kicsit más, mint a fentebb bemutatott bináris predikátum. Az igazzal tért vissza, ha a < b. Ez viszont egy int-et ad, aminek három leheséges értéke van, és azok a kisebb, egyenlő, nagyobb eseteket reprezentálják.

Például egy hasonlító függvény double típusú elemekre az alábbiak szerint implementálható. Figyelni kell arra, hogy mivel nem tudja a qsort(), hogy milyen adatokkal dolgozik, ezért a hasonlító függvénynek is void * típusú pointereket ad a két összehasonlítandó elemre. Egész pontosan void const *-ot, hiszen az összehasonlító függvénynek értelemszerűen nem dolga, hogy módosítsa az adatot.

Ezt a void * típusú pointert át kell konvertálnunk a saját típusunkra. De mivel tudjuk, hogy ezt a függvényt double elemeket tartalmazó tömb esetén adjuk majd a qsort()-nak, a konverzió jogos és helyes:

int hasonlit(void const *vp1, void const *vp2) {
    double const *sz1 = (double const *) vp1;
    double const *sz2 = (double const *) vp2;
    if (*sz1 > *sz2) return +1;
    if (*sz1 < *sz2) return -1;
    return 0;
}

int main(void) {
    double szamok[4] = {9.7, 3.4, 8.5, 1.2};
    qsort(szamok, 4, sizeof(double), hasonlit);
    for (int i = 0; i < 4; ++i)
        printf("%g ", szamok[i]);
    return 0;
}

Így tulajdonképpen a függvény bármilyen elemekből álló tömböt rendezni tud. Az egyes elemek méretét most a sizeof(double) adja meg. Vagy egyszerűen oda sizeof(szamok[0])-t is írhatnánk. (Egyébként az előző példában is a 20 * sizeof(char) lett volna teljesen korrekt.)

bsearch() használata

A bináris kereséshez ugyanilyen függvény van beépítetten, a bsearch():

int t[] = {23, 119, 47, -2, 54, 86};

/* bináris keresés csak rendezett tömbökön */
qsort(t, 6, sizeof(int), hasonlit_int);

int minta = 47;
int *talalt;
talalt = (int *) bsearch(&minta, t, 6, sizeof(int), hasonlit_int);

if (talalt != NULL)
    printf("Megtaláltam, itt van: %p\n", talalt);
else
    printf("Nincs a tömbben.\n");

Hogy ugyanazt a hasonlító függvényt lehessen használni, mint amit a qsort()-hoz is, a bsearch() úgy van megadva, hogy egy mintát is vár tőlünk: első paramétere egy olyan elemre mutató pointer kell legyen, amely egy mintául szolgál a kereséshez. Innen fogja tudni, hogy néz ki az az elem, amit keresnie kell. A hasonlító függvény pedig megmondja neki, hogy a tömbben előre, hátra kell mozogni, esetleg megtalálta az adott elemet. Ne feledjuk, bináris keresésről van szó, és ezért a tömbnek rendezettnek kell lennie!

A visszatérési érték is ahhoz hasonló, mint amit megszoktunk: NULL pointer akkor, ha nincs meg az elem. Ha megvan, akkor pedig a találatra mutat a pointer, amit kapunk.

15. Tömbök generikusan – a pointerek kezelése

Vajon lehet olyan függvényt írni, ami bármilyen tömbön működik?

double szamok[4] = {9.7, 3.4, 8.5, 1.2};
void *ptomb = (void *) szamok;       // így kapja a függvény :(

A gondunk az, hogy a void * esetén a pointer aritmetika nem működhet. Amikor az adatok tömbben vannak, a pointer típusának nem csak egy, hanem két szerepe is van. Azon felül, hogy ez ad információt arról, hogy az adott típust hogyan kell kezelni (nyilván más egy double és egy struct Konyv), a típus ismerete a tömbelemek címének kiszámításakor is fontos. Innen tudja a fordító azt, hogy mekkora egy tömbelem, vagyis a következő elemre lépéshez hány bájtot kell ugrani a memóriában. Ezt az információt mindig figyelembe veszi, amikor egy tömbelemet indexelünk, vagy a címét számítjuk.

Ha a tömb elejére mutató pointert void *-gá konvertáljuk, akkor nem csak a tömb tartalma válik ismeretlenné, hanem az is, hogy az egyes tömbelemek hol helyezkednek el. A tömb elejére mutató void * pointer nem ad semmilyen információt a tömbelemekről. A predikátum paramétere még csak-csak lehet void * (majd a törzsében megfelelő típusú pointerré konvertáljuk), de a tömb elemein nem tudunk lépkedni a típus ismerete nélkül. Ezt a problémát oldja meg az elemméret átadása a qsort() és társai esetén.


Egy char* típusú mutatót használva bájtonként lépkedhetünk:

char *bajtptr = (char *) ptomb;        // sizeof(char) = 1 miatt
for (int i = 0; i < 4; ++i) {          
    double *elem = (double *) bajtptr; // újra double
    printf("%g ", *elem);              
    bajtptr += sizeof(double);         // hány bájtot ugrunk?
}

Ahhoz, hogy a mutató aritmetika működjön, a mutatót típussal kell ellátni, hiszen ilyenkor az adott típus méretével szorozzuk a lépések számát. Ha char * típusúvá alakítjuk a pointert, akkor bájtonként tudunk lépni, mivel definíció szerint sizeof(char) = 1. Mivel ilyenkor a lépések bájtonként értendők, az elem címének kiszámításakor nem azt kell megadnunk, hogy hányadik valós számra, hanem hogy hányadik bájtra ugrunk. Ezért a ciklusban a mutatónkat nem egyesével, hanem sizeof(double) lépésekkel léptetjük: annyi bájtot kell mindig előremenni, ahány bájtból egy double áll. Az így kapott pointert pedig bátran visszakonvertálhatjuk double *-gá.

Egyes fordítók megengedik azt, hogy void * mutatókon használjunk pointer aritmetikát, de ez nem szabványos, úgyhogy inkább kerüljük az ilyesmit!

16. Tömbök generikusan – az elemek kezelése

A probléma tehát megoldható, mégpedig úgy, ha egy generikus tömböt feldolgozó algoritmusnak nem csak a tömb kezdőcímét (most void * formában!) és a tömb méretét adjuk át, hanem megmondjuk neki az egyes tömbelemek méretét is! Erre nincsen trükkös megoldás, egyszerűen közölni kell ezt a számot is az algoritmussal.

Egy függvény így lépdelhet végig egy void * tömbön:

void for_each_tomb(void *t, int db, size_t meret,
                   void (*muvelet)(void *))
{
    char *pbyte = (char *) t;  // sizeof(char) = 1 miatt
    for (int i = 0; i < db; ++i)
        muvelet((void *) (pbyte + i * meret));
}

Tehát ebben a char * csak azért szerepel, mert tudjuk, hogy sizeof(char) = 1, és a pointer aritmetika esetén bájtokkal dolgozunk.

A for_each_tomb() használata egy tömb minden elemének a kiírására:

void kiir_int(void *vp) {
    printf("%d ", *(int *) vp);
}

int tomb[] = { 68, 12, 125, 97, 56 };
for_each_tomb(tomb, 5, sizeof(int), kiir_int);

Visszalépő keresés (backtrack)

18. A nyolckirálynő-probléma

Feladat: tegyük egy sakktáblára 8 királynőt úgy, hogy ne üssék egymást!


Húzd az egeret a királynők fölé!

Lőjünk le néhány kérdést előre! Első kérdésünk lehet, hogy van-e megoldás. A válasz: van, de ez a rajzról is kiderül.

Második pedig, hogy hány megoldás van – összesen 92, amiből csak 12 lényegesen különböző van (a többi forgatással vagy tükrözéssel átvihető egymásba). A programunkban most az összeset megkeressük majd, nem csak a lényegesen különbözőeket; megszámláljuk és ki is rajzoljuk a megoldásokat.

A harmadik kérdésünk az, hogy a feladat általánosítható-e: 9×9-es sakktáblára 9 királynő, vagy 7×7-esre 7 darab. A válasz erre is az, hogy igen. A 2×2-es és 3×3-as esetben nincs megoldás, az összes többi esetben van. A lehetséges megoldások száma igen gyorsan nő a tábla méretével, nagyjából exponenciálisan. 27×27-es táblára

234 907 967 154 122 528

elrendezést találhatunk – lásd a Wikipédia Nyolckirálynő-probléma szócikkét. Ez egyébként a legnagyobb tábla, amire sikerült meghatároznia a megoldások számát egy csapatnak 2016 szeptemberében; nagyobb táblákra a megoldások száma ismeretlen.

19. A mi problémánk

Próbáljuk végig a lehetséges megoldásokat!

Ehhez el kell tárolnunk, hogy melyik királynő hol van. Definiáljunk egy pozíció nevű típust, és hozzuk létre belőle a 8 elemű tömböt!

typedef struct Pozicio {
    int x;
    int y;
} Pozicio;

Pozicio kiralynok[8];
Pozicio kiralynok[8] = {
    {1, 5},
    {7, 6},
    {5, 3},
    /* ... */
};

Hány megoldást kell végigpróbálnunk?

Hány megoldást kell végigpróbálnunk? Összesen 8×8 = 64 mezőre kell 8 királynőt raknunk. Vagyis 64 mezőből 8-at kell választanunk, ahol lesz királynő, a többi mezőkön nem. Ez ugyanaz a probléma matematikailag, mint a lottósorsolás, ahol 90 számból kell 5 különbözőt választani. A kombinatorikában ezt ismétlés nélküli kombinációnak nevezik. Ezek számát, „64 alatt a 8-at” jópár faktoriális kiszámításával lehet meghatározni:

         64!
C = ──────────── = 4 426 165 368
     8!·(64-8)!

100 000 próbálkozás / másodperc → 44 261 másodperc → fél nap.

Ha a gépünk százezer állást tud végigpróbálni másodpercenként, akkor is fél napig fog futni a programunk. Ezért másképp kell okoskodni, még akkor is, ha valójában a mai asztali számítógépek sokkal gyorsabbak ennél (kb. 1–10 millió próbálkozás / másodperc is belefér).

20. Variációk, permutációk

5
2
4
7
3
8
6
1

Mivel nem lehet egy sorban két királynő (ütnék egymást vízszintesen), ezért biztosak lehetünk abban, hogy minden sorban pontosan egy királynő lesz (8 sor, 8 királynő). Tehát lényegében elég csak azt megmondanunk a programunkban, hogy melyik sorban hol van a királynő. És ezt eltárolni is bőven elegendő; egy szimpla int poz[8] tömbre van csak szükségünk. Ha például poz[3] == 7, az azt jelenti, hogy a harmadik sor királynője a hetedik oszlopban van.

Észrevehetjük, hogy minden sorban pontosan egy királynő lesz:

int poz[8] = { ... };

Hogyan számítjuk ki így a végigpróbálandó esetek számát? A tömbelemek a 0...7 (1...8) értékeket vehetik fel. Ez 8n lehetőséget jelent, ahol n a tömbelemek száma; az pedig most szintén 8. A kombinatorikában ez az ún. ismétléses variáció.

V = 88 = 16 777 216

Vagyis 16,7 millió esetről van szó – az előzőek 260-adrészéről. Ez már sokkal inkább vállalhatónak tűnik, de még valamit észre kell vennünk.


Kétszer nem szerepelhet ugyanaz a szám:

int poz[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };

Ha a tömbben kétszer szerepelne ugyanaz a szám, az azt jelentené, hogy két különböző királynő ugyanabban az oszlopban van. Akkor viszont ütnék egymást függőlegesen, ezért ezeket az eseteket is kizárhatjuk. Vagyis valójában nem egy ismétléses variációt keresünk, hanem a fenti, 1-8 számokat tartalmazó tömb permutációit. Az tehát a kérdésünk, hogy ennek a tömbnek mely keverései, sorbaállításai adják a megoldást.

P = 8! = 40 320 !

A permutációk száma faktoriálissal határozható meg. A 8-elemű tömbünk lehetséges permutációinak száma 40320, vagyis az eredetileg kigondolt 4,4 milliárd megvizsgálandó esetet százezred részére tudtuk csökkenteteni! Ha ez még nem lenne elég, az így kialakított tömbben az ütési helyzetek vizsgálata is egyszerűbb. Mivel eleve minden sorba csak egy királynőt rakunk (a sor száma a tömbindex), és minden oszlopba is egyet (a tömbelemek egymástól különböző értékei), így már csak az átlós ütéseket kell vizsgálnunk majd, a függőlegeseket és a vízszinteseket nem.

21. Az ütések vizsgálata

Ütésben vannak, ha

Tehát csak az átlós ütésekkel kell foglalkozni. Átlós ütés akkor van, ha ugyanannyi sort kell lépni az egyik királynőtől a másikig, mint ahány oszlopot.

  • 45 fokos átlón: Δx = Δy
  • –45 fokos átlón: Δx = –Δy
  • A kettő együtt: |Δx| = |Δy|

Figyelembe kell vennünk, hogy ez mindkét irányú átlón megtörténhet. De ha vesszük az ugrások abszolút értékét (hogy mindegy legyen, fel vagy le, illetve jobbra vagy balra kell menni), akkor egyetlen egy egyenlettel leírhatjuk, mikor van ütközés: ha |x1–x2| = |y1–y2|.


A vizsgálatot ez a függvény fogja végezni:

bool kiralyno_oke(int *poz, int meret) {
    for (int i = 0; i < meret-1; ++i)
        for (int j = i+1; j < meret; ++j)
            if (abs(poz[i] - poz[j]) == abs(i - j))
                return false;
    return true;
}

Az adatszerkezetünkben a tömbindexek a sorok, a tömbértékek pedig az oszlopok. Vagyis ha bármely két tömbelemre igaz az, hogy az indexek különbsége megegyezik az értékek különbségével, akkor ütést találtunk, és az nem megoldás. Ha sehol nincs ilyen, akkor a tömb egy helyes megoldást tartalmaz.

22. A permutációk előállítása

Ha ezek megvannak, a megoldások előállítása a permutációk végigpörgetéséből, és azok vizsgálatából áll.

A permutációk előállítása a gyakorlaton megismert módon történik. A rekurzív algoritmus gondolatmenetét egy négyelemű tömbön szemléltetjük: {1, 2, 3, 4}. Ennek permutációi négy csoportba oszthatóak:

  • {1, x, x, x}, az egyessel,
  • {2, x, x, x}, a kettessel,
  • {3, x, x, x}, a hármassal,
  • és {4, x, x, x}, a négyessel kezdődő permutációk.

Az x-szel jelzett helyeken pedig a többi elem van. A többi elemet szintén sorba lehet rakni különféle módokon. Pl. a {1, x, x, x} esetben ezek a {2, 3, 4}, amelyek lehetséges sorrendezései: {2, 3, 4}, {2, 4, 3}, {3, 2, 4} stb. Ezek pedig előállíthatók rekurzívan, hiszen itt egy háromelemű tömb permutációit keressük.

void kiralyno_keres(int *poz, int meret, int honnan) {
    if (honnan == meret) {
        if (kiralyno_oke(poz, meret))
            kiralyno_kiir(poz, meret);
        return;
    }
    for (int i = honnan; i < meret; ++i) {
        csere(&poz[honnan], &poz[i]);
        kiralyno_keres(poz, meret, honnan+1);
        csere(&poz[honnan], &poz[i]);
    }
}

int main(void) {
    int poz[8] = {1, 2, 3, 4, 5, 6, 7, 8};
    kiralyno_keres(poz, 8, 0);
}

A permutációk előállításának módszere tehát az alábbi:

  • Menjünk végig a tömbön (ezt csinálja a ciklus). Tegyük a tömb minden elemét annak elejére, az eredeti elemet tegyük hátra (első csere).
  • Az így kapott tömbnek a fennmaradó részét permutáljuk (rekurzív hívás).
  • Végül az előrehozott elemet tegyük vissza a helyére (második csere), hogy egy újabb elemet vehessünk majd előre.

A rekurzív hívásban mindig csak a tömb fennmaradó részét kell permutálni, ezért a tömbméret mellett átveszünk egy honnan nevű paramétert is. A cserék innen indulnak, a rekurzív hívásban pedig honnan + 1 lesz a következő paraméter (a fennmaradó rész). Amikor eljutunk a honnan == meret értékig, akkor előállt egy permutáció, tehát ez a báziskritérium. Ekkor megvizsgáljuk a tömböt, és ha megoldása a nyolckirálynő-problémának, kirajzoljuk azt.

Az elkészült program letölthető innen: 8kiralyno_perm.c.

23. Feleslegesen kipróbált megoldások?

1
2
?
?
?
?
?
?

Valójában most is rengeteg feleslegesen kipróbált megoldás van:

int poz[8] = {1, 2, ???};
int poz[8] = {3, 2, ???};
int poz[8] = {1, ?, 3, ???};
int poz[8] = {6, ?, 4, ???};

A permutációs módszerrel rengeteg állást megvizsgáltunk hiábavalóan. Például az első királynőt leraktuk az első oszlopba, a másodikat a második oszlopba (mint a rajzon). Ezek biztosan ütik egymást, tehát a maradék hatot hiába próbáljuk meg elhelyezni bárhogyan, helytelen lesz a megoldásunk. A maradék 6 királynő elhelyezésére 6! = 720 lehetőség van, tehát ennyi állás vizsgálatát kihagyhattuk volna. És nem ez az egyetlen ilyen eset; a fenti tömbkezdemények mind olyan elhelyezéseket mutatnak, ahol a kérdőjelek helyére bármi is kerül, biztosan rossz a megoldás.


Tehát a nyolckirálynő-problémában:

  • Részmegoldások vizsgálhatók (első n sor).
  • Ezek vizsgálatával sok lehetőség kizárható.

Vannak olyan feladványok, ahol egy lehetséges megoldást egyben kell látnunk, és csak akkor tudjuk eldönteni, hogy helyes-e. A nyolckirálynő-probléma azonban nem ilyen. Itt egy részmegoldást is tudunk vizsgálni. Vagyis egy még nem teljesen kitöltött táblára kétféle állítást tehetünk, a) ez még lehet jó, próbáljuk meg kitölteni az alját, b) ez már biztosan nem lesz jó. Vagyis hasznos megvizsgálnunk a részmegoldást is, mert az ki fog zárni egy csomó esetet.

24. Nyolckirálynő-probléma: új algoritmus

Az algoritmus működése:

  • Tekintsük a következő üres sort.
  • Próbáljuk végig az összes oszlopot a sorban.
    • Tegyük a táblára a királynőt.
    • Ha üti az eddigieket, vegyük le.
    • Ha nem üti, akkor:
      • Próbáljuk elhelyezni a többit.
      • Végül vegyük le, a többi oszlopot is próbáljuk.
  • Ha közben megtelik a tábla, megoldást találtunk.

A kiemelt műveleteket („ha üti, vegyük le”) nevezzük visszalépésnek, ezért az algoritmus neve: visszalépő keresés (backtracking search).

25. Az ütések vizsgálata: csak az n-edik

Az új algoritmushoz egy egyszerűbb tesztelőfüggvény tartozik, mint az előzőhöz. Mivel most egyesével rakjuk majd a királynőket, mindig csak a legutóbbit kell megnézni, hogy jó-e, nem üti-e a többit. Az összes előzőre nem figyelünk: úgy jutunk mindig ide, hogy azok már ellenőrizve vannak. A függvény paramétere a tömb mellett a sornak a száma, amelyik királynőt ellenőrizni kell.

Ütésben vannak, ha

  • Azonos oszlopban vannak: x1 = x2
  • Azonos átlón vannak: |dx| = |dy|

bool kiralyno_nedik_oke(int *poz, int n) {
    for (int i = 0; i < n; ++i) {
        if (poz[i] == poz[n]
            || abs(poz[i] - poz[n]) == abs(i - n))
            return false;
    }
    return true;
}

Ügyelni kell arra, hogy most nem csak az átlót kell vizsgálni, hanem azt is, hogy az új királynő nem került-e valamelyikkel azonos oszlopba: poz[i] == poz[n]. A tömbbe ugyanis most nem permutációk kerülnek, hanem minden sorban végigpróbáljuk az összes oszlopot, és oszlopok szerinti ütés is előfordulhat. De ez csak egy újabb feltétel; az algoritmus még így is egyszerűbb, egyetlen egy ciklus vizsgálja az új királynő sora előtti sorokat.

26. Algoritmus visszalépő kereséssel (félkész)

Az alábbi függvény valósítja meg a visszalépő keresést a probléma megoldására. Ez nem a klasszikus megvalósítás, még később finomítjuk majd, de előbb lássuk a működését!

void kiralyno_keres(int *poz, int meret, int n) {
    if (n == meret) {
        kiralyno_kiir(poz, meret);
        return;
    }
    for (int uj = 1; uj <= meret; ++uj) {
        poz[n] = uj;
        if (!kiralyno_nedik_oke(poz, n)) {
            poz[n] = 0;    // visszalépés
            continue;
        }
        kiralyno_keres(poz, meret, n+1);
        poz[n] = 0;
    }
}

A függvénynek most is paramétere a kitöltendő tömb mérete. Paramétere továbbá az n, amely azt mutatja, hogy épp hányadik sorban fogunk megoldást keresni.

A ciklus az, amely az adott sorban megpróbálja elhelyezni az új királynőt. Ez végigpróbálja 1-től 8-ig a lehetséges értékeket, amelyek abba a tömbelembe kerülhetnek, vagyis a lehetséges oszlopokat. Az a hipotézis, hogy az új oszlop a királynő számára jó lesz, ezért be is teszi oda: poz[n] = uj. Utána pedig megnézi, hogy a hipotézis jó-e. A kiralyno_nedik_oke() függvénynek ezt az egy új királynőt kell néznie, mivel az összes eddigi biztosan nem üti egymást. Ha kiderül, hogy ez ütésben van az eddigiekkel, akkor kiveszi a tömbből, és próbálkozik tovább. Ha rendben van, akkor pedig a rekurzív hívással megpróbálja elhelyezni a többit.

Valójában egyébként a poz[n] = 0 értékadások feleslegesek, csak az érthetőség kedvéért szerepelnek. Egyrészt mert a következő iteráció úgyis felülírja azt az elemet, másrészt pedig a vizsgáló függvény úgyis csak az első n elemmel foglalkozik – tehát ha nem írjuk felül újra 0-val az adott elemet, az sem baj.

27. Permutáló algoritmus visszalépéssel

Az előbbi magyarázatban a visszalépő keresés tisztázása kedvéért szerepelt egy egyszerűsítés: ismétléses variációkat vizsgáltunk, nem pedig permutációkat. Vagyis nem az {1, 2, 3, 4, 5, 6, 7, 8} tömböt permutáltuk, hanem minden sorban az összes oszlopba próbáltunk királynőt tenni.

Valójában a permutációkat előállító algoritmus beilleszthető a visszalépő keresésbe. Vegyük szemügyre csak a permutációkat előállító kódot egy pillanatra! Ez így fest:

void permutacio(int *poz, int meret, int n) {
    if (n == meret)
        return;

    for (int i = n; i < meret; ++i) {
        csere(&poz[n], &poz[i]);
        permutacio(poz, meret, n+1);
        csere(&poz[n], &poz[i]);
    }
}

Ebben a cserékkel minden tömbelem előre jön, utána a rekurzióban csak a tömb fennmaradó részét permutáljuk. A nyolckirálynő-probléma és a visszalépő keresés esetében ez éppen jó nekünk: a cserével előre hozott szám (oszlop index) lesz a vizsgálandó elem a báziskritériumban. Ha az rendben van, akkor a tömb végét permutáljuk utána csak, vagyis csak ott rendezgetjük a királynőket; az eddig elhelyezettek közötti ütközéseket azok már nem fogják módosítani.

void kiralyno_keres(int *poz, int meret, int n) {
    if (!kiralyno_nedik_oke(poz, n-1)) {   // !
        return;
    }
    if (n == meret) {
        kiralyno_kiir(poz, meret);
        return;
    }
    
    for (int i = n; i < meret; ++i) {
        csere(&poz[n], &poz[i]);
        kiralyno_keres(poz, meret, n+1);
        csere(&poz[n], &poz[i]);
    }
}

A végleges megoldásunk így néz ki. Valójában ez alig különbözik az első, permutáló megoldástól. Az egyetlen különbség abban rejlik, hogy ez részmegoldásokat is megvizsgál, és azokat nagyon hamar visszautasítja, ha nem jók. Ezt mutatja a jelölt rész. A teljes program letölthető innen: 8kiralyno_bt_perm.c.

28. Hatékonyság: permutáló és visszalépő

Az alábbi táblázat azt mutatja, hogy táblaméret függvényében hány pályaállást kell megvizsgálni akkor, ha a permutáló módszert, illetve a visszalépő keresést alkalmazzuk a probléma megoldására.

méretpermutációvalvisszalépővelgyorsulás
84032055097,3×
93628802401215,1×
10362880011000533,0×
113991680054635873,1×
124790016002915741164,3×
13622702080016469570378,1×
148717829120099280505878,1×

Látható, hogy a visszalépő keresés sokkal gyorsabb; a hibás részmegoldások (és azok befejezéseinek) eliminálásával a gyorsulás a táblamérettel meredeken nő. 14×14-es tábla megoldásainak keresésekor már majdnem 900-ad részére csökken a megvizsgált esetek száma.

Ez az algoritmus azért is sokkal gyorsabb, mert az egyes esetek vizsgálata egyszerűbb. Míg a permutáló algoritmusnál teljes játékállásokat kellett vizsgálni (minden királynőt mindegyikkel párba állítva), itt egy hipotézis vizsgálatához elég csak az újonnan felrakottat figyelembe venni. Egy i5-8250U processzorral rendelkező gépen a 14×14-es pályára a megoldások megkeresése mindössze 1,6 másodpercig tart.

29. A visszalépő keresés általános alakja

Lent látható a visszalépő keresés általános megfogalmazása pszeudokód formájában. Ez annyiban különbözik az előbb látott nyolckirálynő-megoldótól, hogy itt a hipotézis helyességének a vizsgálata is báziskritériumként szerepel. Vagyis a ciklus feltétel nélkül elindítja a rekurziót a kiegészített megoldás vizsgálatára; aztán a rekurzív hívás dönti el, hogy elfogadja vagy visszautasítja azt a megoldást, amit éppen lát.

függvény: visszalépő_keresés(megoldás)

    ha a (rész)megoldás hibás báziskritériumok
        vissza
    ha megoldás teljes (és elfogadható)
        kiírás
        vissza

    ciklus a következő részmegoldásokkal egyszerűsítés
        megoldás kiegészítése
        visszalépő_keresés(megoldás)

30. Visszalépő keresés: csak egy megoldás

A fenti algoritmus az összes megoldást kilistázza. De a visszalépő keresés könnyedén módosítható olyan feladatok megoldására, ahol csak egy megoldást keresünk, vagy esetleg meg akarunk állni az első egynéhány megoldás megtalálása után.

Ha egy megoldás keresése a feladat, akkor ahhoz bevezetünk a függvénynek egy visszatérési értéket. Ez fogja azt mutatni, sikerült-e megoldást találni vagy nem.

bool kiralyno_keres(int *poz, int meret, int n) {
    if (!kiralyno_nedik_oke(poz, n-1))
        return false;
    if (n == meret)
        return true;

    for (int i = n; i < meret; ++i) {
        csere(&poz[n], &poz[i]);
        if (kiralyno_keres(poz, meret, n+1))
            return true;
        csere(&poz[n], &poz[i]);
    }
    return false;
}
int poz[8] = {1, 2, 3, 4, 5, 6, 7, 8};
bool talalt = kiralyno_keres(poz, 8, 0);
if (talalt)
    kiralyno_kiir(poz, 8);

Ha true értéket kapunk a függvényből, akkor sikerült egy megoldást találni, és azt betette a tömbbe. Ha false, akkor nem volt megoldás, és a tömbben nincs hasznos adat.

A függvény belsejében elő kell állítani ezt az értéket. Egyrészt a báziskritériumoknál: ha rossz helyre került a királynő, akkor false, ha tele a tábla, akkor jó helyen vannak, és true.

Másrészt pedig magában a keresésben. A leglényegesebb rész az, ahol a rekurzív hívás van. Ha az igazzal tér vissza, azt azt jelenti, hogy a tömb egy teljes megoldást tartalmaz; ilyenkor a hívó is visszatér igazzal. Ez az, ami megszakítja a keresést az első megoldás megtalálása után, ugyanis ilyenkor megáll egyrészt a ciklus is, másrészt pedig a rekurzív hívók is mind igazzal fognak visszatérni. A függvény legalján hamis értékkel kell visszatérni. Ugyanis ha lefutott a ciklus teljes egészében, az azt jelenti, hogy a szóba jövő oszlopok közül egyik se vezetett megoldáshoz.

Így működik a rekurzió kapcsán bemutatott labirintus megoldó is. Ott tudjuk előre, hogy egyetlen egy megoldás van, és azt kell megtalálni; zsákutca esetén pedig visszajönni.

31. Visszalépő keresés: alkalmazások

A visszalépő keresés alkalmazásai:

  • Rejtvények: nyolc királynő, sudoku, keresztrejtvény, labirintus
  • Nyelvi elemzés (fordítóban)
  • Optimalizálási feladatok, pl. hátizsák-probléma, pénzosztás

Lássunk néhány példát a visszalépő keresés alkalmazására!

Nyelvi elemzés. A fordítóprogramnak a megkapott forráskódot elemeznie kell, és az elemzés közben könnyen zsákutcába futhat. Például az x = (double) y; kifejezés értelmezésekor rá kell jönnie, hogy a zárójel mit jelent. Ha elindul abba az irányba, hogy precedenciamódosító zárójelet feltételez (mint pl. az 5 + (2*3) kifejezésben), akkor ellentmondásra jut, mert a zárójelben nem kifejezés van. Ezért visszalép, és megpróbálkozik mással: cast operátornak feltételezve a zárójelet, kiderül hogy a teljes kifejezés értelmezhető.

Optimalizálási feladatok. Ezek közül a legismertebb a hátizsák-probléma, amit a rajz is szemléltet. Adott egy hátizsák, amelynek a teherbírása véges. Adott egy csomó tárgy, amelyeknek ismerjük az értékét és a súlyát. Kérdés, mely tárgyakat kell kiválasztanunk, hogy a legnagyobb összértéket állítsuk össze, figyelembe véve a hátizsák teherbírását. A rajz példáját tekintve, a két legértékesebb tárggyal 10+4 = 14 dolláros csomagot állíthatnánk össze, ezeknek a súlya azonban 12+4 = 16 kg, ami túllépi a limitet. Valamelyiket el kell hagynunk, és könnyebbet keresni helyette.

Szintén visszalépő kereséssel oldható meg helyesen egy bankautomata feladata is, amelynek ki kell adnia egy adott összeget, figyelembe véve, hogy milyen címletekből mennyi áll rendelkezésre. Ha a bankautomata rekeszei ezeket a bankjegyeket tartalmazzák:

címletdarabszám
5000137
2000275
10000

Akkor egy mohó algoritmus, amely a legnagyobb címletekkel próbálkozik a 6000 forint kifizetéséhez nem tudna megoldást találni. Elakadna ott, hogy ad egy 5000-est, és utána 1000-esből meg nincsen. Viszont ezen a ponton visszalépve, úgy döntve, hogy mégsem ad ki 5000-est, rájöhet, hogy a 3×2000 megoldása a feladatnak.