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

Príklad č. 1: 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(void) {
    srand(time(NULL)); // Inicializacia generatora pseudonahodnych cisel
 
    int n;
    cout << "Zadajte pocet hodov: ";
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cout << rand() % 6 + 1 << endl; // Vygenerovanie a vypisanie hodu kockou
    }
  
    return 0;
}

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 bod pseudonáhodnej postupnosti”, počnúc ktorým sa budú jej hodnoty generovať. 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>.

Príklad č. 2: 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(void) {
    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;
    return 0;
}

Príklad behu programu:

Zadajte cislo: 30
Delitelia 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.

Príklad č. 1: Vypisovanie čísel od 1 po n po druhé

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(void) {
    int n;
    cin >> n;
    
    int i = 1;            // Premenna i bude obsahovat aktualne vypisovane cislo; prve bude 1
    while (i <= n) {      // Kym je cislo i mensie ako n ...
        cout << " " << i; // ... vypis cislo i ...
        i++;              // ... a pokracuj cislom o 1 vacsim
    }
    cout << endl;
    
    return 0;
}

Príklad č. 2: Úroky v banke

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

Túto úlohu možno riešiť programom pracujúcim na báze nasledujúcej myšlienky:

• Na začiatku ubehlo nula rokov sporenia a na účte nie sú vložené žiadne peniaze.
• Následne v každom roku vložíme na účet pravidelný vklad; na konci roka sa úspory zúročia.
• Toto opakujeme, kým suma na účte 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: ";
    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;  
    }
    
    return 0;
}

Ukážkový vstup a výstup:

Zadaj kazdorocny vklad: 1000
Zadaj cielovu ciastku: 10000
Zadaj rocny urok: 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

Príklad č. 3: 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 niekedy možno stretnúť aj s označením 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í:

1. Ak a mod b = 0, tak gcd(a,b) = b.
2. Ak a mod b ≠ 0, tak gcd(a,b) = gcd(b, a mod b).

Dôkaz.

• Prvé tvrdenie je zrejmé, stačí dokázať druhé.
• 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. Zrejme stačí dokázať rovnosť X = Y.
• Ak označíme r := a mod b, tak existuje nezáporné celé číslo q také, že a = q b + r.
• Ak Syntaktická analýza (parsing) neúspešná (MathML (experimentálne): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in Y} , číslo x delí b aj r a z rovnosti a = q b + r vyplýva, že delí aj a. Teda Syntaktická analýza (parsing) neúspešná (MathML (experimentálne): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in X} .
• Ak naopak Syntaktická analýza (parsing) neúspešná (MathML (experimentálne): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in X} , číslo x delí a aj b a z rovnosti r = a - qb vyplýva, že delí aj r. Preto Syntaktická analýza (parsing) neúspešná (MathML (experimentálne): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in Y} .
• Dokázali sme teda, že platí Syntaktická analýza (parsing) neúspešná (MathML (experimentálne): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X \subseteq Y} a súčasne Syntaktická analýza (parsing) neúspešná (MathML (experimentálne): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X \supseteq Y} . Preto X = Y. ◻

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(void) {
    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;

    return 0;
}

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

Príklad č. 4: 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.