Gyakorlat, 8. hét: rekurzió

Czirkos Zoltán · 2016.08.28.

Rekurzív algoritmusok: rekurzió tervezése, triviális esetek és visszavezetések.

A rekurzióhoz

Rekurzív algoritmusoknál két dolgot kell meggondolnunk:

  • A triviális eseteket, amelyeknél a megoldás magától értetődik. (Pl. üres sztring hossza nulla.)
  • Nem triviális esetben azt, hogy hogyan tudjuk a kapott problémát visszavezetni egyszerűbb problémákra. (Pl. nem üres sztring hossza 1 + a sztring hossza a második betűtől kezdve.)

Az előbbi a báziskritérium, az utóbbi pedig az egyszerűsítési lépés a rekurzióban, amellyel minden rekurzív függvényhívásnál a báziskritérium felé haladunk. Keressük meg ezeket az alábbi problémáknál!

Felkészülés a gyakorlatra:

1. Rekurzió bemelegítő

Mi a különbség az alábbi két függvény között?

void sztringet_kiir(char *szoveg) {
    if (szoveg[0] == '\0')
        return;
    putchar(szoveg[0]);
    printf("%s", szoveg + 1);
}
void sztringet_kiir(char *szoveg) {
    if (szoveg[0] == '\0')
        return;
    putchar(szoveg[0]);
    sztringet_kiir(szoveg + 1);
}

Megoldás

Semmi.

2. Járda kövezése

Hányféleképpen lehet egy adott hosszúságú járdát kikövezni 1 és 2 méter hosszúságú járdalapokkal? Például ha 3 méteres a járda, a lehetőségek: 1+1+1, 1+2, 2+1, tehát összesen 3.

Megoldás

A megoldás alapötlete a következő. Kétféle járdalapunk van (az 1 és a 2 méter hosszú), ami azt jelenti, hogy induláskor két lehetőségünk van: vagy egy 1 méteressel, vagy egy 2 méteressel kezdünk. Ha összesen 10 métert kell haladni, az első esetben már csak 9, a második esetben pedig már csak 8 métert kell majd haladnunk.

A 9 méteres és a 8 méteres szakasz kövezése is megoldható valahányféleképpen. A 10 méter hosszú járdához a megoldások számát a kettő összege fogja adni.

A rekurzióban az egyszerűsítési lépést így ez a kódrészlet adja:

int jarda(int hossz) {
    /* ... */
    return jarda(hossz - 1) + jarda(hossz - 2);
}

Már csak alkalmas báziskritériumok kellenek. Ezek:

  • Ha 0 hosszúságú járdánk van, az egy (vigyázat, nem nulla!) módon kövezhető csak: úgy, hogy nem csinálunk semmit.
  • A fenti függvény láthatóak meghívja magát negatív hosszakra is, negatív hosszúságú járda viszont nem létezhet, ezért olyankor 0 megoldás van.
#include <stdio.h>

/**
 * Visszaadja, hányféleképpen lehet lekövezni egy
 * <hossz> méret hosszú járdát 1 és 2 méteres kövekkel.
 */
int jarda(int hossz) {
    /* negatív hossz nem létezik, úgyhogy 0 megoldás van.
     * az egyszerűsítésnél lehet, hogy fog ilyen hívódni! */
    if (hossz < 0)
        return 0;
    /* 0 hosszú járdát egyféleképp: úgy, hogy nem csinálunk semmit.
     * ilyen is adódhat ki az egyszerűsítésnél */
    if (hossz == 0)
        return 1;

    /* amúgy pedig vagy lerakunk egy 1 hosszút,
     * vagy egy 2 hosszút. és utána ahányféleképp a maradékot. */
    return jarda(hossz - 1) + jarda(hossz - 2);
}

int main() {
    int h;
    printf("Hossz?\n");
    scanf("%d", &h);

    printf("%d lehetőség.\n", jarda(h));
}

3. Alakzat kitöltése

Adott egy két dimenziós tömb, amelyik egy képet reprezentál. A képen egy adott színnel el van kerítve egy terület – vagyis meg van rajzolva egy alakzat. Színezzük ki ennek az alakzatnak a belsejét! Az alakzat lehet konkáv is, abban az esetben is be kell menni minden zugba!

char z4qqq[20][32] = {
    "                               ",
    "            xx   xx            ",
    "       xxxx x xxx x xxxx       ",
    "      xx  x x     x x  xx      ",
    "    xxx  xx x     x xx  xxx    ",
    "  xxx    x  x     x  x    xxx  ",
    "  x      x  x     x  x      x  ",
    " xx       xx       xx       xx ",
    " x                           x ",
    " x                           x ",
    " x                           x ",
    " x                           x ",
    " x                           x ",
    " xx    xx             xx    xx ",
    "  x   x  x xx     xx x  x   x  ",
    "  xxx  x x x x   x x x x  xxx  ",
    "    xx x xxx xx xx xxx x xx    ",
    "     xxx      x x      xxx     ",
    "              xxx              ",
    "                               "
};

Megoldás

