Prednáška 7

Oznamy

• Začiatok semestra je pre začiatočníkov ťažký, ale programovať sa naučíte len riešením čo najväčšieho počtu príkladov
• Bez dobrej znalosti cyklov, podmienok, premenných, polí a funkcií nebudete rozumieť ďalšiemu učivu a nespravíte skúšku
• Snažte sa každý týždeň vyriešiť čo najviac príkladov
• Pred cvičením si pozrite poznámky z prednášok
• Dobre si prečítajte zadanie, vrátane príkladu vstupu a výstupu
  • Cieľom príkladu vstupu je aj lepšie ilustrovať zadanie. Skúste si skontrolovať, ako sa asi výstup vypočítal zo vstupu.
• Najskôr si vymyslite postup, ako idete úlohu riešiť. Vytiahnite si papier na poznámky a náčrtky.

Domáca úloha do pondelka 24.10.

• Preštudujte si zadanie, pýtajte sa otázky
• K úlohe sa vám môže hodiť pozrieť si video z konca prednášky 5 o knižnici SVGdraw a o ukladaní struct-ov do poľa
• Časť bodov môžete dostať aj za neúplný program, začnite od jednoduchších častí, napr. načítanie vstupu a uloženie do poľa, vykreslenie mnohouholníka a bodov jednotnou farbou
• Potom môžete prejsť na počítanie priesečníka a správne nastavovanie farieb v obrázku
• Úloha je dobrá príležitosť precvičiť si doteraz preberanú látku
• Každá domáca úloha má váhu 5% známky, t.j. zhruba ako dva týždne cvičení

• Ak ste v utorok na cvičení vyriešili len 1-2 príklady, odporúčame prísť v piatok na cvičenia

Ďalšie prednášky

• Dnes ešte algoritmy, znaky, v pondelok reťazce (ďalšie precvičenie polí a funkcií, trochu nových pojmov z C)
• Budúcu stredu začneme rekurziu, potenciálne ťažké učivo

Budúci týždeň cvičenia v špeciálnom režime

• Budúci utorok rozcvička a zopár príkladov na znaky a reťazce
• Budúcu stredu po prednáške pribudne 1 menší príklad na rekurziu, v piatok bude opäť bonusová rozcvička na rekurziu
• Odporúčame budúci týždeň na doplnkové cvičenia prísť aj stredne pokročilým programátorom, ak ste ešte nerobili s rekurziou

Vyhľadávanie prvkov poľa

Chceme zistiť, či pole obsahuje prvok zadanej hodnoty.

• Musíme prejsť celé pole, lebo nevieme, kde sa prvok môže nachádzať.
• Tento algoritmus sa nazýva lineárne vyhľadávanie

/* Funkcia find vráti index výskytu prvku x
 * v poli a. Ak sa x v poli nevyskytuje, vráti -1.
 * Hodnota n určuje počet prvkov poľa. */
int find(int a[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (a[i] == x) return i;
    }
    return -1;
}

• Toto môžeme urobiť aj v prípade, že máme pole usporiadané.
• Ale neexistuje lepšie riešenie?

Binárne vyhľadávanie v utriedenom poli

Ak porovnáme hľadanú hodnotu x s nejakým prvkom utriedeného poľa a[i], môžu nastať tri možnosti:

• ak sme trafili pozíciu i takú, že x==a[i], máme odpoveď a môžeme skončiť s vyhľadávaním
• ak x < a[i], tak všetky prvky a[j] napravo od pozície i budú určite tiež väčšie ako x a teda ich nemusíte ďalej uvažovať, stačí hľadať vľavo od i
• ak x > a[i], tak všetky prvky a[j] naľavo od pozície i budú určite tiež menšie ako x a teda ich nemusíte ďalej uvažovať, stačí hľadať vpravo od i

Binárne vyhľadávanie v utriedenom poli teda pracuje nasledovne:

