Prednáška 3

Oznamy

• Budúci pondelok 5. októbra bude v čase prednášky teoretické cvičenie
  • Budete písať krátky test zameraný učivo z prvých troch prednášok
  • Úspešní riešitelia testu pre pokročilých sa testu zúčastniť nemusia
  • Na teste bude povolené používať pero a ťahák vo forme jedného obojstranne popísaného listu A4

Opakovanie: výpočet faktoriálu

#include <iostream>
using namespace std;

int main() {
    int n;
    
    cout << "Zadajte n: ";
    cin >> n;
    
    int vysledok = 1;
    for (int i = 1; i <= n; i++) {
       vysledok = vysledok * i;
    }
    
    cout << n << "! = " << vysledok << endl;
}

Cvičenie: rozšírte program tak, aby okrem výpisu výsledku aj rozpísal faktoriál ako súčin:

Zadajte n: 4
4! = 1*2*3*4 = 24

Príklad behu programu pre n=4:

Zadajte n: 4
4! = 24

Cvičenie: rozšírte program tak, aby okrem výpisu výsledku aj rozpísal faktoriál ako súčin:

Zadajte n: 4
4! = 1*2*3*4 = 24

Ďalšie príklady na cyklus for

Simulovanie hodov kocky

Nasledujúci program od používateľa načíta číslo n a vypíše n simulovaných hodov kocky (každý na samostatný riadok).

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main() {
    // Inicializacia generatora pseudonahodnych cisel
    srand(time(NULL)); 
 
    int n;
    cout << "Zadajte pocet hodov: ";
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        // Vygenerovanie a vypisanie hodu kockou
        cout << rand() % 6 + 1 << endl; 
    }
}

Príklad behu programu:

Zadajte pocet hodov: 6
2
6
1
2
1
4

• Program využíva funkciu rand(), ktorá generuje pseudonáhodné celé čísla.
  • Nie sú v skutočnosti náhodné, lebo ide o pevne definovanú matematickú postupnosť, ktorá však má mnohé vlastnosti náhodných čísel.
  • Aby bolo možné použiť túto funkciu, treba do hlavičky pridať #include <cstdlib>.
  • Výstupom funkcie rand() je nezáporné celé číslo medzi nulou a nejakou veľkou konštantou.
  • Zvyšok po delení tohto čísla šiestimi, t.j. rand() % 6, je potom číslo medzi 0 a 5. Ak k tomu pripočítame 1, dostaneme číslo od 1 po 6.
• Funkcia srand inicializuje generátor pseudonáhodných čísel na základe parametra určujúceho počiatočný bod pseudonáhodnej postupnosti.
  • My ako tento parameter používame aktuálny čas (v sekundách od začiatku roku 1970), čo zaručuje dostatočný efekt náhodnosti.
  • Aby bolo možné použiť funkciu time, je treba do hlavičky pridať #include <ctime>.

Vypisovanie deliteľov (podmienka v cykle)

Nasledujúci program načíta od používateľa prirodzené číslo n a vypíše zoznam jeho deliteľov.

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "Zadajte cislo: ";
    cin >> n;
    
    cout << "Delitele cisla " << n << ":";
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            cout << " " << i;
        }
    }    
    cout << endl;
}

Príklad behu programu:

Zadajte cislo: 30
Delitele cisla 30: 1 2 3 5 6 10 15 30

Cyklus while

Schéma cyklu while

Okrem cyklu for možno v jazykoch C/C++ používať aj cyklus while s nasledujúcou schémou:

while (podmienka) { 
    telo cyklu 
}

Telo takéhoto cyklu sa vykonáva, kým je podmienka cyklu splnená. Presnejšie sa pri vykonávaní cyklu while typicky deje nasledovné:

1. Overí sa, či je podmienka cyklu splnená.
2. Ak áno, vykoná sa telo cyklu a celý proces sa opakuje (čiže sa opätovne vykoná overenie podmienky z bodu 1, atď.).
3. Ak nie, vykonávanie programu pokračuje prvým príkazom nasledujúcim za cyklom while.

Vypisovanie čísel od 1 po n pomocou while

