Programovanie (1) v C/C++
1-INF-127, ZS 2017/18

Úvod · Pravidlá · Prednášky · Netbeans · SVGdraw · Testovač
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Tretia písomka bude v stredu 29.11. o 18:15. Bude pokrývať rekurziu, znaky, reťazce, smerníky (vrátane smerníkov na struct), vektor, matice
· DÚ3 je zverejnená, odovzdávajte do pondelka 20.11. 22:00.
· Prosíme študentov, aby si pravidelne čítali e-maily na @uniba.sk adrese alebo aby si tieto emaily presmerovali na adresu, ktorú pravidelne čítajú, viď návod tu: [1]


Prednáška 9

Z Programovanie
Prejsť na: navigácia, hľadanie

Organizačné poznámky

Plán na najbližšie obdobie:

  • Dnes normálne prednáška a doplnkové cvičenia s rozcvičkou
  • Dnes do 22:00 termín na DÚ1
  • V utorok cvičenia - cvičíme rekurziu
  • V stredu prednáška - rekurzia a rekurzívne triedenia
  • Budúci týždeň odpadne - rektorské a dekanské voľno a sviatok (odpadnú obe prednášky a obe cvičenia)
  • Druhá písomka bude v stredu 8.11. o 18:10. Miestnosť oznámime neskôr. Bude pokrývať učivo po prednášku 9 (funkcie, polia, rekurzia).

Opakovanie 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
  • 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);
}
  • Ako by sme vypisovali všetky k-tice v opačnom poradí, od 111 po 000?

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 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é?
  • súčet cifier je aspoň S?

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, vypisme 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 vypísal, ak by sme prehodili true a false v rekurzii?

Problém batoha, Knapsack problem

Zlodej sa vlúpal do obchodu a vidí n vecí, pričom pre každú z nich vie odhadnúť jej hmostnosť a cenu, za ktorú by ju vedel predať. V svojom batohu však vie odniesť len veci s celkovou hmotnosťou najviac W kilogramov. Ako má vybrať veci, aby mali čo najväčšiu cenu a aby ich celková hmostnosť neprekročila W?

Príklad: majme n=3 veci, pričom vec 0 má hmostnoť 10 a cenu 6, vec 1 má hmotnosť 8 a cenu 4 a vec 2 má hmotnosť 6 a cenu 3. Zlodej unesie najviac 15. Na vstupe to zapíšeme takto:

Zadaj pocet predmetov: 3
Zadaj hmotnost a cenu 0-teho predmetu: 10 6
Zadaj hmotnost a cenu 1-teho predmetu: 8 4
Zadaj hmotnost a cenu 2-teho predmetu: 6 3
Zadaj nosnost batoha: 15
Zober predmety 1, 2. Ich cena je 7.

Najlepšie je zobrať veci 1 a 2. Ich cena je 7 a súčet hmotností 14.

Tento problém ešte stretnete v ďalších ročníkoch štúdia, teraz si ukážeme jednoduchý program, ktorý prehľadáva všetky možnosti.

Jednoduché riešenie: pozeráme všetky podmnožiny

Ako predtým, generujeme všetky podmnožiny a pre každú spočítame, či jej hmotnosť nepresahuje nosnosť batoha. Podmnožiny však nevypisujeme, ale porovnávame s najlepšou nájdenou doteraz.

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

/* struktura na ukladanie udajov o jednej veci */
struct vec {
    int hmotnost;
    int cena;
};

const int maxN = 100; /* maximalny pocet veci */

/* globalne premenne pouzivane v rekurzii */
int n;           /* celkovy pocet veci v obchode */
vec a[maxN];     /* pole veci */
int maxCena;     /* najlepsie doteraz najdene riesenie */
bool maxZober[maxN];  /* ktore veci su v najlepsom rieseni */
int nosnost;     /* kolko unesie batoh */

/* spocitaj sucet hmotnosti vybranych predmetov */
int sucetHmotnosti(bool zober[]) {
    int sucet = 0;
    for (int i = 0; i < n; i++) {
        if(zober[i]) sucet += a[i].hmotnost;
    }
    return sucet;
}

/* spocitaj sucet cien vybranych predmetov */
int sucetCien(bool zober[]) {
    int sucet = 0;
    for (int i = 0; i < n; i++) {
        if(zober[i]) sucet += a[i].cena;
    }
    return sucet;
}

/* vypis zoznam vybranych predmetov */
void vypis(bool zober[]) {
    cout << "Zober predmety ";
    bool prve = true;    
    for (int i = 0; i < n; i++) {
        if (zober[i]) {
            if (prve) {
                cout << i;
                prve=false;
            } else {
                cout << "," << i;
            }
        }
    }
    cout << ". Ich cena je " << sucetCien(zober) << "." << endl;
}

