Programovanie (1) v C/C++
1-INF-127, ZS 2018/19

Úvod · Pravidlá · Prednášky · Netbeans a Kate · 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).
· 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]
· Druhá písomka bude v stredu 21.11. o 18:10 v posluchárni B. Bude pokrývať materiál po prednášku 12 (polia, reťazce, rekurzia, triedenia, úvod do smerníkov).
· DÚ3 je zverejnená, odovzdávajte do piatku 23.11. 22:00
· V stredu 21.11. na začiatku doplnkových cvičení bude krátka demonštrácia programu valgrind na hľadanie chýb súvisiacich s pamäťou.


Prednáška 9

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

Oznamy

  • Opravná písomka v piatok 9.11. o 12:20
    • Ak ju chcete písať, prihláste sa cez AIS alebo VOTR (termín sa objaví dnes poobede)
  • Domáca úloha do piatku
    • Časť bodov môžete dostať aj za neúplný program
    • Ďalšia DÚ zverejnená koncom týždňa
  • Dnes na doplnkových cvičeniach pribudne rozcvička a ďalší príklad na rekurziu
    • Odporúčame na doplnkové cvičenia prísť aj stredne pokročilým programátorom, ak ste ešte nerobili s rekurziou (ak sa nezmestíme do F1 248, použijeme aj F2-T3=F2-128)
    • Rozcvička sa bude dať rátať aj doma do 22:00

Poznámky k reťazcom

  • Naučte sa používať funkcie zo štandardných knižníc, ako strlen, strcmp, strcpy, strcat, cin.getline, nie ich verzie z prednášky

Klasické úvodné príklady na rekurziu

Rekurzia je metóda, pri ktorej definujeme objekt (funkciu, pojem, . . . ) pomocou jeho samého.

Na začiatok sa pozrieme na „klasické“ príklady algoritmov využívajúcich rekurziu.

Výpočet faktoriálu

Faktoriál prirodzeného čísla n značíme n! a je to súčin všetkých celých čísel od 1 po n. Pre úplnosť 0! definujeme ako 1.

Výpočet pomocou cyklu z prednášky 3:

int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Rekurzívna definícia faktoriálu: n!=\left\{{\begin{array}{ll}1&{\mathrm  {ak~}}n<2\\n\cdot (n-1)!&{\mathrm  {inak}}\\\end{array}}\right.

Túto matematickú definíciu môžeme priamočiaro prepísať do rekurzívnej funkcie:

int factorial(int n) {
    if (n < 2) return 1;
    else return n * factorial(n-1);
}

Aby sa nám rekurzia nezacyklila, mali by sme dodržiavať nasledujúce zásady:

  • Rekurzívna funkcia musí obsahovať vetvu pre triviálny prípad niektorého vstupu. Táto vetva nebude obsahovať rekurzívne volanie funkcie, ktorú práve definujeme.
  • Rekurzívne volanie funkcie by malo mať vhodne redukovaný niektorý vstup, aby sme sa časom dopracovali k triviálnemu prípadu.

Najväčší spoločný deliteľ (Euklidov algoritmus)

Ďalším tradičným príkladom na rekurziu, s ktorým ste sa už stretli, je počítanie najväčšieho spoločného deliteľa.

  • Euklidov algoritmus z prednášky 3 bol založený na rovnosti gcd(a,b) = gcd(b, a mod b)
  • Tú sme použili v cykle:
int gcd(int a, int b) {
    while(b != 0) {
        int x = a % b;
        a = b;
        b = x;
    }
    return a;
}

Avšak opäť to isté môžeme ešte kratšie a elegantnejšie napísať rekurziou:

int gcd(int a, int b) {
   if (b == 0) return a;
   else return gcd(b, a % b);
}

Fibonacciho čísla

Nemôžeme vynechať obľúbený rekurzívny príklad - Fibonacciho čísla, ktoré sme videli na prednáške 4. Aj tam sa rekurzia priam pýta, keďže Fibonacciho čísla sú samé o sebe definované rekurzívne:

  • F(0)=F(1)=1
  • F(n)=F(n-1)+F(n-2) pre n>2

Z tejto definície vieme opäť urobiť rekurzívnu funkciu jednoducho:

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

Toto je opäť krajšie ako nerekurzívna verzia:

int fib(int n) {
    int f = 1;     // Cislo F(i) 
    int oldF = 1;  // Cislo F(i-1)
    
    for (int i = 2; i <= n; i++) {
        int newF = f + oldF;  // spocitaj nove F(i) pre vyssie i
        oldF = f;             // poposuvaj hodnoty
        f = newF;
    }
    return f;
}

Binárne vyhľadávanie

Aj binárne vyhľadávanie prvku v utriedenom poli z prednášky 7 sa do sprehľadní v rekurzívnom zápise.

Pôvodná nerekurzívna funkcia vrátila polohu prvku x v poli a alebo hodnotou -1, ak sa tam nenachádzal:

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

V rekurzívnej verzii si okraje aktuálneho úseku poľa si v rekurzii posielame ako parametre:

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);
}