Program z minulej prednášky, vypisujúci všetky prirodzené čísla od 1 po n, môžeme napísať aj pomocou cyklu while:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // Premenna i bude obsahovat aktualne vypisovane cislo
    int i = 1;            
    while (i <= n) {      
        cout << " " << i; 
        i++;            
    }
    cout << endl;
}

Úroky v banke

• Predpokladajme, že na začiatku každého roku uložíme na účet nejakú pevnú sumu (napríklad 1000 EUR).
• Na konci každého roku sa vklad zúročí ročným úrokom (napríklad 5%).
• Za koľko rokov úspory dosiahnu danú cieľovú čiastku (napríklad 10000 EUR)?

Túto úlohu budeme riešiť programom pracujúcim nasledovne:

• V premennej ciastka budeme uchovávať aktuálny stav účtu
• V každom roku túto premennú zvýšime o vklad a úrok
• Toto opakujeme, kým suma uložená v premennej nie je rovná aspoň cieľovej čiastke.

To môžeme vyjadriť pomocou cyklu while.

#include <iostream>
using namespace std;

int main(void) {
    double vklad, ciel, urok;
        
    cout << "Zadaj kazdorocny vklad: ";
    cin >> vklad;
    cout << "Zadaj cielovu ciastku: ";
    cin >> ciel;
    cout << "Zadaj rocny urok (v %): ";
    cin >> urok;
    
    int rok = 0;
    double ciastka = 0;
    
    while (ciastka < ciel) {
        rok++;                   
        ciastka = (ciastka + vklad) * (1 + urok / 100);
        cout << "Na konci roku " << rok << " je na ucte " << ciastka << " EUR." << endl;  
    }
}

Ukážkový vstup a výstup:

Zadaj kazdorocny vklad: 1000
Zadaj cielovu ciastku: 10000
Zadaj rocny urok (v %): 5
Na konci roku 1 je na ucte 1050 EUR
Na konci roku 2 je na ucte 2152.5 EUR
Na konci roku 3 je na ucte 3310.12 EUR
Na konci roku 4 je na ucte 4525.63 EUR
Na konci roku 5 je na ucte 5801.91 EUR
Na konci roku 6 je na ucte 7142.01 EUR
Na konci roku 7 je na ucte 8549.11 EUR
Na konci roku 8 je na ucte 10026.6 EUR

Euklidov algoritmus

Euklidov algoritmus slúži na hľadanie najväčšieho spoločného deliteľa dvojice kladných celých čísel a, b.

• To znamená: hľadáme najväčšie kladné prirodzené číslo d, ktoré delí súčasne a aj b.
• Najväčší spoločný deliteľ čísel a, b označujeme gcd(a,b) (z angl. greatest common divisor). V slovenčine sa používa aj s označenie nsd(a,b).
• Ide o jeden z najstarších známych algoritmov vôbec. Jeho variant popísal už Euklides v diele Základy okolo roku 300 pred Kr.

Príklad:

• Delitele čísla 12 sú 1, 2, 3, 4, 6, 12.
• Delitele čísla 8 sú 1, 2, 4, 8.
• Spoločné delitele 8 a 12 teda sú 1, 2, 4.
• Najväčší spoločný deliteľ čísel 8 a 12 je teda gcd(8,12) = 4.

Euklidov algoritmus je založený na platnosti nasledujúcej lemy.

Lema. Pre všetky kladné celé čísla a, b platí:

gcd(a,b) = gcd(b, a mod b).

Dôkaz.

• Nech X je množina spoločných deliteľov a a b, nech Y je množina spoločných deliteľov b a a mod b. Dokážeme rovnosť X = Y.
• Ak označíme r := a mod b, tak existuje celé číslo q také, že a = q b + r.
• Ak x ∈ Y, číslo x delí b aj r a z rovnosti a = q b + r vyplýva, že delí aj a. Teda x ∈ X.
• Ak naopak x ∈ X, číslo x delí a aj b a z rovnosti r = a - qb vyplýva, že delí aj r. Preto x ∈ Y.
• Dokázali sme teda, že platí X ⊆ Y a súčasne X ⊆ Y. Preto X = Y. ◻

