3. cvičení

Důležité pojmy

• Pro čtení vstupních dat z terminálu (tj. data zadaná uživatelem) lze použít objekt cin, který funguje obdobně jako objekt cout pro výpis:

  int promenna;
  cin >> promenna;
  

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