• pamätáme si ľavý a pravý okraj intervalu, kde ešte môže byť hľadaný prvok x
• vyberieme prvok a[index] v strede tohoto intervalu, teda index=(left+right)/2
• na základe porovnania s hľadaným prvkom x interval skrátime na polovicu
• ak už je interval zlý (t.j. pravý a ľavý kraj sú naopak), tak skončíme

int find(int a[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int index = (left + right) / 2;
        if (a[index] == x) {
            return index;
        }
        else if (a[index] < x) {
            left = index + 1;
        }
        else {
            right = index - 1;
        }
    }
    return -1;
}

Ukážka práce algoritmu pre dva vstupy

int a[7]={2,5,21,32,38,45,50}
x=21
   left=0 right=6: index=3; A[index]>x (32>21)
   left=0 right=2; index=1; A[index]<x (5<21)
   left=2 right=2; index=2; A[index]=x -> return 2
x=11
   left=0 right=6: index=3; A[index]>x (32>11)
   left=1 right=2; index=1; A[index]<x (5<11)
   left=2 right=2; index=2; A[index]>x (21>11)
   left=2 right=1; left>right           -> koniec while cyklu -> return -1

Intuitívne máme pocit, že binárne vyhľadávanie je lepšie, ako lineárne.

Zložitosť algoritmu

Ako sme videli napríklad pri triedení a vyhľadávaní, jednu úlohu môžeme často riešiť viacerými spôsobmi. Intuitívne máme o niektorých pocit, že sú lepšie ako iné. Pozrime sa, prečo sú niektoré riešenia lepšie a ako môžeme niečo také odhadovať.

Časová zložitosť lineárneho vyhľadávania

Často nás zaujíma, ako rýchlo nám program bude bežať. Väčšinou táto rýchlosť nejako závisí od vstupných dát. Iste bude kratšie trvať triedenie trojprvkového poľa ako poľa s milión prvkami. Časovú zložitosť teda budeme odhadovať v závislosti od veľkosti vstupu.

Pre niektoré programy môžeme spočítať počet operácií, ktoré program vykoná na vstupoch veľkosti n.

• Ukážme si túto metódu pre lineárne vyhľadávanie v neutriedenom poli

int find(int a[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (a[i] == x) return i;
    }
    return -1;
}

• Najmenej operácií spravíme, ak x je v a[0]
• Vtedy spravíme 4 kroky: i=0, i<n, a[i]==x, return i (závisí aj od toho, čo presne považujeme za "jeden krok")
• Najviac operácií spravíme, ak sa x v poli nenachádza
• Vtedy spravíme raz i=0, (n+1) krát i<n, n krát i++, n krát a[i]==x, raz return -1, spolu 3n+3 krokov
• Celkový počet krokov bude teda niečo medzi 4 a 3n+3

Vo väčších programoch však toto rozmedzie nie je jednoduché vypočítať.

• Preto uvažujeme väčšinou iba najhorší prípad, ktorý môže nastať
• Okrem toho nás nezaujímajú presné čísla, ale iba akýsi odhad (približná funkcia) závislá od vstupu.
• Pri lineárnom vyhľadávaní je v najhoršom prípade počet krokov lineárna funkcia od n, vravíme teda, že tento algoritmus má lineárnu zložitosť, značíme O(n)
• Presnú definíciu O uvidíte budúci rok na predmete Algoritmy a dátové štruktúry

Časová zložitosť binárneho vyhľadávania

• Najhorší možný scenár pre danú veľkosť vstupu n nastane, keď prvok nájdeme až v poslednom kroku alebo v poli nebude vôbec.
• V prvom kroku máme celé pole a v ňom sa pozrieme na stredný prvok a podľa jeho hodnoty zoberieme buď ľavú alebo pravú (zhruba) polovicu poľa.
• Tým pádom v druhom kroku máme pole polovičnej veľkosti a robíme na ňom zase to isté.
• V každom kroku teda máme pole o polovicu menšie, až kým nemáme pole veľkosti 1. Potom už prvok nájdeme alebo v ďalšom kroku povieme, že tam nie je.
• Akú zložitosť bude mať tento algoritmus?
  • Zapíšeme si číslo n (počet prvkov) v dvojkovej sústave.
  • Pri delení poľa na polovicu bude ďalšia veľkosť poľa toto číslo bez poslednej cifry.
  • Počet krokov, ktoré potrebujeme, je teda zhruba počet cifier n v dvojkovej sústave, čo je log₂ n.