Poznámka: môže sa stať, že a mod b je 0. Nakoľko ale každé celé číslo delí nulu, gcd(b, 0), takže tvrdenie aj v tomto prípade platí.

Hodnotu gcd(a,b) teda možno nájsť Euklidovým algoritmom takto:

1. Ak a mod b = 0, nutne gcd(a,b) = b.
2. V opačnom prípade vypočítame rovnakým spôsobom hodnotu gcd(b, a mod b).

(Všimnime si, že v bode 2 pre a < b platí a mod b = a, takže obidva argumenty sa iba vymenia. Prípad a = b tu nastať nemôže, lebo v takom prípade je splnená podmienka z bodu 1. Ak nakoniec a > b, nutne a mod b < b, takže prvý argument už bude aj naďalej väčší ako ten druhý. Keďže navyše b < a a a mod b < b, sú obidva argumenty oproti pôvodným aspoň o 1 menšie. To garantuje, že sa Euklidov algoritmus v konečnom čase zastaví.)

Implementácia tohto algoritmu teda môže vyzerať nasledovne:

#include <iostream>
using namespace std;

int main() {
    int a, b;    
    cout << "Zadaj dvojicu kladnych celych cisel: ";
    cin >> a >> b;
    
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    
    cout << "Najvacsi spolocny delitel je " << a << "." << endl;
}

Príklad behu programu:

Zadaj dvojicu kladnych celych cisel: 30 8
Najvacsi spolocny delitel je 2.

Tento výpočet prešiel cez dvojice:

30 8
8 6
6 2
2 0

Nekonečný cyklus

V cykle while typu

while (true) {
    telo cyklu
}

je podmienka stále splnená; telo cyklu sa teda opakuje donekonečna resp. kým program nezastavíme (v prípade, že cyklus neukončíme umelo príkazom break, ktorým sa budeme zaoberať neskôr).

Napríklad môžeme donekonečna niečo vypisovať na konzolu:

#include <iostream>
using namespace std;

int main(void) {
    while (true) {
        cout << "Hello, World!" << endl;
    }
    return 0;
}

Príklad č. 5: Hra „hádaj číslo”

V nasledujúcom programe si počítač „myslí” číslo od 1 do 100 a užívateľ háda, o ktoré číslo ide (až kým nakoniec neuhádne).

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main(void) {
    srand(time(NULL));

    int num = rand() % 100 + 1;
    cout << "Myslim si cislo od 1 po 100. Tvoj tip: ";
    
    bool correct = false;

    while (!correct) {
        int guess;
        cin >> guess;
        if (guess < num) {
            cout << "Prilis nizko. Iny tip: ";
        } else if (guess > num) {
            cout << "Prilis vysoko. Iny tip: ";        
        } else {
            correct = true;
            cout << "Spravne!" << endl;
        }
    }
    return 0;
}

Príklad behu programu:

Myslim si cislo od 1 po 100. Tvoj tip: 50
Prilis nizko. Iny tip: 70
Prilis nizko. Iny tip: 90
Prilis vysoko. Iny tip: 80
Spravne!

Príkazy break a continue

V C/C++ existuje dvojica príkazov umožňujúcich umelo prerušiť vykonávanie cyklu resp. jednej jeho iterácie:

• Príkaz break ukončí cyklus, v ktorom sa program práve nachádza; vykonávanie programu pokračuje prvým príkazom za cyklom.
• Príkaz continue „skočí” na ďalšiu iteráciu cyklu, pričom nevykoná zvyšok tela cyklu.

Tieto príkazy treba používať s mierou, keďže robia program menej prehľadným a sú častým zdrojom chýb.

Príklad: Hra „hádaj číslo” po druhé

Program uvedený vyššie môžeme prepísať bez boolovskej premennej s použitím nekonečného cyklu, z ktorého ale „vyskočíme” príkazom break, keď používateľ uhádne.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main(void) {
    srand(time(NULL));

    int num = rand() % 100 + 1;
    cout << "Myslim si cislo od 1 po 100. Tvoj tip: ";
    
    while (true) {
        int guess;
        cin >> guess;
        if (guess < num) {
            cout << "Prilis nizko. Iny tip: ";
        } else if (guess > num) {
            cout << "Prilis vysoko. Iny tip: ";        
        } else {
            cout << "Spravne!" << endl;
            break;
        }
    }
    return 0;
}

