Prednáška 10

Oznamy

• Zajtrajšia rozcvička bude z dnešnej prednášky
  • Tento týždeň iba 3 príklady na cvičeniach, spolu 6 bodov
• V piatky 1.11. a 8.11. nebudú doplnkové cvičenia. Namiesto toho budú náhradné doplnkové cvičenia v pondelky 4. a 11.11. o 11:30 v miestnosti M217, kde ste vítaní, ak máte nejaké otázky alebo si chcete samostatne riešiť príklady.
• DÚ2 je zverejnená, odovzdávajte do pondelka 11.11. 22:00
• Druhá písomka bude v stredu 21.11. o 18:10 v posluchárni A, tretia 11.12.
• Dnes po prednáške vzorové riešenia prvej písomky

Opakovanie rekurzie

• Rekurentná definícia: určitý objekt definujeme pomocou menších objektov toho istého typu
  • Napr. Fibonacciho čísla F(n) = F(n-1) + F(n-2)
  • Nezabudnime na triviálne prípady, napr. F(0)=F(1)=1

• Rekurentné definície vieme často priamočiaro zapísať do rekurzívnych funkcií (aj keď môžu byť pomalé)

int fib(int n){
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

• V rekurzívnej funkcii riešime problém pomocou menších podproblémov toho istého typu
  • Napríklad aby sme našli číslo x v utriedenom poli medzi indexami left a right, potrebujeme ho porovnať so stredným prvkom tohoto intervalu a potom riešiť tú istú úlohu pre menší interval
  • Aj keď sme pôvodne chceli hľadať prvok v celom poli, úlohu rozšírime o parametre left a right, aby sa dala spraviť rekurzia

int find(int a[], int left, int right, int x) {
    if (left > right) {
        return -1;
    }
    int index = (left + right) / 2;
    if (a[index] == x) {
        return index;
    }
    else if (a[index] < x) {
        return find(a, index+1, right, x);
    }
    else {
        return find(a, left, index - 1, x);
    }
}

Zásobník volaní

Druhý pohľad na rekurziu je dynamický: môžeme simulovať, čo sa v programe deje so zásobníkom volaní (call stack)

• Skúsme napríklad odsimulovať, čo sa deje ak vo funkcii main zavoláme fib(3)
• Kvôli prehľadnosti si fib rozpíšeme na viac riadkov:

#include <iostream>
using namespace std;

int fib(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        int a = fib(n - 1); // riadok (A)
        int b = fib(n - 2); // riadok (B)
        return a+b;
    }
}

int main(void) {
    int x = fib(3);    // riadok (C)
    cout << x << endl; 
}

Tu je priebeh programu (obsah zásobníka)

(1)          (2)                      (3)

                                       fib n=2
              fib n=3                  fib n=3, a=?, b=?, riadok A
main, x=?     main, x=?, riadok C      main, x=?, riadok C

(4)                             (5)
 
fib n=1                         
fib n=2, a=?, b=?, riadok A     fib n=2, a=1, b=?, riadok A
fib n=3, a=?, b=?, riadok A     fib n=3, a=?, b=?, riadok A
main, x=?, riadok C             main, x=?, riadok C             


(6)                             (7)
 
fib n=0                         
fib n=2, a=1, b=?, riadok B     fib n=2, a=1, b=0, riadok B
fib n=3, a=?, b=?, riadok A     fib n=3, a=?, b=?, riadok A
main, x=?, riadok C             main, x=?, riadok C             


(8)                             (9)

                                fib n=1
fib n=3, a=1, b=?, riadok A     fib n=3, a=1, b=?, riadok B 
main, x=?, riadok C             main, x=?, riadok C                 


(10)                            (11)

fib n=3, a=1, b=1, riadok B     
main, x=?, riadok C             main, x=2, riadok C 

Pozor, priamočiary rekurzívny zápis výpočtu Fibonacciho čísel je neefektívny, lebo výpočet Fibonacciho čísel sa opakuje

• Napr. pre n=4 počítame fib(2) dvakrát, pre n=6 päťkrát a pre n=20 až 4181-krát

Postupnosť volaní počas výpočtu vieme znázorniť aj stromovým diagramom:

Ako by sme zistili, čo robí rekurzívna funkcia, napríklad takáto obmena Fibonacciho postupnosti?

int f(int n) {
    if (n <= 2) return 1;
    else return f(n-1) + f(n-3);
}

Vypisovanie variácií s opakovaním

Vypíšte všetky trojice cifier, pričom každá cifra je z množiny {0..n-1} a cifry sa môžu opakovať (variácie 3-tej triedy z n prvkov). Napr. pre n=2:

000
001
010
011
100
101
110
111

Veľmi jednoduchý program s troma cyklami:

#include <iostream>
using namespace std;

