3. cvičení

Důležité pojmy

Probrané příklady

  1. Výpočet faktoriálu

    Funkci pro výpočet faktoriálu lze naprogramovat buď nerekurzivně:

    int faktorial(int n)
    {
        int f = 1;
        while (n > 1) {
            f *= n;
            n--;
        }
        return f;
    }
    

    nebo rekurzivně:

    int faktorial_rec(int n)
    {
        if (n == 1) {
            return 1;
        }
        return n * faktorial_rec(n - 1);
    }
    

    Ve funkci main se pak použije např. takto:

    int main()
    {
        int cislo = 1;
        cout << "Zadej cislo: " << endl;
        cin >> cislo;
    
        if (cislo > 0) {
            int vysledek = faktorial(cislo);
            cout << "faktorial cisla " << cislo << " je " << vysledek << endl;
            return 0;
        }
        else {
            cout << "cislo " << cislo << " neni kladne." << endl;
            return 1;
        }
    }
    
  2. Výpočet členů Fibonacciho posloupnosti.

    Rekurzivní verze je jednoduchá, ale velmi pomalá (i výpočet prvních 200 členů trvá dlouho):

    #include <iostream>
    
    using namespace std;
    
    int fibonacci(int n)
    {
        if (n <= 2) {
            return 1;
        }
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
    
    int main()
    {
        int cislo = 1;
        cout << "Zadej cislo: ";
        cin >> cislo;
    
        if (cislo > 0) {
            int vysledek = fibonacci(cislo);
            cout << vysledek << endl;
            return 0;
        else {
            cout << "cislo " << cislo << " neni kladne." << endl;
            return 1;
        }
    }
    

    Pomalost rekurzivní verze je způsobena tím, že při rekurzivním větvení programu nelze využít již známé mezivýsledky (viz obrázek ze cvičení). Abychom mohli využít již spočítané hodnoty a vyhnuli se zbytečným výpočtům, je potřeba naprogramovat nerekurzivní algoritmus. Výsledná funkce je sice komplikovanější, ale mnohem rychlejší.

    #include <iostream>
    
    using namespace std;
    
    int fib(int n)
    {
        // pomocne promenne pro predchozi cleny posloupnosti
        int a = 1;  // a_{i-2}
        int b = 1;  // a_{i-1}
        for (int i = 3; i <= n; i++) {
            // vypocet aktualniho clenu
            int c = a + b;  // a_i
            // posun promennych pro dalsi iteraci
            a = b;
            b = c;
        }
        return b;
    }
    
    int main()
    {
        int cislo = 1;
        cout << "Zadej cislo: ";
        cin >> cislo;
    
        if (cislo > 0) {
            int vysledek = fibonacci(cislo);
            cout << vysledek << endl;
            return 0;
        else {
            cout << "cislo " << cislo << " neni kladne." << endl;
            return 1;
        }
    }
    

Last updated: Tue 06 October 2020