• Vravíme teda, že zložitosť binárneho vyhľadávania je logaritmická, značíme O(log n)
• Logaritmus rastie pre veľké n oveľa pomalšie ako lineárna funkcia, čiže binárne vyhľadávanie považujeme za efektívnejší algoritmus ako lineárne vyhľadávanie
  • pozor, neplatí to však pre každý vstup, iba pre porovnanie najhorších prípadov pre dosť veľké n

Pre ilustráciu som na mojom počítači namerala, koľko sekúnd v priemere trvá lineárne a binárne vyhľadávanie v poli s n číslami:

n       lineárne binárne
10      3.1e-8   3.7e-8
100     2.0e-7   6.9e-8
1000    1.8e-6   1.0e-7
10000   1.8e-5   1.4e-7
100000  1.8e-4   1.8e-7
1000000 1.8e-3   2.4e-7

Pripomíname, že napr. 1.8e-3 je 1.8 ⋅ 10^-3, t.j. 0.0018. Pri hľadaní v poli dĺžky 10 je teda lineárne vyhľadávanie rýchlejšie, ale v poli dĺžky milión je už vyše 7000 krát pomalšie...

Časová zložitosť triedenia vkladaním

Triedenie vkladaním (Insertion sort) z minulej prednášky

• Pripomíname ideu: prvých i prvkov máme utriedených, prvok a[i] sa snažíme vložiť na správne miesto
• Na to musíme posunúť všetky väčšie prvky o jedna doprava, aby sme mu spravili miesto

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 najhoršom prípade pre dané i bude a[i] menšie ako všetky doteraz utriedené prvky a teda while cyklus bude bežať i krát
• Ak je pole na začiatku usporiadané naopak, t.j. od najväčšieho prvku po najmenší, tento najhorší prípad nastane pri každej hodnote i
• Teraz si už iba spočítame: pre i=1 posúvame 1 prvok, pre i=2 dva prvky, ..., pre i=n-1 posúvame n-1 prvkov
• Teda čas, ktorý na to potrebujeme je 1+2+...+(n-1) = n(n-1)/2 = n²/2-n/2.
• Zložitosť tohto triedenia bude teda kvadratická, čiže O(n²)

• Bude sa však správať rovnako (kvadraticky) na všetkých vstupoch? Čo ak dostaneme na vstupe pole už správne utriedené?

Ostatné triedenia z prednášky (výberom a bublinkové) majú tiež v najhoršom prípade kvadratickú zložitosť

• Premyslite si prečo
• Ako dlho im to potrvá v najlepšom prípade?

Existujú však aj triedenia s časovou zložitosťou O(n log n), ako uvidíme neskôr v semestri

Cvičenie:

• Na vstupe máme n čísel usporiadaných od najmenšieho po najväčšie a číslo x, chceme zistiť, či sa x nachádza medzi n číslami
• Načítame čísla do poľa a spustíme lineárne alebo binárne vyhľadávanie
• Aká bude časová zložitosť týchto dvoch verzií programu?
• Čo ak nechceme vyhľadávať jednu hodnotu x, ale m rôznych hodnôt?
• Čo ak nie sú čísla na vstupe utriedené a pred binárnym vyhľadávaním musíme najskôr triediť?

Znaky

Doteraz sme pracovali iba s číselnými dátami, ale pri programovaní často pracujeme z reťazcami (textami).

