Oznamy

Čo nás čaká v najbližšom čase

  • Po prednáške bude na testovači zverejnené zadanie miniprojektu: väčšej úlohy na dlhší čas a viac bodov.
  • Dnes algoritmy s poliami.
  • Na cvičeniach dnes a zajtra príklady na polia, vrátane rozcvičiek (pri počítači).
  • Za rozcvičky môžete tento týždeň dostať bonusový bod, ak ich na testovač odovzdáte na prvýkrát dobre.
    • Cieľom je, aby ste si precvičili kompilovanie a spúšťanie programu a kontrolu jeho výstupov.

Prebrali sme premenné, polia, podmienky, cykly a funkcie.

  • Z týchto stavebných prvkov sa dajú vystavať pomerne komplikované programy.
  • Menej skúsení programátori si potrebujú prácu s týmito pojmami čo najviac precvičiť. Skúste vyriešiť všetky príklady z cvičení, pracujte na miniprojekte.
    • Neodpisujte, nič sa tým nenaučíte.
    • Kontaktujte nás, ak potrebujete pomôcť.

Parametre funkcií: opakovanie

Jednoduché typy, napr. int, double, bool: skopíruje sa hodnota do novej lokálnej premennej vo funkcii. Zmeny sa neprenesú do volajúcej funkcie.

#include <stdio.h>
void f1(int x) {
    x++; // zmena x sa neprenesie do main (y zostane rovnaká)
    printf("x: %d\n", x);
}

int main(void) {
    int y = 0;
    printf("y: %d\n", y);
    f1(y);
    printf("y: %d\n", y);
    f1(y + 1);
    printf("y: %d\n", y);
}

Funkcie a polia

  • Keď do funkcie posielame pole, nerobí sa jeho kópia.
  • Zmeny prvkov v poli zostanú aj po skončení funkcie.
  • V hlavičke funkcie sa pole uvádza ako int a[].
  • Väčšinou potrebujeme poslať do funkcie aj veľkosť poľa v zvláštnej premennej.

V nasledujúcom programe

  • funkcia sucet spočíta súčet prvkov poľa a s n prvkami
  • funkcia prepis prepíše všetky prvky poľa a s n prvkami hodnotou x
  • funkcia main vytvorí pole b, zavolá funkcie sucet na pôvodné pole, zmení pole pomocou prepis a znovu spočíta súčet.
#include <stdio.h>
int sucet(int a[], int n) {
    int sucet = 0;
    for (int i = 0; i < n; i++) {
        sucet += a[i];
    }
    return sucet;
}

int prepis(int a[], int n, int x) {
    for (int i = 0; i < n; i++) {
        a[i] = x;
    }
}

int main() {
    int b[3] = {1, 2, 3};
    printf("Sucet: %d\n", sucet(b, 3));
    prepis(b, 3, 10);
    printf("Sucet: %d\n", sucet(b, 3));
}

Funkcie a polia: načítanie a vypísanie poľa

Dve základné funkcie, ktoré sa nám môžu zísť v programoch

  • precvičíme si tiež ako sa pracuje s poliami vo funkciách
#include <assert.h>
#include <stdio.h>

int readArray(int a[], int maxSize) {
    /* Od užívateľa načíta počet vstupných čísel. 
     * Potom načíta zadaný počet celých čísel a uloží ich do poľa a,
     * Hodnota maxSize je veľkosť poľa,
     * ktorú nemožno prekročiť.
     * Funkcia vráti počet načítaných čísel. */

    int n;
    scanf("%d", &n);
    assert(n <= maxSize);
    for (int i = 0; i < n; i++) {
        scanf("%d", &(a[i]));
    }
    return n;
}

void printArray(int a[], int n) {
   for (int i = 0; i < n; i++) {
       printf(" %d", a[i]);
   }
   printf("\n");
}

#define NMAX 100

int main() {
    int a[NMAX];

    int n = readArray(a, NMAX);

    // tu môžeme pole nejako upraviť

    printArray(a, n);
}

Triedenia

Máme pole čísel, chceme ich usporiadať od najmenšieho po najväčšie.

  • Napr. pre pole 9 3 7 4 5 2 chceme dostať 2 3 4 5 7 9
  • Jeden z najštudovanejších problémov v informatike.
  • Súčasť mnohých zložitejších algoritmov.
  • Veľa spôsobov, ako triediť, dnes si ukážeme zopár najjednoduchších.

Pomocná funkcia swap

Dostane pole a dva indexy a vymení hodnoty prvkov na týchto indexoch.

  • Zíde sa pri triedení.
  • Potrebujeme pomocnú premennú, kam si dočasne uložíme jednu z hodnôt, aby sme ju nestratili.
