Oznamy

Cvičenia tento týždeň

  • Na začiatku cvičení v pondelok aj utorok sa na testovači objaví nová sada úloh.
  • Prvá úloha je rozcvička, treba ju odovzdať do konca cvičenia, začnite teda touto úlohou.
  • Zvyšok cvičenia riešte ďalšie úlohy.
  • Čo nestihnete na cvičení, môžete dokončiť doma.
  • Termín odovzdania je ďalší pondelok večer 22:00.
  • Úlohy sa dajú odovzdávať aj po termíne, ale nedostanete za ne body, ak sme vám neudelili výnimku.
  • Ak vám testovač k príkladu vypíše zelené OK, prešiel testami. Ak vypíše oranžový kód chyby, niečo je zle, treba opraviť a odovzdať znovu.
  • Do dnes večera 22:00 je možné odovzdávať aj úlohy z predchádzajúceho týždňa, ak ste ich nestihli odovzdať.

Opakovanie

Videli sme:

  • základy použitia funkcií printf a scanf na načítanie a výpis
  • premenné typu int, double, bool a operátory, ktoré s nimi vedia počítať
  • podmienku if
  • cyklus for

Tu je program, ktorý vypisoval čísla od 1 po n pre zadané n

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        printf(" %d", i);
    }
    printf("\n");
}

Ďalšie príklady na cyklus for

Výpočet faktoriálu

Nasledujúci program si od používateľa vypýta číslo n a vypočíta n!, t.j. súčin celých čísel od 1 po n.

#include <stdio.h>

int main() {
    int n;
    
    printf("Zadajte n: ");
    scanf("%d", &n);
    
    int vysledok = 1;
    for (int i = 1; i <= n; i++) {
       vysledok = vysledok * i;
    }
    
    printf("%d! = %d\n", n, vysledok);
}

Príklad behu programu pre n=4 (1*2*3*4=24):

Zadajte n: 4
4! = 24
  • Program používa premennú vysledok, ktorú na začiatku inicializuje hodnotou 1 a postupne ju násobí číslami 1, 2, …, n.
  • Riadok vysledok = vysledok * i; zoberie pôvodnú hodnotu premennej vysledok, vynásobí ju hodnotou premennej i (t.j. jedným z čísel 1, 2, …, n) a výsledok uloží naspäť do premennej vysledok (prepíše pôvodnú hodnotu). To isté sa dá napísať ako vysledok *= i;

Tento program ale funguje správne iba pre n<13, lebo n! veľmi rýchlo rastie a už pre n=13 sa výsledok nezmestí do premennej typu int. Dostávame nezmyselné hodnoty:

    12! = 479001600
    13! = 1932053504
    14! = 1278945280
    15! = 2004310016
    16! = 2004189184
    17! = -288522240

Správne hodnoty (ktoré možno získať zmenou typu premennej vysledok na long long int) sú:

    12! = 479001600
    13! = 6227020800
    14! = 87178291200
    15! = 1307674368000
    16! = 20922789888000
    17! = 355687428096000

(Aj typ long long int má však svoj limit, ktorý pri faktoriále rýchlo prekročíme.)

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

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 <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    // Inicializácia generátora pseudonáhodných čísel
    srand(time(NULL));
 
    int n;
    printf("Zadajte pocet hodov: ");
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        // Vygenerovanie a vypisanie hodu kockou
        printf("%d\n", rand() % 6 + 1);
    }
}

Príklad behu programu:

Zadajte pocet hodov: 5
2
6
1
2
1
  • 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 <stdlib.h>.
    • Výstupom funkcie rand() je 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 pre našu ukážku vytvorí dostatočný efekt náhodnosti.
    • Aby bolo možné použiť funkciu time, je treba do hlavičky pridať #include <time.h>.

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 <stdio.h>

int main() {
    int n;
    printf("Zadajte cislo: ");
    scanf("%d", &n);
    
    printf("Delitele cisla %d:", n);

    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            printf(" %d", i);
        }
    }    
    printf("\n");
}

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 často 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 pre C nejakým spôsobom odsadzovanie podporuje
  • 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++) {
    sucet += i;
}

je o dosť prehľadnejší ako

for(int i=1;i<=n;i++){sucet+=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 jazyku 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 ucet 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 <stdio.h>

int main(void) {
    double vklad, ciel, urok;
        
    printf("Zadaj kazdorocny vklad: ");
    scanf("%lf", &vklad);
    printf("Zadaj cielovu ciastku: ");
    scanf("%lf", &ciel);
    printf("Zadaj rocny urok (v %%): ");
    scanf("%lf", &urok);
    
    int rok = 0;
    double ucet = 0;
    
    while (ucet < ciel) {
        rok++;                   
        ucet = (ucet + vklad) * (1 + urok / 100);
        printf("Na konci roku %d je na ucte %lf EUR.\n", rok, ucet);
    }
}

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 <stdio.h>

int main() {
    int a, b;    
    printf("Zadaj dvojicu kladnych celych cisel: ");
    scanf("%d %d", &a, &b);
    
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    
    printf("Najvacsi spolocny delitel je %d.\n", a);
}

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?

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 <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

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

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

    while (!correct) {
        int guess;
        scanf("%d", &guess);
        if (guess < num) {
            printf("Prilis nizko. Iny tip: ");
        } else if (guess > num) {
            printf("Prilis vysoko. Iny tip: ");        
        } else {
            correct = true;
            printf("Spravne!\n");
        }
    }
}

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, nekonečný cyklus

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

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

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

#include <stdio.h>

int main() {
    while (true) {
        printf("Hello, World!\n");
    }
}

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 <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

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

    int num = rand() % 100 + 1;
    printf("Myslim si cislo od 1 po 100. Tvoj tip: ");
    
    while (true) {
        int guess;
        scanf("%d", &guess);
        if (guess < num) {
            printf("Prilis nizko. Iny tip: ");
        } else if (guess > num) {
            printf("Prilis vysoko. Iny tip: ");        
        } else {
            printf("Spravne!\n");
            break;
        }
    }
}

Viac o cykle for

Cyklus for sme zatiaľ používali iba základným spôsobom; jeho možnosti sú väčšie. 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++) {
    printf(" %d", i);
}

int i = 1;
while (i <= 9) {
    printf(" %d", 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 <stdio.h>

int main() {
    int n;
    printf("Zadajte cislo: ");
    scanf("%d", &n);
    
    printf("Delitele cisla %d:", n);
    for (int i = n; i >= 1; i--) {
        if (n % i == 0) {
            printf(" %d", i);
        }
    }
    printf("\n");
}

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 <stdio.h>

int main() {
    int n;
    printf("Zadajte cislo: ");
    scanf("%d", &n);
    
    printf("Delitele cisla %d:", n);
    for (int i = 1; i*i <= n; i++) {
        if (n % i == 0) {
            printf(" %d %d", i, n / i);
        }
    }
    printf("\n");
}

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; ) {
    printf("Hello, World!" "\n");
}

prípadne ako

for ( ; ; ) {
    printf("Hello, World!" "\n");
}

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 <stdio.h>

int main() {
    int n;  // pokial ma ist nasobilka
    scanf("%d", &n);
    for (int riadok = 1; riadok <= n; riadok++) {
        for (int stlpec = 1; stlpec <= n; stlpec++) {
            printf(" %d", riadok * stlpec);
        }
        printf("\n");
    }
}

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.