Programovanie (1) v C/C++
1-INF-127, ZS 2024/25
Prednáška 10: Rozdiel medzi revíziami
(29 medziľahlých úprav od 2 ďalších používateľov nie je zobrazených) | |||
Riadok 1: | Riadok 1: | ||
== Oznamy == | == Oznamy == | ||
− | * | + | * Zajtra 22:00 termín odovzdania DÚ1 |
− | * | + | * V stredu zverejníme DÚ2 |
− | * Zajtrajšia rozcvička bude z dnešnej prednášky | + | * Zajtrajšia rozcvička bude z dnešnej prednášky (a teda je fajn si prednášku pozrieť pred cvičením) |
− | * | + | * V piatok je sviatok, cvičenia nebudú |
− | + | * V utorok 5.11. na cvičeniach bude krátky test podobne ako na prednáške 7.10. | |
− | * | + | ** Bude zahŕňať učivo po dnešnú prednášku. |
− | ** Bude zahŕňať učivo po dnešnú prednášku | ||
** Môžete si priniesť ťahák 1 list A4. Používanie počítača nebude povolené. | ** Môžete si priniesť ťahák 1 list A4. Používanie počítača nebude povolené. | ||
− | ** | + | ** Ide o súčasť cvičení 7, takže študenti, ktorí majú cvičenia 7 uznané na základe testu pre pokročilých, nemusia prísť. |
− | |||
* Všímajte si varovania kompilátora, môžu vás upozorniť na chybu | * Všímajte si varovania kompilátora, môžu vás upozorniť na chybu | ||
Riadok 33: | Riadok 31: | ||
==Opakovanie rekurzie== | ==Opakovanie rekurzie== | ||
* '''Rekurzívna definícia''': určitý objekt definujeme pomocou menších objektov toho istého typu | * '''Rekurzívna definícia''': určitý objekt definujeme pomocou menších objektov toho istého typu | ||
− | ** | + | * Napríklad rekurzívna definícia faktoriálu: |
− | ** | + | ** ''n! = 1'' ak ''n≤1'' (triviálny prípad) |
+ | ** ''n! = n ⋅ (n-1)!'' inak | ||
− | * Rekurzívne definície vieme často priamočiaro zapísať do '''rekurzívnych funkcií''' | + | * Rekurzívne definície vieme často priamočiaro zapísať do '''rekurzívnych funkcií''' |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | int | + | int factorial(int n) { |
− | if (n | + | if (n <= 1) return 1; |
− | + | else return n * factorial(n-1); | |
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
* V '''rekurzívnej funkcii''' riešime problém pomocou menších podproblémov toho istého typu | * 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 <tt>left</tt> a <tt>right</tt>, potrebujeme ho porovnať so stredným prvkom tohoto intervalu a potom riešiť tú istú úlohu pre menší interval | + | ** Napríklad aby sme našli číslo ''x'' v utriedenom poli medzi indexami <tt>left</tt> a <tt>right</tt>, 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 <tt>left</tt> a <tt>right</tt>, aby sa dala spraviť rekurzia | + | ** Aj keď sme pôvodne chceli hľadať prvok v celom poli, úlohu rozšírime o parametre <tt>left</tt> a <tt>right</tt>, aby sa dala spraviť rekurzia. |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
int find(int a[], int left, int right, int x) { | int find(int a[], int left, int right, int x) { | ||
Riadok 69: | Riadok 63: | ||
===Zásobník volaní=== | ===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) | + | 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 <tt>main</tt> zavoláme <tt>fib(3)</tt> | * Skúsme napríklad odsimulovať, čo sa deje ak vo funkcii <tt>main</tt> zavoláme <tt>fib(3)</tt> | ||
* Kvôli prehľadnosti si <tt>fib</tt> rozpíšeme na viac riadkov: | * Kvôli prehľadnosti si <tt>fib</tt> rozpíšeme na viac riadkov: | ||
Riadok 135: | Riadok 129: | ||
[[Súbor:fib.png|400px]] | [[Súbor:fib.png|400px]] | ||
− | Pozor, priamočiary rekurzívny zápis výpočtu Fibonacciho čísel je neefektívny, lebo výpočet Fibonacciho čísel sa opakuje | + | Pozor, priamočiary rekurzívny zápis výpočtu Fibonacciho čísel je neefektívny, lebo výpočet Fibonacciho čísel sa opakuje, čas výpočtu rastie exponenciálne od ''n'' |
* Napr. pre ''n=5'' počítame <tt>fib(2)</tt> trikrát, pre ''n=6'' päťkrát a pre ''n=20'' až 4181-krát | * Napr. pre ''n=5'' počítame <tt>fib(2)</tt> trikrát, pre ''n=6'' päťkrát a pre ''n=20'' až 4181-krát | ||
− | + | * Fibonacciho čísla je teda lešie počítať nerekurzívnymi metódami z minulej prednášky, ktorých čas je lineárny od ''n'' | |
− | + | * Iné ukážky z minulej prednášky (faktoriál, gcd, binárne vyhľadávanie) nevedú v rekurzívnej forme takémuto extrémnemu spomaleniu a teda väčšinou nie je problém v nich rekurziu použiť | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Vypisovanie variácií s opakovaním== | ==Vypisovanie variácií s opakovaním== | ||
Riadok 168: | Riadok 155: | ||
int n; | int n; | ||
cin >> n; | cin >> n; | ||
− | for(int i=0; i<n; i++) { | + | for(int i = 0; i < n; i++) { |
− | for(int j=0; j<n; j++) { | + | for(int j = 0; j < n; j++) { |
− | for(int k=0; k<n; k++) { | + | for(int k = 0; k < n; k++) { |
cout << i << j << k << endl; | cout << i << j << k << endl; | ||
} | } | ||
Riadok 270: | Riadok 257: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
bool spravne(int a[], int k, int n) { | bool spravne(int a[], int k, int n) { | ||
− | /* je v poli a dlzky k kazde cislo od 0 po n-1 najviac raz? */ | + | /* je v poli a dlzky k kazde cislo |
+ | * od 0 po n-1 najviac raz? */ | ||
bool bolo[maxN]; | bool bolo[maxN]; | ||
for (int i = 0; i < n; i++) { | for (int i = 0; i < n; i++) { | ||
Riadok 340: | Riadok 328: | ||
void generuj(int a[], bool bolo[], int i, int k, int n) { | void generuj(int a[], bool bolo[], int i, int k, int n) { | ||
/* v poli a dlzky k mame prvych i cifier, | /* v poli a dlzky k mame prvych i cifier, | ||
− | * v poli bolo | + | * v poli bolo su zaznamenane pouzite cifry, |
* chceme vygenerovat vsetky moznosti | * chceme vygenerovat vsetky moznosti | ||
* poslednych k-i cifier */ | * poslednych k-i cifier */ | ||
Riadok 372: | Riadok 360: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Cvičenie: ako potrebujeme zmeniť program, aby sme generovali všetky postupnosti ''k'' cifier z množiny ''{0,..,n-1}'' | + | '''Cvičenie:''' 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? |
− | 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''' | + | 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''', po anglicky '''backtracking'''. |
− | * Hľadáme všetky postupnosti, ktoré spĺňajú nejaké podmienky | + | * Hľadáme všetky postupnosti, ktoré spĺňajú nejaké podmienky. |
− | ** Vo všeobecnosti nemusia byť rovnako dlhé | + | ** Vo všeobecnosti nemusia byť rovnako dlhé. |
− | * Ak máme celú postupnosť, vieme otestovať, či spĺňa podmienku (funkcia <tt>spravne</tt>) | + | * Ak máme celú postupnosť, vieme otestovať, či spĺňa podmienku (funkcia <tt>spravne</tt>). |
− | * Ak máme časť postupnosti a nový prvok, vieme otestovať, či po pridaní tohto prvku má ešte šancu tvoriť časť riešenia (funkcia <tt>moze</tt>) | + | * Ak máme časť postupnosti a nový prvok, vieme otestovať, či po pridaní tohto prvku má ešte šancu tvoriť časť riešenia (funkcia <tt>moze</tt>). |
− | ** Funkcia <tt>moze</tt> nesmie vrátiť <tt>false</tt>, ak ešte je možné riešenie | + | ** Funkcia <tt>moze</tt> nesmie vrátiť <tt>false</tt>, ak ešte je možné riešenie. |
− | ** Môže vrátiť <tt>true</tt>, ak už nie je možné riešenie, ale nevie to ešte odhaliť | + | ** Môže vrátiť <tt>true</tt>, 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 | + | ** Snažíme sa však odhaliť problém čím skôr. |
+ | * Prehľadávanie s návratom môže byť vo všeobecnosti '''veľmi pomalé''', čas výpočtu exponenciálne rastie. | ||
− | Všeobecná schéma | + | '''Všeobecná schéma prehľadávania s návratom''' |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
void generuj(int a[], int i) { | void generuj(int a[], int i) { | ||
Riadok 392: | Riadok 381: | ||
} else { | } else { | ||
pre vsetky hodnoty x { | pre vsetky hodnoty x { | ||
− | if (moze(a,i,x)) { | + | if (moze(a, i, x)) { |
a[i] = x; | a[i] = x; | ||
generuj(a, i + 1); | generuj(a, i + 1); | ||
Riadok 398: | Riadok 387: | ||
} | } | ||
} | } | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Riadok 757: | Riadok 392: | ||
==Problém 8 dám== | ==Problém 8 dám== | ||
− | Prehľadávanie s návratom sa dá využiť aj na riešenie rôznych hlavolamov. Tu si ukážeme jeden z nich. | + | Prehľadávanie s návratom sa dá využiť aj na riešenie rôznych hlavolamov. Tu si ukážeme jeden z nich. <!-- Program nebol podrobnejšie rozberaný na prednáške, tu je uvedený pre záujemcov. --> |
Riadok 777: | Riadok 412: | ||
** V jednom smere majú miesta na uhlopriečke rovnaký súčet, ten teda bude číslom uhlopriečky | ** 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'' | ** V druhom smere majú rovnaký rozdiel, ten však môže byť aj záporný, pričítame ''n-1'' | ||
+ | * Pre jednoduchosť použijeme niekoľko globálnych premenných, aby si rekurzívne funkcie nemuseli posielať veľa argumentov | ||
+ | ** Krajšie by bolo dať tieto premenné do struct-u a posielať ten ako argument | ||
+ | |||
+ | [[Súbor:damy-uh1.png|400px]] [[Súbor:damy-uh2.png|400px]] | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
Riadok 784: | Riadok 423: | ||
/* globalne premenne */ | /* globalne premenne */ | ||
const int maxN = 100; | const int maxN = 100; | ||
− | int n; | + | int n; /* velkost sachovnice */ |
int damy[maxN]; /* damy[i] je stlpec s damou v riadku i*/ | int damy[maxN]; /* damy[i] je stlpec s damou v riadku i*/ | ||
bool bolStlpec[maxN]; /* bolStlpec[i] je true ak stlpec i obsadeny */ | bool bolStlpec[maxN]; /* bolStlpec[i] je true ak stlpec i obsadeny */ | ||
− | /* polia ktore obsahuju true ak uhlopriecky obsadene */ | + | /* polia, ktore obsahuju true, ak uhlopriecky obsadene */ |
bool bolaUhl1[2 * maxN - 1]; | bool bolaUhl1[2 * maxN - 1]; | ||
bool bolaUhl2[2 * maxN - 1]; | bool bolaUhl2[2 * maxN - 1]; | ||
Riadok 856: | Riadok 495: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | ==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 | ||
+ | <pre> | ||
+ | {} | ||
+ | {0} | ||
+ | {1} | ||
+ | {0,1} | ||
+ | </pre> | ||
+ | Podmnožinu vieme vyjadriť ako binárne pole dĺžky ''m'', | ||
+ | * <tt>a[i]=0</tt> znamená, že ''i'' nepatrí do množiny a <tt>a[i]=1</tt> znamená, že patrí. | ||
+ | * Napríklad podmnožina {0,2,3} množiny {0,1,2,3,4} sa zapíše ako pole 1,0,1,1,0. | ||
+ | Teda môžeme použiť program variácie s opakovaním pre ''n=2'', ''k=m'' a zmeniť iba výpis: | ||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
+ | 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; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | * V premennej <tt>prve</tt> 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: | ||
+ | <syntaxhighlight lang="C++"> | ||
+ | #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() { | ||
+ | const int maxM = 100; | ||
+ | int m; | ||
+ | cin >> m; | ||
+ | bool a[maxM]; | ||
+ | generuj(a, 0, m); | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Pre n=3 program vypíše: | ||
+ | <pre> | ||
+ | {0,1,2} | ||
+ | {0,1} | ||
+ | {0,2} | ||
+ | {0} | ||
+ | {1,2} | ||
+ | {1} | ||
+ | {2} | ||
+ | {} | ||
+ | </pre> | ||
+ | |||
+ | Cvičenie: Čo by program vypísal, ak by sme prehodili <tt>true</tt> a <tt>false</tt> v rekurzii? | ||
+ | |||
+ | Generovanie podmnožín využijeme na budúcej prednáške na riešenie problému batoha, čo je jeden z dôležitých praktických problémov, pre ktoré nepoznáme efektívne algoritmy. | ||
== Zhrnutie == | == Zhrnutie == | ||
− | * Videli sme ako rekurzívne generovať všetky postupnosti spĺňajúce určité požiadavky | + | * Videli sme ako rekurzívne generovať všetky postupnosti spĺňajúce určité požiadavky. |
− | * Ak máme špeciálne požiadavky, napr. že žiadne číslo sa neopakuje, môžeme buď generovať všetky | + | * Ak máme špeciálne požiadavky, napr. že žiadne číslo sa neopakuje, môžeme buď generovať všetky postupnosti a testovať to pred výpisom, alebo už počas generovania urezávať neperspektívne vetvy výpočtu, čo je rýchlejšie. |
− | * Táto technika sa volá prehľadávanie s návratom (backtracking) | + | * Táto technika sa volá prehľadávanie s návratom (backtracking). |
* Pozor, čas výpočtu prudko (exponenciálne) rastie s dĺžkou postupností, takže vhodné len pre malé vstupy. | * Pozor, čas výpočtu prudko (exponenciálne) rastie s dĺžkou postupností, takže vhodné len pre malé vstupy. | ||
− | * Dve ukážky: problém | + | * Dve ukážky: problém 8 dám, problém batoha (budúca prednáška). |
Aktuálna revízia z 19:52, 29. október 2024
Obsah
Oznamy
- Zajtra 22:00 termín odovzdania DÚ1
- V stredu zverejníme DÚ2
- Zajtrajšia rozcvička bude z dnešnej prednášky (a teda je fajn si prednášku pozrieť pred cvičením)
- V piatok je sviatok, cvičenia nebudú
- V utorok 5.11. na cvičeniach bude krátky test podobne ako na prednáške 7.10.
- Bude zahŕňať učivo po dnešnú prednášku.
- Môžete si priniesť ťahák 1 list A4. Používanie počítača nebude povolené.
- Ide o súčasť cvičení 7, takže študenti, ktorí majú cvičenia 7 uznané na základe testu pre pokročilých, nemusia prísť.
- Všímajte si varovania kompilátora, môžu vás upozorniť na chybu
main.cpp:15:22: warning: array subscript 1 is above array bounds of 'char [1]' [-Warray-bounds] char str[0]; str [0] = '\n'; main.cpp:16:1: warning: no return statement in function returning non-void [-Wreturn-type] main.cpp:12:31: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare] for (int i = 0; i < strlen(retazec); i ++) {
Opakovanie rekurzie
- Rekurzívna definícia: určitý objekt definujeme pomocou menších objektov toho istého typu
- Napríklad rekurzívna definícia faktoriálu:
- n! = 1 ak n≤1 (triviálny prípad)
- n! = n ⋅ (n-1)! inak
- Rekurzívne definície vieme často priamočiaro zapísať do rekurzívnych funkcií
int factorial(int n) {
if (n <= 1) return 1;
else return n * factorial(n-1);
}
- 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() {
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
Postupnosť volaní počas výpočtu vieme znázorniť aj stromovým diagramom:
Pozor, priamočiary rekurzívny zápis výpočtu Fibonacciho čísel je neefektívny, lebo výpočet Fibonacciho čísel sa opakuje, čas výpočtu rastie exponenciálne od n
- Napr. pre n=5 počítame fib(2) trikrát, pre n=6 päťkrát a pre n=20 až 4181-krát
- Fibonacciho čísla je teda lešie počítať nerekurzívnymi metódami z minulej prednášky, ktorých čas je lineárny od n
- Iné ukážky z minulej prednášky (faktoriál, gcd, binárne vyhľadávanie) nevedú v rekurzívnej forme takémuto extrémnemu spomaleniu a teda väčšinou nie je problém v nich rekurziu použiť
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() {
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() {
const int maxK = 100;
int a[maxK];
int k, n;
cout << "Zadajte k a n: ";
cin >> k >> n;
generuj(a, 0, k, n);
}
Strom rekurzívnych volaní pre k=3, n=2 (generuj je skrátené na gen, červenou je zobrazený obsah poľa a):
Ď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 107 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 namiesto funkcie 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 su zaznamenane pouzite cifry,
* 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() {
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čenie: 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?
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, po anglicky 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.
- Prehľadávanie s návratom môže byť vo všeobecnosti veľmi pomalé, čas výpočtu exponenciálne rastie.
Všeobecná schéma prehľadávania s návratom
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);
}
}
}
}
Problém 8 dám
Prehľadávanie s návratom sa dá využiť aj na riešenie rôznych hlavolamov. Tu si ukážeme jeden z nich.
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 riešenie môžeme reprezentovať ako pole damy dĺžky n, kde damy[i] je stĺpec, v ktorom je dáma na riadku i
- Príklad vyššie by v poli damy mal čísla 1,3,0,2
- Podobne ako pri generovaní variácií bez opakovania 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 polia, kde si pre každý stĺpec a uhlopriečku pamätáme, či už je obsadená
- Uhlopriečky v oboch smeroch očíslujeme čí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 niekoľko globálnych premenných, aby si rekurzívne funkcie nemuseli posielať veľa argumentov
- Krajšie by bolo dať tieto premenné do struct-u a posielať ten ako argument
#include <iostream>
using namespace std;
/* globalne premenne */
const int maxN = 100;
int n; /* velkost sachovnice */
int damy[maxN]; /* damy[i] je stlpec s damou v riadku i*/
bool bolStlpec[maxN]; /* bolStlpec[i] je true ak stlpec i obsadeny */
/* polia, ktore obsahuju true, ak uhlopriecky obsadene */
bool bolaUhl1[2 * maxN - 1];
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() {
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} {1} {0,1}
Podmnožinu vieme vyjadriť ako binárne pole dĺžky m,
- a[i]=0 znamená, že i nepatrí do množiny a a[i]=1 znamená, že patrí.
- Napríklad podmnožina {0,2,3} množiny {0,1,2,3,4} sa zapíše ako pole 1,0,1,1,0.
Teda môžeme použiť program variácie s opakovaním 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() {
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?
Generovanie podmnožín využijeme na budúcej prednáške na riešenie problému batoha, čo je jeden z dôležitých praktických problémov, pre ktoré nepoznáme efektívne algoritmy.
Zhrnutie
- Videli sme ako rekurzívne generovať všetky postupnosti spĺňajúce určité požiadavky.
- Ak máme špeciálne požiadavky, napr. že žiadne číslo sa neopakuje, môžeme buď generovať všetky postupnosti a testovať to pred výpisom, alebo už počas generovania urezávať neperspektívne vetvy výpočtu, čo je rýchlejšie.
- Táto technika sa volá prehľadávanie s návratom (backtracking).
- Pozor, čas výpočtu prudko (exponenciálne) rastie s dĺžkou postupností, takže vhodné len pre malé vstupy.
- Dve ukážky: problém 8 dám, problém batoha (budúca prednáška).