void generuj(bool zober[], int i) {
    /* v poli a dlzky k mame rozhodnutie o prvych i
     * prvkoch, chceme vygenerovat vsetky podmnoziny
     * prvkov {i..n-1} a kazdu skontrolovat a porovnat s maximom */
    if (i == n) {
        /* uz sme sa rozhodli o kazdom prvku. Zistime, ci mame hmostnost
         * vybranych predmetov <= nosnost */
        if(sucetHmotnosti(zober)<=nosnost) {
            /* ak ano, zistime, ci cena vybranych predmetov
             * je viac ako doteraz najlepsie maximum */
            int cena = sucetCien(zober);
            if(cena>maxCena) {
                /* prekopiruj sucasny vyber do najlepsieho */
                maxCena = cena;
                for(int i=0; i<n; i++) {
                    maxZober[i] = zober[i];
                }
            }
        }
    } else {
        /* dosad true aj false na miesto i
         * a skusaj vsetky moznosti pre zvysok pola */
        zober[i] = true;
        generuj(zober, i+1);
        zober[i] = false;
        generuj(zober, i+1);
    }
}

int main(void) {
    cout << "Zadaj pocet predmetov: ";
    cin >> n;
    /* nacitame hmotnost a cenu predmetov */
    for(int i=0; i<n; i++) {
        cout << "Zadaj hmotnost a cenu " << i << "-teho predmetu: ";
        cin >> a[i].hmotnost >> a[i].cena;
    }
    /* nacitame nostnost */
    cout << "Zadaj nosnost batoha: ";
    cin >> nosnost;
    
    bool zober[maxN];
    maxCena = -1; /* doteraz najlepsie riesenie ma cenu -1 */
    generuj(zober, 0); /* prehladavaj vsetky moznosti */

    vypis(maxZober); /* vypis najlepsie najdene riesenie */
}

Trochu rýchlejší program: skončíme vždy keď prekročíme nosnosť

Keď už sme sa rozhodli o prvých i veciach, sčítame hmotnosť tých, čo sme vybrali, a ak prekračuje nosnosť, túto vetvu hľadania ukončíme - nemá zmysel dopĺňať ďalšie hodnoty do zvyšku poľa, ak už zvolené veci sú príliš ťažké.

/* spocitaj sucet hmotnosti vybranych predmetov,
 * ale uvazujme iba prvych k predmetov  */
int sucetHmotnosti(bool zober[], int k) {
    int sucet = 0;
    for (int i = 0; i < k; i++) {
        if(zober[i]) sucet += a[i].hmotnost;
    }
    return sucet;
}

void generuj(bool zober[], int i) {
    /* v poli a dlzky k mame rozhodnutie o prvych i
     * prvkoch. Chceme prehladat vsetky perspektivne podmnoziny
     * prvkov {i..n-1} a kazdu skontrolovat a porovnat s maximom */

    /* ak uz sme prekrocili nosnost, nemusime pokracovat v hladani */
    if(sucetHmotnosti(zober, i) > nosnost) return;
    if (i == n) {
        /* uz sme sa rozhodli o kazdom prvku.
         * Sucasne vieme, ze hmostnost
         * vybranych predmetov <= nosnost.
         * Zistime teda, ci cena vybranych predmetov
         * je viac ako doteraz najlepsie maximum */
        int cena = sucetCien(zober);
        if (cena > maxCena) {
            /* prekopiruj sucasny vyber do najlepsieho */
            maxCena = cena;
            for (int i = 0; i < n; i++) {
                maxZober[i] = zober[i];
            }
        }
    } else {
        /* dosad true aj false na miesto i
         * a skusaj vsetky moznosti pre zvysok pola */
        zober[i] = true;
        generuj(zober, i + 1);
        zober[i] = false;
        generuj(zober, i + 1);
    }
}

Ešte rýchlejší program: neprepočítavame nosnosť a cenu vždy znovu a znovu

Predchádzajúci program vždy znovu a znovu prepočítava hmotnosť a cenu, aj keď sa zoznam vybraných predmetov zmení iba trochu. Namiesto toho si môžeme v rekurzii udržiavať aktuálnu hmotnosť aj cenu doteraz vybraných predmetov.

void generuj(bool zober[], int i, int hmotnost, int cena) {
    /* v poli a dlzky k mame rozhodnutie o prvych i
     * prvkoch, hmotnost je sucet hmotnosti uz vybranych predmetov
     * a cena je sucet ich cien.
     * Chceme prehladat vsetky perspektivne podmnoziny
     * prvkov {i..n-1} a kazdu skontrolovat a porovnat s maximom */

    /* ak uz sme prekrocili nosnost, nemusime pokracovat v hladani */
    if(hmotnost > nosnost) return;
    if (i == n) {
        /* uz sme sa rozhodli o kazdom prvku.
         * Sucasne vieme, ze hmostnost
         * vybranych predmetov <= nosnost.
         * Zistime teda, ci cena vybranych predmetov
         * je viac ako doteraz najlepsie maximum */
        if (cena > maxCena) {
            /* prekopiruj sucasny vyber do najlepsieho */
            maxCena = cena;
            for (int i = 0; i < n; i++) {
                maxZober[i] = zober[i];
            }
        }
    } else {
        /* dosad true aj false na miesto i
         * a skusaj vsetky moznosti pre zvysok pola */
        zober[i] = true;
        generuj(zober, i + 1, hmotnost + a[i].hmotnost, cena + a[i].cena);
        zober[i] = false;
        generuj(zober, i + 1, hmotnost, cena);
    }
}
  • V main zavoláme generuj(zober, 0, 0, 0);
    • Prečo sme nastavili cenu aj hmotnost na 0?