int main(void) {
    int n;
    cin >> n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            for(int k=0; k<n; k++) {
                cout << i << j << k << endl;
            }
        }
    }
}

Rekurzívne riešenie pre všeobecné k

Čo ak chceme k-tice pre všeobecné k? Využijeme rekurziu.

• Variácie k-tej triedy vieme rozdeliť na n skupín podľa prvého prvku:
  • tie čo začínajú na 0, tie čo začínajú na 1, ..., tie čo začínajú na n-1.
• V každej skupine ak odoberieme prvý prvok, dostaneme variácie triedy k-1

#include <iostream>
using namespace std;

void vypis(int a[], int k) {
    for (int i = 0; i < k; i++) {
        cout << a[i];
    }
    cout << endl;
}

void generuj(int a[], int i, int k, int n) {
    /* v poli a dlzky k mame prvych i cifier,
     * chceme vygenerovat vsetky moznosti
     * poslednych k-i cifier */
    if (i == k) {
        vypis(a, k);
    } else {
        for (int x = 0; x < n; x++) {
            a[i] = x;
            generuj(a, i + 1, k, n);
        }
    }
}

int main(void) {
    const int maxK = 100;
    int a[maxK];
    int k, n;
    cout << "Zadajte k a n: ";
    cin >> k >> n;
    generuj(a, 0, k, n);
}

Ďalšie rozšírenia

• Čo ak chceme všetky k-tice písmen A-Z?
• Čo ak chceme všetky DNA reťazce dĺžky k (DNA pozostáva z "písmen" A,C,G,T)?

// pouzi n=26
void vypis(int a[], int k) {
    for (int i = 0; i < k; i++) {
        char c = 'A'+a[i];
        cout << c;
    }
    cout << endl;
}

// pouzi n=4
void vypis(int a[], int k) {
    char abeceda[5] = "ACGT";
    for (int i = 0; i < k; i++) {
        cout << abeceda[a[i]];
    }
    cout << endl;
}

Cvičenia

• Ako by sme vypisovali všetky k-ciferné hexadecimálne čísla (šestnástková sústava), kde používame cifry 0-9 a písmená A-F?
• Ako by sme vypisovali všetky k-tice písmen v opačnom poradí, od ZZZ po AAA?

Variácie bez opakovania

Teraz chceme vypísať všetky k-tice cifier z množiny {0,..,n-1}, v ktorých sa žiaden prvok neopakuje (pre k=n dostávame permutácie)

Príklad pre k=3, n=3

012
021
102
120
201
210

Skúšanie všetkých možností

• Jednoduchá možnosť: použijeme predchádzajúci program a pred výpisom skontrolujeme, či je riešenie správne

Prvý pokus:

bool spravne(int a[], int k, int n) {
    /* je v poli a dlzky k kazde cislo od 0 po n-1 najviac raz? */
    bool bolo[maxN];
    for (int i = 0; i < n; i++) {
        bolo[i] = false;
    }
    for (int i = 0; i < k; i++) {
        if (bolo[a[i]]) return false;
        bolo[a[i]] = true;
    }
    return true;
}

void generuj(int a[], int i, int k, int n) {
    /* v poli a dlzky k mame prvych i cifier,
     * chceme vygenerovat vsetky moznosti
     * poslednych k-i cifier */
    if (i == k) {
        if (spravne(a, k, n)) {
            vypis(a, k);
        }
    } else {
        for (int x = 0; x < n; x++) {
            a[i] = x;
            generuj(a, i + 1, k, n);
        }
    }
}

Cvičenie: ako by sme napísali funkciu spravne, ak by nedostala ako parameter hodnotu n?

Prehľadávanie s návratom, backtracking

• Predchádzajúce riešenie je neefektívne, lebo prechádza cez všetky variácie s opakovaním a veľa z nich zahodí.
  • Napríklad pre k=7 a n=10 pozeráme Syntaktická analýza (parsing) neúspešná (MathML (experimentálne): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 10^7} variácií s opakovaním, ale iba 604800 z nich je správnych, čo je asi 6%
• Len čo sa v poli a vyskytne opakujúca sa cifra, chceme túto vetvu prehľadávania ukončiť, lebo doplnením ďalších cifier problém neodstránime
• Spravíme funkciu moze(a,i,x), ktorá určí, či je možné na miesto i v poli a dať cifru x
• Testovanie správnosti vo funkcii generuj sa dá vynechať

bool moze(int a[], int i, int x) {
    /* Mozeme dat hodnotu x na poziciu i v poli a?
     * Mozeme, ak sa nevyskytuje v a[0..i-1] */
    for (int j = 0; j < i; j++) {
        if (a[j] == x) return false;
    }
    return true;
}