Viac o cykle for

Schéma cyklu for

Cyklus for sme doposiaľ používali iba veľmi základným spôsobom; jeho možnosti sú omnoho väčšia. Vo všeobecnosti možno schému cyklu for popísať nasledovne:

for (prikaz1; podmienka; prikaz2) {
    postupnost_prikazov
}

Takýto cyklus potom pracuje nasledovne:

• Vykoná sa príkaz prikaz1.
• Kým platí podmienka podmienka, vykonáva sa telo cyklu postupnost_prikazov zakaždým nasledované príkazom prikaz2.

Uvedený cyklus for je teda typicky ekvivalentný nasledujúcemu cyklu while:

prikaz1;
while (podmienka) {
    postupnost_prikazov
    prikaz2;
}

(Drobnou nepodstatnou výnimkou z uvedeného tvrdenia je prípad, keď telo cyklu for obsahuje príkaz continue. V takom prípade sa príkaz prikaz2 aj tak vykoná.)

Nasledujúce kúsky kódu napríklad obidva vypisujú čísla 0 až 9:

for (int i = 0; i <= 9; i++) {
    cout << " " << i;
}

int i = 0;
while (i <= 9) {
    cout << " " << i;
    i++;
}

Cyklus for spravidla používame, ak má náš cyklus krátky a jednoduchý iterátor (prikaz2) a jednoduchú podmienku. V opačnom prípade väčšinou používame cyklus while.

Príklad č. 1: Vypisovanie deliteľov po druhé

Vráťme sa k programu na vypisovanie všetkých deliteľov čísla n z úvodu tejto prednášky. Tam sme deliteľov vypisovali v poradí od najmenšieho po najväčší, a to použitím cyklu

for (int i = 1; i <= n; i++)

Nahradením tohto cyklu cyklom

for (int i = n; i > 0; i--)

získame program vypisujúci delitele v poradí od najväčšieho po najmenší.

#include <iostream>
using namespace std;

int main(void) {
    int n;
    cout << "Zadajte cislo: ";
    cin >> n;
    
    cout << "Delitele cisla " << n << ":";
    for (int i = n; i > 0; i--) {
        if (n % i == 0) {
            cout << " " << i;
        }
    }
    cout << endl;
    return 0;
}

Príklad behu programu:

Zadajte cislo: 30
Delitelia cisla 30: 30 15 10 6 5 3 2 1

Príklad č. 2: Vypisovanie deliteľov po tretie

Program na vypisovanie deliteľov môžeme o niečo urýchliť: stačí si všimnúť, že i je deliteľ čísla n práve vtedy, keď je deliteľom čísla n číslo n/i; číslo n/i teda môžeme rovno vypísať spoločne s i. Aspoň jedno z tejto dvojice čísel je navyše menšie alebo rovné odmocnine z n, čo znamená, že stačí prehľadať iba čísla i spĺňajúce túto podmienku.

#include <iostream>
using namespace std;

int main(void) {
    int n;
    cout << "Zadajte cislo: ";
    cin >> n;
    
    cout << "Delitelia cisla " << n << ":";
    for (int i = 1; i*i <= n; i++) {
        if (n % i == 0) {
            cout << " " << i << " " << n / i;
        }
    }
    cout << endl;
    return 0;
}

Cvičenie 1: Občas sa môže stať, že program vypíše niektorého deliteľa dvakrát. Kedy? Modifikujte telo cyklu for tak, aby program každého deliteľa vypísal práve raz.

Cvičenie 2: Vyskúšajte si rýchlosť rôznych variantov programu na vypisovanie deliteľov na veľkom vstupe, napríklad pre n = 1234567890.

Príklad č. 3: Nekonečný cyklus for

V cykle

for (prikaz1; podmienka; prikaz2) {
    postupnost_prikazov
}

