Prednáška 3

Oznamy

Od tohto týždňa budú cvičenia v náhradných miestnostiach F2-295 a F1-223 (v piatok iba F2-295). Prosím príďte do jednej z nich a ak je už plná, skúste druhú.

Budúci pondelok 2. októbra bude na časti prednášky teoretické cvičenie

• Budete písať krátky test zameraný na učivo z prvých troch prednášok
• Tento test sa počíta do druhých cvičení. Ak ich máte uznané z testu pre pokročilých, na test nemusíte ísť
• Na teste bude povolené používať pero a ťahák vo forme jedného obojstranne popísaného listu A4

Ciele teoretického cvičenia

• Precvičiť si poriadnejšie základné konštrukty
• Vynechaním časti prednášky vznikne väčší priestor precvičiť si základy
• Vyskúšať si prácu na papieri (bude treba na aj semestrálnom teste, ktorý má oveľa väčšiu váhu)

Prečo robíme toto cvičenie a písomné testy na papieri?

• Dobré na precvičenie porozumenia hotovým programom (treba na ďalších predmetoch aj pri štúdiu odbornej literatúry)
• Núti vás dobre si premyslieť každý detail, nie len náhodne skúšať meniť rôzne časti programu, kým nezačne fungovať
• Pri zložitejších programoch sa už nedá postupovať náhodne
• Na papieri miernejšie hodnotíme drobné chyby ako chýbajúca bodkočiarka, to vám na počítači pomôže nájsť kompilátor. Dôležitejšie je sa rozhodnúť, či má byť niekde napríklad i<n alebo i<=n.

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

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.

• číslo i delí číslo n práve vtedy, keď zvyšok po delení čísla n číslom i je 0

#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

Úprava a čitateľnosť programov

Pri písaní programov myslite na to, že ich typicky budú okrem počítača čítať aj ľudia (napríklad vy po dlhšom čase, učitelia, alebo kolegovia 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 }) 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 editorov a IDE pre C/C++ nejakým spôsobom odsadzovanie podporujú
• Voľné riadky: ucelené časti programu je kvôli prehľadnosti často dobré oddeliť prázdnym riadkom.
• Medzery: odporúča sa písať okolo operátorov medzery.
• Napríklad zápis

for (int i = 1; i <= n; i++) {
    a += i;
}

je o dosť prehľadnejší ako

for(int i=1;i<=n;i++){a+=i;}

• Dĺžka riadku: odporúča sa vyhýbať sa riadkom dlhším ako 80 znakov. 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.

Cyklus 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.

Ú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) = b pre každé kladné b.

• Euklidov algoritmus opakovane používa lemu: gcd(12,8) = gcd(8, 4) = gcd(4, 0) = 4
• Dostáva sa k stále menším číslam, až kým b neklesne na nulu

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

Cvičenie: Ako bude fungovať Euklidov algoritmus pre vstupné čísla 8, 30?

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ý uvidíme o chvíľu).

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

#include <iostream>
using namespace std;

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

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

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.

Hra „hádaj číslo” s príkazom break

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

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 výnimkou 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 1 až 9:

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

int i = 1;
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.

Vypisovanie deliteľov od najväčších

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 >= 1; i--)

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

#include <iostream>
using namespace std;

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

Príklad behu programu:

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

Rýchlejšie hľadanie deliteľov

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ď n/i je deliteľom čísla n.
• Čí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() {
    int n;
    cout << "Zadajte cislo: ";
    cin >> n;
    
    cout << "Delitele cisla " << n << ":";
    for (int i = 1; i*i <= n; i++) {
        if (n % i == 0) {
            cout << " " << i << " " << n / i;
        }
    }
    cout << endl;
}

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.

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.

Nekonečný cyklus možno teda napísať aj ako

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

prípadne ako

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

Vnorené cykly

Vypíšeme tabuľku násobilky, v ktorej bude v riadku i a stĺpci j súčin i ⋅ j.

• Použijeme dva vnorené cykly: jeden pôjde cez riadky, druhý cez stĺpce.

#include <iostream>
using namespace std;

int main() {
    int n;  // pokial ma ist nasobilka
    cin >> n;
    for (int riadok = 1; riadok <= n; riadok++) {
        for (int stlpec = 1; stlpec <= n; stlpec++) {
            cout << " " << riadok * stlpec;
        }
        cout << endl;
    }
}

Ukážka výstupu pre n=5:

 1 2 3 4 5
 2 4 6 8 10
 3 6 9 12 15
 4 8 12 16 20
 5 10 15 20 25

Ak pred každé číslo vypíšeme namiesto medzery " " tabulátor "\t", dostaneme krajší výstup

	1	2	3	4	5
	2	4	6	8	10
	3	6	9	12	15
	4	8	12	16	20
	5	10	15	20	25

Cvičenie: pridajme jednotlivým riadkom a stĺpcom hlavičku

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.