Ak chceme vyhľadať x v poli a s n prvkami, voláme find(a, 0, n-1, x).

Na zamyslenie:

  • Táto funkcia má dva triviálne (nerekurzívne) prípady. Ktoré?
  • Aká veličina klesá v každom rekurzívnom volaní?

Tu je ešte trochu iná verzia binárneho vyhľadávania s niekoľkými rozdielmi:

  • vraciame iba či sa x nachádza v poli alebo nie (dalo by sa rozšíriť aj na index)
  • pri porovnávaní x a a[index] rozlišujeme iba dva prípady, nie tri
  • končíme pri intervale dĺžky 1, nie 0
bool contains (int a[], int left, int right, int x){
    if (left == right) return (a[left] == x);
    int index = (left + right) / 2;
    if (x <= a[index]) return contains(a, left, index, x);
    else return contains(a, index+1, right, x);
}

int main(void) {
  const int n = 9;
  int a[n]={1,5,7,12,45,55,72,95,103};
  cout << contains(a, 0, n-1, 467) << endl;
  cout << find(a, 0, n-1, 467) << endl;
}

Zhrnutie

Pri rekurzii vyjadríme riešenie nejakej úlohy pomocou riešenia jednej alebo viacerých úloh toho istého typu, ale s menším vstupom plus ďalšie potrebné nerekurzívne výpočty

  • výpočet n! vyjadríme pomocou výpočtu (n-1)! a násobenia
  • výpočet gcd(a, b) vyjadríme pomocou výpočtu gcd(b, a % b)
  • výpočet F[n] vyjadríme pomocou výpočtu F[n-1] a F[n-2]
  • binárne vyhľadávanie v dlhšom intervale vyjadríme pomocou binárneho vyhľadávania v kratšom intervale

Všimnite si, že občas musíme zoznam parametrov nejakej funkcie rozšíriť pre potreby rekurzie

  • napr. funkcia find by prirodzene dostávala pole a, dĺžku n a hľadaný prvok, ale kvôli rekurzii potrebuje ľavý a pravý okraj
  • pre pohodlie užívateľa môžeme pridať pomocnú funkciu (wrapper):
int find(int a[], int n, int x) {
  return find(a, 0, n-1, x);
}

Viac o rekurzii

Nepriama rekurzia

Všetky doteraz uvedené funkcie sú príkladom priamej rekurzie – definovaná funkcia používa seba samú priamo. Druhým možným prípadom je nepriama rekurzia (alebo tiež vzájomná), kedy funkcia neodkazuje vo svojej definícii priamo na seba, ale využíva inú funkciu, ktorá sa odkazuje naspäť na prvú (všeobecnejšie sa kruh môže uzavrieť na viac krokov). Ako príklad uveďme rekurzívne definície predikátov párnosti a nepárnosti:

bool even(int n) {
    if (n == 0) return true;
    else return odd(n - 1);
}

bool odd(int n) {
    if (n == 0) return false;
    else return even(n - 1);
}

Rekurzia pomocou zásobníka - ako je rekurzia implementovaná

O rekurzívne volania sa stará zásobník volaní (call stack)

  • Ide o všeobecnú štruktúru potrebnú aj v nerekurzívnych programoch, ktoré volajú funkcie
  • Po zavolaní nejakej funkcie f sa pre ňu vytvorí na zásobníku záznam, ktorý obsahuje všetky lokálne premenné a argumenty funkcie
  • Keď potom z funkcie f zavoláme nejakú funkciu g (pričom v rekurzii môže byť aj f=g), tak sa vytvorí nový záznam pre g. Navyše v zázname pre f si uložíme aj to, v ktorom kroku sme prestali s výpočtom, aby sme vedeli správne pokračovať
  • Po skončení výpočtu funkcie g sa jej záznam zruší zo zásobníka. Vrátime k záznamu pre funkciu f a pokračujeme vo výpočte so správnymi hodnotami všetkých premenných a od správneho miesta.

Záznamy v zásobníku si môžeme predstaviť uložené v stĺpci jeden nad druhým

  • vrchný záznam je aktuálny, pre funkciu, ktorá sa vykonáva
  • pod ním je záznam pre funkciu, ktorá ju volala atď
  • na spodku je záznam pre funkciu main

Teraz si môžeme jednoduchý zásobník odsimulovať napríklad na výpočte faktoriálu.

int factorial(int n) {
    if (n < 2) return 1;
    else return n * factorial(n-1);
}

Zložitejšie príklady rekurzie