void swap(int a[], int i, int j) {
    /* Vymeň hodnoty prvkov v poli a na pozíciách i a j. */
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

Bublinkové triedenie (Bubble Sort)

Idea: Kontrolujeme všetky dvojice susedných prvkov a keď vidíme menšie číslo za väčším, vymeníme ich

for (int i = 1; i < n; i++) {
     if (a[i] < a[i - 1]) {
         swap(a, i - 1, i);
     }
}
  • Ak sme nenašli v poli žiadnu dvojicu, ktorú treba vymeniť, skončili sme.
  • Inak celý proces opakujeme znova.

Celé triedenie:

void sort(int a[], int n) {
    /* usporiadaj prvky v poli a od najmenšieho po najväčší */

    bool hotovo = false;
    while (!hotovo) {
        bool vymenil = false;
        /* porovnávaj všetky dvojice susedov, 
           vymeň ak menší za väčším */
        for (int i = 1; i < n; i++) {
            if (a[i] < a[i - 1]) {
                swap(a, i - 1, i);
                vymenil = true;
            }
        }
        /* ak sme žiadnu dvojicu nevymenili, 
           môžeme skončiť. */
        if (!vymenil) {
            hotovo = true;
        }
    }
}
  • Čo ak vo for cykle dáme for (int i = 0; i < n; i++) { ?
  • Ako nahradíme premennú hotovo príkazom break?

Príklad behu:

prvá iterácia while cyklu
 9 3 7 4 5 2
 3 9 7 4 5 2
 3 7 9 4 5 2
 3 7 4 9 5 2
 3 7 4 5 9 2
 3 7 4 5 2 9

druhá iterácia while cyklu
 3 7 4 5 2 9
 3 4 7 5 2 9
 3 4 5 7 2 9
 3 4 5 2 7 9

tretia iterácia while cyklu
 3 4 5 2 7 9
 3 4 2 5 7 9

štvrtá iterácia while cyklu
 3 4 2 5 7 9
 3 2 4 5 7 9

piata iterácia while cyklu
 3 2 4 5 7 9
 2 3 4 5 7 9

Cvičenie: Ako sa bude správať algoritmus na nasledujúcich vstupoch, koľkokrát zopakuje vonkajší while cyklus?

  • Utriedené pole 1,2,…,n
  • Pole n,1,2,…,n-1
  • Pole 2,3,…,n,1
  • Pole n,n-1,…,1

Triedenie výberom (selection sort, max sort)

Idea: nájdime najväčší prvok a uložme ho na koniec. Potom nájdime najväčší medzi zvyšnými a uložme ho na druhé miesto odzadu atď.

  • V cykle uvádzame ako komentár invariant, podmienku, ktorá na tom mieste vždy platí. Takýto invariant nám pomôže si uvedomiť, že je náš program správny.
int maxIndex(int a[], int n) {
    /* vráť index, na ktorom je najväčší prvok 
       z prvkov a[0]...a[n-1] */
    int index = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[index]) {
            index = i;
        }
        /* invariant: a[j] <= a[index] pre vsetky j=0,...,i*/
    }
    return index;
}

void sort(int a[], int n) {
    /* usporiadaj prvky v poli a od najmenšieho po najväčší */

    for(int kam = n - 1; kam >= 1; kam--) {
        /* invariant: a[kam+1]...a[n-1] sú utriedené
         * a pre každé i,j také že 0<=i<=kam, kam<j<n 
         * platí a[i]<=a[j] */
        int index = maxIndex(a, kam + 1);
        swap(a, index, kam);
    }
}

Príklad behu programu

Vstup           9 3 7 4 5 2 
Po výmene (9,2) 2 3 7 4 5 9
Po výmene (7,5) 2 3 5 4 7 9
Po výmene (5,4) 2 3 4 5 7 9
Po výmene (4,4) 2 3 4 5 7 9
Po výmene (3,3) 2 3 4 5 7 9

Cvičenie: Bude čas behu algoritmu výrazne odlišný pre pole utriedené správne a pole utriedené v opačnom poradí?

Triedenie vkladaním (Insertion Sort)

Idea:

  • v prvej časti poľa prvky v utriedenom poradí
  • zober prvý prvok z druhej časti a vlož ho na správne miesto v utriedenom poradí

Príklad behu algoritmu:

 9 3 7 4 5 2
 3 9 7 4 5 2
 3 7 9 4 5 2
 3 4 7 9 5 2
 3 4 5 7 9 2
 2 3 4 5 7 9