A rekurzió nélkül lehetetlennek tűnő feladat rekurzív megoldása végtelenül egyszerű. A függvény először megvizsgálja, hogy olyan pozíciót kapott-e, ahova szabad lépni, és amit ki kell festeni. Ha nem szóköz (kifestendő képpont) van az adott helyen, vagy talán olyan pozícióról van szó, ami kilóg a képről, akkor egyből vissza is tér. Ha viszont kifestendő a pont, akkor kifesti, és kifesti a szomszédait is. A szomszédoknál ugyanez a feladat: az aktuális pontot kifesteni, és mind a négy irányba megpróbálni menni. Ha a festés ilyen módon végül egy zsákutcában elakad, a függvények visszatérnek – és a próbálkozás megy tovább a másik három lehetséges irányba. Zsákutca pedig a saját maga által kifestett pontok miatt is keletkezhet, hiszen onnantól kezdve, hogy egy pontot kifest az algoritmus, az ugyanolyan falnak számít, mint az eredeti alakzat körvonalai.


A kifestő működése. A videóban minden függvényhívás elején pirosra festi a program az adott helyet; és miután az összes irányból visszatértek a hívott függvények, csak akkor kékre. Ezen is, és a bejelölt útvonalon is látszik az, hogy melyek a befejezetlen, nem teljesen lefutott függvénytörzsek.
#include <stdio.h >

void kifest(char kep[20][32], int y, int x) {
    if (y < 0 || x < 0 || y >= 20 || x >= 31)
        return;
    if (kep[y][x] != ' ')
        return;
    kep[y][x] = '.';
    kifest(kep, y - 1, x);
    kifest(kep, y + 1, x);
    kifest(kep, y, x - 1);
    kifest(kep, y, x + 1);
}

int main(void) {
    /* IDE KELL BERAKNI A RAJZOT */

    kifest(z4qqq, 10, 10);
    int y;
    for (y = 0; y < 20; ++y)
        puts(z4qqq[y]);

    return 0;
}

4. Permutáció

Írjuk ki egy szónak (karaktersorozatnak) az összes permutációját! Pl. abc permutációi: abc acb bac bca cab cba.

Megoldás

A megoldás lényege, hogy egy-egy betűpárt megcserél, és a fennmaradó részeket is permutálja. A start változóban azt kapja a függvény, hogy hányadik karaktertől kezdve kell kezdeni a permutálást. Ha ez megegyezik a sztring hosszával, akkor már nem permutál (hiszen már nincs mit), hanem egyszerűen kiírja az aktuális állapotot. Ez a báziskritérium, így lesz vége a rekurzió „mélységének” – a rekurziónál mindig kell lennie egy feltételnek, amikor többé már nem hívja meg magát a függvény. Minden hívásnál közelít efelé a bázis felé, hiszen mindig egyre rövidebb fennmaradó sztringrészletet permutál.

Tegyük fel, hogy kezdetben a sztring „abcd”. Ennek úgy néznek ki a permutációi, hogy azok kezdődhetnek a-val, b-vel, c-vel és d-vel. Az a-val kezdődőek: „abcd”, „abdc”, „acbd”, … ezek végülis egy fix „a”, és utána a „bcd” sztring permutációi, az összes lehetséges sorrendben. A b-vel kezdődőek: „bacd”, „badc”, „bcad”, …, vagyis egy „b” betű, és az „acd” sztring permutációi. Itt van ebben a rekurzió: az „abcd” sztring permutációi azok kezdődnek az „abcd” sztring valamelyik (egyik) karakterével, és utána fennmaradó karakterek (de már csak három betűs sztring) permutációi kellenek.

A permutáló függvény ezt úgy valósítja meg, hogy a kapott sztring mindegyik karakterét berakja az első helyre (vagyis mindegyik karakterét megcseréli az elsővel), és utána képezi a fennmaradó rész permutációit. Ha nincs fennmaradó rész, akkor pedig kiírja az addigra már összekevert sztringet. Pl. a kiindulási sztring „abcd”, akkor:

  • először az a[bcd]-ket írja ki (csere nélkül)
  • utána meg cserékkel: b[acd] (i=1), c[abd] (i=2), d[abc] (i=3), és mindenhol a [] részre rekurzívan hívódik.

Az összes hívás az első mélységben így, ahol a [] jelenti a további rekurzív hívásokat:

  • a[bcd] (nincs csere)
  • b[acd] (a↔b)
  • c[bad] (a↔c)
  • d[bca] (a↔d)

A rekurzió itt azért is jó, hogy miután visszajöttünk a fennmaradó rész permutációinak képzéséből, akkor emlékezzünk rá, hogy melyik karaktereket kell visszacserélni (ez lokális változó, eltárolódik a veremben).

#include <stdio.h>
#include <string.h>

/* megcsereli az adott indexu karaktereket */
void betucserel(char* str, int a, int b) {
    char t = str[a];
    str[a] = str[b];
    str[b] = t;
}