void generuj(int a[], int i, int k, int n) {
    /* v poli a dlzky k mame prvych i cifier,
     * chceme vygenerovat vsetky moznosti
     * poslednych k-i cifier */
    if (i == k) {
        vypis(a, k);
    } else {
        for (int x = 0; x < n; x++) {
            if (moze(a, i, x)) {
                a[i] = x;
                generuj(a, i + 1, k, n);
            }
        }
    }
}

Možné zrýchlenie: vytvoríme trvalé pole bolo, v ktorom bude zaznamené, ktoré cifry sa už vyskytli a to použijeme vo funkcii moze.

• Po návrate z rekurzie nesmieme zabudúť príslušnú hodnotu odznačiť!

void generuj(int a[], bool bolo[], int i, int k, int n) {
    /* v poli a dlzky k mame prvych i cifier,
     * v poli bolo mame zaznamenane, ktore cifry su uz pouzite,
     * chceme vygenerovat vsetky moznosti
     * poslednych k-i cifier */
    if (i == k) {
        vypis(a, k);
    } else {
        for (int x = 0; x < n; x++) {
            if (!bolo[x]) {
                a[i] = x;
                bolo[x] = true;
                generuj(a, bolo, i + 1, k, n);
                bolo[x] = false;
            }
        }
    }
}

int main(void) {
    const int maxK = 100;
    const int maxN = 100;
    int a[maxK];
    bool bolo[maxN];
    int k, n;
    cout << "Zadajte k a n (k<=n): ";
    cin >> k >> n;
    for (int i = 0; i < n; i++) {
        bolo[i] = false;
    }
    generuj(a, bolo, 0, k, n);
}

Cvičenia: ako potrebujeme zmeniť program, aby sme generovali všetky postupnosti k cifier z množiny {0,..,n-1}, také, že:

• z každej cifry sú v postupnosti najviac 2 výskyty?
• žiadne dve po sebe idúce cifry nie sú rovnaké?

Technika rekurzívneho prehľadávania všetkých možností s orezávaním beznádejných vetiev sa nazýva prehľadávanie s návratom alebo backtracking.

• Hľadáme všetky postupnosti, ktoré spĺňajú nejaké podmienky
  • Vo všeobecnosti nemusia byť rovnako dlhé
• Ak máme celú postupnosť, vieme otestovať, či spĺňa podmienku (funkcia spravne)
• Ak máme časť postupnosti a nový prvok, vieme otestovať, či po pridaní tohto prvku má ešte šancu tvoriť časť riešenia (funkcia moze)
  • Funkcia moze nesmie vrátiť false, ak ešte je možné riešenie
  • Môže vrátiť true, ak už nie je možné riešenie, ale nevie to ešte odhaliť
  • Snažíme sa však odhaliť problém čím skôr

Všeobecná schéma

void generuj(int a[], int i) {
    /* v poli a dlzky k mame prvych i cisel z riesenia */
    if (spravne(a, i)) { 
        /* ak uz mame cele riesenie, vypiseme ho */
        vypis(a, i);
    } else {
        pre vsetky hodnoty x {
            if (moze(a,i,x) {
                a[i] = x;
                generuj(a, i + 1);
            }
        }
    }
}

Prehľadávanie s návratom môže byť vo všeobecnosti veľmi pomalé, čas výpočtu exponenciálne rastie.

Problém 8 dám

Cieľom je rozmiestniť n dám na šachovnici nxn tak, aby sa žiadne dve navzájom neohrozovali, tj. aby žiadne dve neboli v rovnakom riadku, stĺpci, ani na rovnakej uhlopriečke.

Príklad pre n=4:

 . * . .
 . . . *
 * . . .
 . . * .

• V každom riadku bude práve jedna dáma, teda môžeme si riešenie reprezentovať ako pole damy dĺžky n, kde damy[i] je stĺpec, v ktorom je dáma na riadku i
• Podobne ako v predchádzajúcom príklade chceme do poľa dať čísla od 1 po n, aby spĺňali ďalšie podmienky (v každom stĺpci a na každej uhlopriečke najviac 1 dáma)
• Vytvoríme si polia, kde si budeme pamätať pre každý stĺpec a uhlopriečku, či už je obsadený
• Uhlopriečky v oboch smeroch očísľujeme číslami od 0 po 2n-2
  • V jednom smere majú miesta na uhlopriečke rovnaký súčet, ten teda bude číslom uhlopriečky
  • V druhom smere majú rovnaký rozdiel, ten však môže byť aj záporný, pričítame n-1
• Pre jednoduchosť použijeme globálne premenné, lebo potrebujeme veľa polí
  • Globálne premenné spôsobujú problémy vo väčších programoch: mená premenných sa môžu "biť", môžeme si omylom prepísať číslo dôležité v inej časti programu
  • Mohli by sme si tiež spraviť struct obsahujúci všetky premenné potrebné v rekurzii a odovzdávať si ten

#include <iostream>
using namespace std;

/* globalne premenne */
const int maxN = 100;
int n;
int damy[maxN];       /* pole ktore obsahuje stlpec s damou v riadku i*/
bool bolStlpec[maxN]; /* pole ktore obsahuje true ak stlpec obsadeny damou */
bool bolaUhl1[2 * maxN - 1];  /* polia ktore obsahuju true ak uhlopriecky obsadene */
bool bolaUhl2[2 * maxN - 1];
int pocet;       /* pocet najdenych rieseni */

int uhl1(int i, int j) {
    /* na ktorej uhlopriecke je riadok i, stlpec j v smere 1? */
    return i + j;
}

int uhl2(int i, int j) {
    /* na ktorej uhlopriecke je riadok i, stlpec j v smere 2? */
    return n - 1 + i - j;
}

void vypis() {
    /* vypis sachovnicu textovo a zvys pocitadlo rieseni */
    pocet++;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (damy[i] == j) cout << " *";
            else cout << " .";
        }
        cout << endl;
    }
    cout << endl;
}