môžu byť príkazy prikaz1 a prikaz2 aj prázdne – v takom prípade sa na ich mieste nič nevykoná. Podobne môže byť prázdna aj podmienka podmienka, ktorá sa v takom prípade interpretuje ako true. Z uvedeného vyplýva, že nekonečný cyklus možno napísať aj ako

for ( ; true; ) {
    cout << "Hello, World!" << endl;
}

prípadne ekvivalentne ako

for ( ; ; ) {
    cout << "Hello, World!" << endl;
}

Vnorené cykly

Vykreslíme „štvorec” pozostávajúci z n krát n čísel, ktoré sú striedavo 0 a 1, podobne ako biele a čierne políčka na šachovnici.

• Potrebujeme na to dva vnorené cykly: jeden pôjde cez riadky, druhý cez stĺpce.
• Ak je hodnota row + column párna, píšeme 0; inak píšeme 1.

#include <iostream>
using namespace std;

int main(void) {
    int n;
    cin >> n;
    for (int row = 0; row <= n - 1; row++) {
        for (int column = 0; column <= n - 1; column++) {
            if ((row + column) % 2 == 0) {
                cout << "0";
            } else {
                cout << "1";
            }
        }
        cout << endl;
    }
    
    return 0;
}

Úprava a čitateľnosť programov

Pri písaní programov je potrebné myslieť na to, že ho typicky budú okrem počítača čítať aj ľudia (či už ide o vás samotných po dlhšom čase, učiteľov, alebo v praxi o spolupracovníkov na väčšom projekte). Je preto zvykom dodržiavať určité zásady, ktoré čitateľnosť zdrojového kódu zlepšujú:

• Odsadzovanie: príkazy vykonávané v cykle, či v podmienke (alebo vo všeobecnosti v ľubovoľnom bloku medzi { a }) kvôli čitateľnosti odsadzujeme o niekoľko pozícií doprava (napríklad o 4 medzery). Pri vnorených cykloch, podmienkach a podobne odsadzujeme o ďalšie štyri pozície, atď. Väčšina syntax zvýrazňujúcich textových editorov a IDE pre C/C++ nejakým spôsobom odsadzovanie podporujú (minimálne by sa mala dať nastaviť šírka tabulátora).
• Voľné riadky: ucelené časti programu je kvôli prehľadnosti často dobré oddeliť prázdnym riadkom.
• Medzery: odporúča sa (najmä v zložitejších výrazoch) písať okolo operátorov medzery.
• Napríklad zápis

for (int i = 0; i <= count - 1; i++) {
    a += i;
}

je o dosť prehľadnejší ako

for(int i=0;i<=count-1;i++){a+=i;}

• Dĺžka riadku: odporúča sa vyhýbať sa riadkom dlhším ako 80 znakov (aj keď nie vždy sa tento limit dá dodržať striktne). S dlhými riadkami sú problémy pri tlači alebo zobrazovaní v menších oknách; aj na veľkom monitore čitateľa zbytočne namáhajú. V prípade potreby je možné dlhšiu podmienku alebo iný výraz rozdeliť na viac riadkov.
• Názvy premenných: najmä pri rozsiahlejších programoch je vhodné používať názvy premenných, ktoré vyjadrujú ich obsah (napríklad userCount alebo pocet_pouzivatelov namiesto h). Premenné v kratších programoch, alebo premenné používané iba lokálne v kratšom kuse programu možno označovať aj krátkymi zaužívanými názvami, ako napríklad i a j pre premenné v cykloch, n pre počet, alebo a pre pole.
• Komentáre: význam jednotlivých úsekov kódu je najmä pri rozsiahlejších programoch dobré popísať v komentároch.

Pri známkovaní budeme brať do úvahy aj prehľadnosť vašich programov.

Cykly: zhrnutie

• Videli sme niekoľko príkladov využitia cyklov for a while.
• Cyklus for je možné zapísať ako while (a naopak).
• Z cyklu vieme vyskočiť príkazom break, prejsť na ďalšiu iteráciu príkazom continue. Používať s mierou.
• Euklidov algoritmus rýchlo nájde najväčšieho spoločného deliteľa dvoch čísel.