void permutal(char* str, int start) {
    int hossz = strlen(str);

    if (start == hossz-1) {
        /* ha mar nincs mit permutalni */
        printf("%s ", str);    
    } else {
        /* permutaljuk a string hatralevo reszet, tovabba minden
         * karaktert megcserelunk a startadikkal, es ugy is
         * permutalunk. az elso esetet, amikor i=start lenne, kulon
         * is lehet hivni, mivel olyankor nem kell csere. */
        permutal(str, start+1);

        int i;
        for (i = start+1; i < hossz; ++i) {
            betucserel(str, start, i);    /* csere */
            permutal(str, start+1);
            betucserel(str, start, i);    /* visszacsere */
        }
    }
}

int main(void) {
    char s[] = "abcd";
    permutal(s, 0);
    printf("\n");

    return 0;
}

A fenti megoldás nem veszi figyelembe azt, ha egyforma betűk vannak a sztringben, és azokat is cseréli. Pl. az „abba” sztringnek többször is megjelennek ugyanazon permutációi. Ehhez a cserék előtt meg kell vizsgálnunk azt, hogy a cserélendő karakter szerepelt-e már a cserések között. Mert ha igen, akkor azt a lépést nem kell újra elvégezni, hanem ki kell hagyni:

permutal(str, start + 1);

for (i = start + 1; i < hossz; ++i) {
    bool kell_csere = true;
    int k;
    for (k = start; k < i; ++k)         /* volt mar ez a betu? */
        if (str[k] == str[i])
            kell_csere = false;

    if (kell_csere) {
        betucserel(str, start, i);    /* csere */
        permutal(str, start + 1);
        betucserel(str, start, i);    /* visszacsere */
    }
}

5. További feladatok – Járda II.

Hogyan kell módosítani a járdás programot, ha 3 egység hosszú lapunk is van? És ha paraméterként kapjuk, hogy hányféle lap van? (Pl. 5 → 1, 2, 3, 4, 5 hosszú lapok vannak.)

Megoldás

int jarda(int hossz, int hanyfele) {
    /* ... */
    
    int osszeg = 0;
    int i;
    for (i = 1; i <= hanyfele; ++i)
        osszeg += jarda(hossz - i, hanyfele);
    return osszeg;
}

6. További feladatok – Pénzváltás

Adott egy zsák 5, 10, 20 és 50 forintos érménk. Hányféleképpen lehet ezekkel kifizetni 100 forintot?

(A feladatnak egy nehezített változata megtalálható a feladatgyűjteményben.)

Megoldás

A probléma könnyen megoldható rekurzívan. Tekintsünk pl. egy 20 forintost! Két lehetőségünk van: ha a 20 forintos része a megoldásnak (vagyis adunk egy 20-ast), akkor a maradék 100-20=80 forintot még valahányféleképpen (x) ki lehet fizetni. A másik lehetőség, ha azt mondjuk, hogy nem adunk 20-ast, és a 100 forint kifizetését a többi érmével oldjuk meg (y lehetőség). A megoldás ezek összege: x+y.

Így közeledünk a rekurzióban a báziskritérium felé: vagy az összeg csökken, vagy a felhasználható érmefajtákat csökkentjük. Figyelembe kell még vennünk három extrém esetet. Ezek lesznek a báziskritériumok:

  1. Ha 0 forintot kell kifizetnünk, azt egyféleképpen tehetjük: nem adunk pénzt.
  2. Ha 0-nál többet kell fizetnünk, de nincs semmilyen fajta érménk, akkor nulla lehetőség.
  3. Ha negatív összeget kell fizetnünk, azt sem tudjuk megtenni: nulla lehetőség.

Az utóbbi feltételt az algoritmus egyszerűségéhez használjuk ki. Jelentése: ha 5 forintot kell kifizetni, és megpróbáljuk egy 20-assal, akkor még -15 forintot kellene – de ez nem megoldás.

#include <stdio.h>
#include <stdlib.h>

int penzvalto(int mennyit, int *fajtak, int hanyadiktol) {
    /* báziskritérium */
    if (mennyit == 0) // 1. pont
        return 1;
    if (fajtak[hanyadiktol] == -1 || mennyit < 0) // 2, 3. pont
        return 0;

    /* egyszerűsítés */
    return penzvalto(mennyit-fajtak[hanyadiktol], fajtak, hanyadiktol)
           + penzvalto(mennyit, fajtak, hanyadiktol+1);
}

int main(void) {
    int fajtak[] = {5, 10, 20, 50, -1};

    printf("Összesen: %d lehetőség\n", penzvalto(100, fajtak, 0));

    return 0;
}

Az érmék névértékeit egy tömbbe tettük, amely egy lezáró -1-et is tartalmaz (a római számos példákhoz hasonlóan). A függvény ezt a tömböt kapja, és egy indexet, hogy hányadik elemtől kell a tömböt figyelembe vegye. Az utolsó sorában ezt növeli, és úgy hívja meg magát – így maradnak ki a tömb eleji érmék a rekurzív hívásban, és így fogy el végül a tömb, amikor fajtak[hanyadiktol]==-1. Ez megoldható lenne pointer aritmetikával is: fajtak+1 a tömb belsejébe mutat (a hátsó részére), és így fogyhat el a tömb.