void generuj(int i) {
    /* v poli damy mame prvych i dam, dopln dalsie */
    if (i == n) {
        vypis();
    } else {
        for (int j = 0; j < n; j++) {
            /* skus dat damu na riadok i, stlpec j */
            if (!bolStlpec[j]
                    && !bolaUhl1[uhl1(i, j)] && !bolaUhl2[uhl2(i, j)]) {
                damy[i] = j;
                bolStlpec[j] = true;
                bolaUhl1[uhl1(i, j)] = true;
                bolaUhl2[uhl2(i, j)] = true;
                generuj(i + 1);
                bolStlpec[j] = false;
                bolaUhl1[uhl1(i, j)] = false;
                bolaUhl2[uhl2(i, j)] = false;
            }
        }
    }
}

int main(void) {
    cout << "Zadajte velkost sachovnice: ";
    cin >> n;
    for (int i = 0; i < n; i++) {
        bolStlpec[i] = false;
    }
    for (int i = 0; i < 2 * n + 1; i++) {
        bolaUhl1[i] = false;
        bolaUhl2[i] = false;
    }

    /* rekuzia */
    pocet=0;
    generuj(0);
    cout << "Pocet rieseni: " << pocet << endl;
}

Generovanie všetkých podmnožín

Chceme vypísať všetky podmnožiny množiny {0,..,m-1}. Na rozdiel od variácií nám v podmnožine nezáleží na poradí (napr. {0,1} = {1,0}), prvky teda budeme vždy vypisovať od najmenšieho po najväčší. Napr. pre m=2 máme podmnožiny

{}
{0}
{0,1}
{1}

Podmnožinu vieme vyjadriť ako binárne pole dĺžky m, kde a[i]=0 znamená, že i nepatrí do množiny a a[i]=1 znamená, že patrí. Teda môžeme použiť predchádzajúci program pre n=2, k=m a zmeniť iba výpis:

void vypis(int a[], int m) {
    cout << "{";
    bool prve = true;
    for (int i = 0; i < m; i++) {
        if (a[i] == 1) {
            if (prve) {
                cout << "" << i;
                prve=false;
            } else {
                cout << "," << i;
            }
        }
    }
    cout << "}" << endl;
}

• V premennej prve si pamätáme, či máme oddeliť ďalšie vypisované číslo od predchádzajúceho.
  • Ak ešte žiadne nebolo, oddeľovač je prázdny reťazec.
  • Ak už sme niečo vypísali, oddeľovač je čiarka.

Namiesto poľa intov môžeme použiť pole boolovských hodnôt a celý program trochu prispôsobiť tomu, že generujeme podmnožiny:

#include <iostream>
#include <cstring>
using namespace std;

void vypis(bool a[], int m) {
    cout << "{";
    bool prve = true;
    for (int i = 0; i < m; i++) {
        if (a[i]) {
            if (prve) {
                cout << "" << i;
                prve=false;
            } else {
                cout << "," << i;
            }
        }
    }
    cout << "}" << endl;
}

void generuj(bool a[], int i, int m) {
    /* v poli a dlzky k mame rozhodnutie o prvych i
     * prvkoch, chceme vygenerovat vsetky podmnoziny
     * prvkov {i..m-1} */
    if (i == m) {
        vypis(a, m);
    } else {
        a[i] = true;
        generuj(a, i + 1, m);
        a[i] = false;
        generuj(a, i + 1, m);
    }
}

int main(void) {
    const int maxM = 100;
    int m;
    cin >> m;
    bool a[maxM];
    generuj(a, 0, m);
}

Pre n=3 program vypíše:

{0,1,2}
{0,1}
{0,2}
{0}
{1,2}
{1}
{2}
{}

Cvičenie: Čo by program vypísal, ak by sme prehodili true a false v rekurzii?