Každý z predchádzajúcich príkladov sme vedeli pomerne jednoducho zapísať aj bez rekurzie, aj keď rekurzívny výpočet bol často prehľadnejší, zrozumiteľnejší, kratší a krajší.

Ukážeme si však aj príklady, ktoré by sa bez rekurzie písali obtiažne (aj keď ako si neskôr ukážeme, rekurzia sa dá vždy odstrániť, v najhoršom prípade simuláciou zásobníka). Takéto príklady, kde rekurzia veľmi pomáha, uvidíme na zvyšku dnešnej prednášky, ale aj na dvoch ďalších a k rekurzii sa vrátime aj neskôr v semestri a samozrejme na ďalších predmetoch.

Odbočka: korytnačia grafika v SVGdraw

Náš prvý dnešný príklad rekurzie budú rekurzívne obrázky, fraktály. Aby sa nám lepšie vykresľovali, v knižnici SVGdraw je možnosť kresliť pomocou korytnačej grafiky.

  • Vytvoríme si virtuálnu korytnačku, ktorá má určitú polohu a natočenie.
  • Môžeme jej povedať, aby sa otočila doľava alebo doprava o určitý počet stupňov (turtle.turnLeft(uhol) a turtle.turnRight(uhol)).
  • Môžeme jej povedať, aby išla o určitú dĺžku dopredu (turtle.forward(dlzka))
  • Keď ide korytnačka dopredu, zanecháva v piesku chvostom čiarku (vykreslí teda čiaru do nášho obrázku).

Napríklad na vykreslenie štvorca s dĺžkou strany 100 môžeme korytnačke striedavo prikazovať ísť o 100 dopredu a otáčať sa o 90 stupňov doľava.

  • Na obrázku sa animuje pohyb korytnačky (pozri tu)
  • Program by sa dal ľahko rozšíriť na vykresľovanie pravidelného n-uholníka (stačí zmeniť uhol otočenia a počet opakovaní cyklu)
#include "SVGdraw.h"

int main(void) {
    /* Vytvor korytnačku na súradniciach (25,175)
     * otočenú doprava na obrázku s rozmermi 200x200 pixelov,
     * ktorý bude uložený do súboru stvorec.svg. */
    Turtle turtle(200, 200, "stvorec.svg", 25, 175, 0);

    for (int i = 0; i < 4; i++) {
        turtle.forward(150);  /* vykresli čiaru dĺžky 100 */
        turtle.turnLeft(90);  /* otoč sa doľava o 90 stupňov */
    }
    /* strany sú vykreslené v poradí dolná, pravá, horná, ľavá */

    /* Ukonči vypisovanie obrázka. */
    turtle.finish();
}

Fraktály

Fraktály sú útvary, ktorých časti na rôznych úrovniach zväčšenia sa podobajú na celý útvar. Mnohé fraktály vieme definovať a vykresliť pomocou jednoduchej rekurzie.

Ḱochova krivka

Kochova krivka stupňa 3

Príkladom fraktálu je Kochova krivka. Ako vzniká?

  • Predstavme si úsečku, ktorá meria d centimetrov.
  • Spravíme s ňou nasledujúcu transformáciu:
    • Úsečka sa rozdelí na tretiny a nad strednou tretinou sa zostrojí rovnostranný trojuholník. Základňa trojuholníka v krivke nebude.
    • Dostávame tak útvar pozostávajúci zo štyroch úsečiek s dĺžkou d/3
  • Tú istú tranformáciu môžeme teraz spraviť na každej zo štyroch nových úsečiek, t.j. dostávame 16 úsečiek dĺžky d/9
  • Takéto transformácie môžeme robiť do nekončna

Druhá možnosť je popísať krivku pomocou dvoch parametrov: dĺžka d a stupeň n

  • Kochova krivka stupňa 0 je úsečka dĺžky d
  • Kochova krivka stupňa n pozostáva zo štyroch kriviek stupňa n-1 a dĺžky n/3
    • na presný popis umiestnenia a natočenia týchto kriviek nižšieho stupňa použijeme korytnačiu grafiku, čo máme spravené vo funkcii nižšie.
 
#include "SVGdraw.h"

void drawKoch(double d, int n, Turtle& turtle){
    if (n==0) turtle.forward(d);
    else {
        drawKoch(d/3, n-1, turtle);
        turtle.turnLeft(60);
        drawKoch(d/3, n-1, turtle);
        turtle.turnRight(120);
        drawKoch(d/3, n-1, turtle);
        turtle.turnLeft(60);
        drawKoch(d/3, n-1, turtle);
    }
}

int main(void) {
    int width = 310; /* rozmery obrazku */
    int height = 150;

    double d = 300; /* velkost krivky */
    int n = 5; /* stupen krivky */

    /* Vytvor korytnačku otočenú doprava. */
    Turtle turtle(width, height, "fraktal.svg", 1, height-10, 0);

    /* nakresli Kochovu krivku rekurzívne */
    drawKoch(d, n, turtle);

    /* Schovaj korytnačku. */
    turtle.finish();
}