• Reťazce budú na ďalšej prednáške, dnes si ukážeme, ako pracovať s ich jednotlivými súčasťami, znakmi (písmená, čísla, medzery,...)

• Znakové konštanty sa zapisujú v apostrofoch, napr. 'A', '1', ' ' a pod.
• Znakové premenné sú typu char, z anglického character. Ich veľkosť je spravidla 1 bajt, t.j. 8 bitov.

Znaky majú svoje kódy uvedené v tabuľke ASCII. Najbežnejšie sa budeme stretávať s týmito:

• 48...57: '0'...'9'
• 65...90: 'A'...'Z'
• 97...122: 'a'...'z'
• 32: medzera ' '
• 9: tabulátor '\t'
• 10: koniec riadku '\n'
• 0: špeciálny nulový znak (uvidíme nabudúce) '\0'

Poznámky

• bežné znaky z US klávesnice sú v rozsahu 0..127 (7 bitov)
• nakoľko char je 8-bitový, môže ešte nadobúdať hodnoty -1 ... -128 alebo 128..255 podľa kompilátora
• moderný softvér väčšinou namiesto klasických 8-bitových znakov používa Unicode, aby sa dali reprezentovať aj rôzne špeciálne symboly, znaky s diakritikou, jazyky nepoužívajúce latinku a pod.
• na tomto predmete si vystačíme s klasickými znakmi v rozsahu 0..127

Do premennej typu char môžeme priraďovať, jej obsah zapísať alebo prečítať:

  char c='A';
  char z;
  z=c;
  cout << c;
  cin >> z;  // prečíta jeden znak (pozor, preskakujú sa biele znaky)

Znaky môžeme porovnávať. Na konci programu vyššie platí nasledovné:

• c=='A' ... je pravda,
• c=='a' ... nie je pravda – rozlišujú sa malé a veľké písmená,
• c<='Z' ... je pravda – písmená sú usporiadané: A<B< ... <Z, a<b< ... <z, aj cifry sú usporiadané: 0<1< ... <9.

Pri čítaní zo vstupu pomocou cin do premennej typu char sa preskakujú tzv. biele znaky (napr. medzera, tabulátor, koniec riadku).

• Toto nie je vždy žiadúce a preto môžeme použiť modifikátor noskipws, ktorý zruší preskakovanie takýchto znakov. Do premennej teda budeme vedieť prečítať aj medzeru.

#include <iostream>
using namespace std;

int main(void) {
  char a,b,c; 
  cin >> noskipws >> a >> b >> c;
  cout << a << b << c;
}

Hodnota jednoduchého výrazu

Nasledujúci program spočíta hodnotu jednoduchého výrazu, ktorý pozostáva z dvoch čísel spojených znamienkom +, -, * alebo /. Okolo sú medzery (kvôli jednoduchšiemu načítaniu).

Napr. pre vstup 1 / 2 program vypíše 0.5.

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

int main(void) {
    double a, b;
    char znamienko;
    cin >> a >> znamienko >> b;
    double vysledok;
    if (znamienko == '+') {
        vysledok = a + b;
    }
    else if (znamienko == '-') {
        vysledok = a - b;
    }
    else if (znamienko == '*') {
        vysledok = a * b;
    }
    else if (znamienko == '/') {
        vysledok = a / b;
    } else {
        cout << "zle znamienko " << znamienko << endl;
        exit(1);
    }
    cout << vysledok << endl;
}

Switch

• V predchádzajúcom programe bola pomerne dlhá a komplikovaná séria príkazov if, else
• Namiesto toho sa dá použiť príkaz switch, ktorý podľa hodnoty výrazu pokračuje jednou z viacerých vetiev.

V našom jednoduchom príklade by mohol switch vyzerať nasledovne:

    switch (znamienko) {
    case '+' :
        vysledok = a + b;
        break;
    case '-' :
        vysledok = a - b;
        break;
    case '*' :
        vysledok = a * b;
        break;
    case '/' :
        vysledok = a / b;
        break;
    default:
        cout << "zle znamienko " << znamienko << endl;
        exit(1);
    }