Ako spraviť vkladanie:

  • Vkladaný prvok si zapamätáme v pomocnej premennej prvok
  • Utriedené prvky posúvame o jedno doprava, kým nenájdeme správne miesto pre odložený prvok
void sort(int a[], int n) {
    /* usporiadaj prvky v poli a od najmenšieho po najväčší */

    for (int i = 1; i < n; i++) {
        int prvok = a[i];
        int kam = i;
        while (kam > 0 && a[kam - 1] > prvok) {
            a[kam] = a[kam - 1];
            kam--;
        }
        a[kam] = prvok;
    }
}
  • Všimnime si podmienku (kam > 0 && a[kam - 1] > prvok)
    • Ak kam je 0, prvá časť je false, druhá časť sa už nevyhodnocuje
    • Ak by sme prehodili časti, program by mohol spadnúť (a[kam - 1]> prvok && kam > 0)

Cvičenie: Ako sa bude správať algoritmus na nasledujúcich vstupoch, koľkokrát zopakuje priradenie a[kam] = a[kam - 1]?

  • Utriedené pole 1,2,…,n
  • Pole n,1,2,…,n-1
  • Pole 2,3,…,n,1
  • Pole n,n-1,…,1

Triedenia: zhrnutie

  • Videli sme tri jednoduché algoritmy na triedenie
  • Celý program s triedeniami je na zvláštnej stránke

  • Neskôr sa naučíme rýchlejšie algoritmy na triedenie, ktoré používajú rekurziu

  • Precvičili sme si funkcie, parametre a polia
  • K funkciám je dobré napísať, čo robia
  • Do cyklov si môžeme písať invarianty
    • Používajú sa pri formálnom dokazovaní správnosti
    • Pomáhajú pochopeniu kódu
    • Môžeme ich použiť na ručnú alebo automatickú kontrolu správnosti hodnôt premenných
    • Príkaz assert v knižnici assert.h kontroluje podmienku, napr. assert(i>=0 && i<n); ukončí program s chybovou hláškou ak podmienka neplatí

Cvičenie:

  • Na vstupe je postupnosť N celých čísel. Zistite, či sa v nej nachádza nejaké číslo viackrát.
  • Viete pri tom použiť triedenie?

Eratostenovo sito

  • Prvočíslo je prirodzené číslo väčšie ako 1, ktoré je deliteľné len samo sebou a číslom 1.
  • Chceli by sme nájsť všetky prvočísla medzi 2 a n.
  • Napríklad ak n=30, výsledok má byť 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Mohli by sme ísť cez všetky čísla a pre každé testovať, koľko má deliteľov (deliteľov sme už hľadali predtým), ale vieme to spraviť aj rýchlejšie. Použijeme algoritmus zvaný Eratostenovo sito.

  • Vytvoríme pole a pravdivostných hodnôt, kde a[i] nám hovorí, či je i ešte potenciálne prvočíslo.
  • Na začiatku budú všetky hodnoty true, lebo sme ešte žiadne číslo nevylúčili.
  • Začneme číslom 2. Toto je iste prvočíslo, tak ho vypíšeme. O jeho násobkoch však vieme, že iste nemôžu byť prvočísla. Nastavíme preto pre každý násobok j=2*k pravdivostnú hodnotu a[j] na false.
  • Potom prechádzame v poli, kým nenájdeme najbližšiu ďalšiu hodnotu true. Toto číslo je prvočíslo, teda ho vypíšeme a vyškrtáme jeho násobky.
#include <stdio.h>
#include <stdbool.h>

#define N 30

int main() {
    bool a[N + 1];

    for (int i = 2; i <= N; i++) {
         a[i] = true;
    }
    for (int i = 2; i <= N; i++) {
        if (a[i]) {
            printf("%d ", i);
            for (int j = 2 * i; j <= N; j = j + i) {
                a[j] = false;
            }
        }
    }
    printf("\n");
}

Výstup programu

2 3 5 7 11 13 17 19 23 29

Priebeh programu:

0  1  2  3  4  5  6  7  8  9 10 11 12 ...
?  ?  T  T  T  T  T  T  T  T  T  T  T ... na zaciatku
?  ?  T  T  F  T  F  T  F  T  F  T  F ... po vyskrtani i=2
?  ?  T  T  F  T  F  T  F  F  F  T  F ... po vyskrtani i=3
?  ?  T  T  F  T  F  T  F  F  F  T  F ... dalej sa uz skrtaju len vacsie cisla

Cvičenie: Napíšte funkciu, ktorá uloží prvočísla medzi 2 a N do zadaného poľa (ak by sme ich chceli použiť na ďalšie výpočty) a vráti ich počet.