Rekurzívny strom

A ešte jeden príklad fraktálu: strom definovaný nasledovne:

  • strom má dva parametre: veľkosť d a stupeň n
  • strom stupňa 0 je prázdna množina
  • strom stupňa n pozostáva z kmeňa, ktorý tvorí úsečka dĺžky d a z dvoch podstromov, ktoré sú stromy stupňa n-1, veľkosti d/2 a otočené o 30 stupnov doľava a doprava od hlavnej osi stromu (pozri obrázky nižšie)

Rekurzívnu funkciu na vykresľovanie stromu napíšeme tak, aby sa po skončení vrátila na miesto a otočenie, kde začala

  • Bez toho by sa sme nevedeli, kde korytnačka je po vykreslení ľavého podstromu a nemohli by sme teda kresliť pravý
  • Korytnačka teda prejde po každej vetve dvakrát, raz smerom dopredu a raz naspäť.
#include "SVGdraw.h"

void drawTree(double d, int n, Turtle& turtle) {
    if (n == 0) {
        return;  /* stupen 0 - nerob nic */
    } else {
        turtle.forward(d);              /* kmen stromu */
        turtle.turnLeft(30);
        drawTree(d / 2, n - 1, turtle); /* lava cast koruny */
        turtle.turnRight(60);
        drawTree(d / 2, n - 1, turtle); /* prava cast koruny */
        turtle.turnLeft(30);
        turtle.forward(-d);             /* navrat na spodok kmena */
    }
}

int main(void) {
    int width = 150; /* rozmery obrazku */
    int height = 200;

    double d = 100; /* velkost stromu */
    int n = 5; /* stupen krivky */

    /* vytvor korytnačku otočenú hore */
    Turtle turtle(width, height, "fraktal.svg", width / 2, height - 10, 90);

    /* nakresli strom rekurzívne */
    drawTree(d, n, turtle);

    /* schovaj korytnačku */
    turtle.finish();
}

Hanojské veže

  • Problém Hanojských veží pozostáva z troch stĺpcov (tyčiek) a niekoľkých kruhov rôznej veľkosti. Začína sa postavením pyramídy z kruhov (kameňov) na prvú tyčku od najväčšieho po najmenší.
  • Úlohou je potom presunúť celú pyramídu na inú tyčku, avšak pri dodržaní nasledovných pravidiel:
    • v jednom ťahu (na jedenkrát) je možné premiestniť iba jeden hrací kameň
    • väčší kameň nesmie byť nikdy položený na menší

Úlohu budeme riešiť rekurzívne

  • Ak máme iba jeden kameň, úloha je veľmi jednoduchá - preložíme ho z pôvodného stĺpika na cieľový stĺpik.
  • Ak chceme preložiť viac kameňov (nech ich je N), tak
    • Všetky okrem posledného preložíme na pomocný stĺpik (na to použijeme taký istý postup len s N-1 kameňmi)
    • Premiestnime jeden kameň kam potrebujeme
    • Zatiaľ odložené kamene (na pomocnom stĺpiku) preložíme z pomocného na cieľový stĺpik (na to použijeme opäť taký istý postup s N-1 kameňmi)

Aby sme to popísali konkrétnejšie - preloženie N kameňov z A na C (s pomocným stĺpikom B) urobíme takto:

  • Preložíme N-1 kameňov z A na B (s použitím C)
  • Preložíme 1 kameň z A na C (s použitím B - ale reálne to potrebovať nebudeme)
  • Preložíme N-1 kameňov z B na C (s použitím A)
void presunHanoi(int odkial, int cez, int kam, int n){
    if (n == 1) {
        cout << "Prelozim kamen z " << odkial <<" na " << kam << endl;
    } else {
        presunHanoi(odkial, kam, cez, n-1); // odlozime si n-1 na pomocny-cez
        presunHanoi(odkial, cez, kam, 1);   // prelozime najvacsi na finalne miesto
        presunHanoi(cez, odkial, kam, n-1); // zvysnych n-1 prelozime z docasneho odkladiska na finalne
    }
}

int main (void){
    presunHanoi(1, 2, 3, 3); // z veze 1 na vezu 3 (pomocou veze 2)
}

Dôležité je si uvedomiť, že nasledovný postup dodržuje pravidlá. Po zavolaní funkcie presunHanoi vždy platí:

  • Funkcia bude presúvať n horných kameňov z tyče odkial na tyč kam pomocou pomocnej tyče cez.
  • Ak n>1, tak na tyčiach kam a cez sú len väčšie kamene ako horných n kameňov na odkial.
  • Ak n=1, na tyči kam sú len väčšie kamene, obsah tyče cez môže byť ľubovoľný.