Vo všeobecnosti obsahuje príkaz switch viacero rôznych prípadov vyhodnotenia výrazu v podmienke.

switch (výraz)
{
case k1: príkazy1
case k2: príkazy2
default: príkazyd
}

Takýto príkaz funguje nasledovne:

• Vyhodnotí výraz.
  • Ak sa hodnota zhoduje s konštantným výrazom ki v niektorom z prípadov, pokračuje časťou príkazyi
  • Ak sa nezhoduje a máme vetvu default, pokračuje sa časťou prikazyd
  • Ak nie je vetva default, pokračuje sa za koncom switch bloku.
• Pozor: Na rozdiel od pascalovského case, vykonávanie nekončí vykonaním posledného príkazu v prikazyi, ale pokračuje ďalej, kým nie je prerušené príkazom break.
  • Toto je častá chyba pri použití príkazu switch

#include <iostream.h>

void main () {
  int n;
  cout << "Zadaj n (1,2,3,4): ";
  cin >> n;
  switch (n) {
    case 1: cout << "Jeden" << endl;
    case 2: cout << "Dva" << endl;
    case 3:
    case 4: cout << "Tri alebo styri" << endl;
    default: cout << "Chyba!" << endl;
  }
  cout << "Koniec." << endl;
}

Pre n=2 sa začnú vykonávať príkazy uvedené za vetvou case 2:. Vypíše sa:

    Dva
    Tri alebo styri
    Chyba!
    Koniec.

Výhodou je, že môžeme zlúčiť viacero prípadov do jednej vetvy tým, ze príkazy napíšeme až za posledný prípad (tu vidíme napr. v situácii n=3 a n=4).

Dôležité upozornenie: break switch while

Predstavme si, že v programe sa pýtame užívateľa, či chce pokračovať s ďalším vstupom, pričom odpoveď má byť znak 'A' alebo 'N'. Ak by sme program napísali takto, nefungoval by:

    while (true) {
        // nejaky vypocet
        cout << "Chcete pokracovat? (Zadajte odpoved A alebo N)" << endl;
        char odpoved;
        cin >> odpoved;
        switch (odpoved) {
        case 'N':
            break;
        // spracovanie inych pripadov...
        }
    }

• Príkaz break nevyskočí zo všetkých cyklov, ale iba z najvnútornejšieho - a tým je v tomto prípade switch. Program teda pokračuje aj keď užívateľ zadá 'N'.
• Ak by break bol použitý s podmienkou, všetko by fungovalo: while (true) { ... if (odpoved=='N') { break; } }

Ešte znaky

Pretypovanie

Znakové premenné teda ukladajú kódy jednotlivých znakov, čo sú celé čísla.

• Preto medzi znakmi a celými číslami môžeme prechádzať jednoducho (char môžeme priradiť do int a naopak, s char môžeme tiež robiť aritmetické operácie, pozor jedine na malý rozsah char-u)
• Ale pri výpise sa výraz typu char vypisuje ako znak podľa ASCII tabuľky, výraz typu int ako číslo, niekedy teda treba pretypovať
• Podobne vstup sa inak spracúva, ak ide do premennej char vs int.

#include<iostream>
using namespace std;

int main(void) {
  int i;
  char c;

  c = 'A';             // to iste ako c = 65
  cout << c << endl;   // vypise A
  cout << c+1 << endl; // vypise 66 (c+1 je typu int)
  cout << (char)(c+1) << endl; // pretypujeme, vypise B

  cout << "Napiste cifru 0-9: ";
  cin >> c;  
  // ak pouzivatel zada 0, do c sa ulozi '0', t.j. 48

  cout << "Napiste cifru 0-9: ";
  cin >> i;  
  // ak pouzivatel zada 0, do i sa ulozi hodnota 0

  cout << c << " " << (int)c << endl;
  cout << i << " " << (char)i << endl;
}