Prednáška 5

Oznamy

• DÚ1 bude zverejnená pravdepodobne dnes večer
• Budúcu stredu večer test
• Príďte na dnešné doplnkové cvičenia, ak sa vám včera nepodarilo vyriešiť veľa príkladov. Pomôžeme vám s ďalšími príkladmi na tento týždeň
• Skúste si niektoré príklady vyriešiť najskôr na papieri ako tréning na test
• Dnes polia (nebudú na teste), budúci pondelok hlavne ďalšie príklady a algoritmy s použitím tých častí Cčka, ktoré už poznáte

Štatistika z N čísel

Od užívateľa postupne načítame N čísel a chceme o nich zistiť nejaké štatistické údaje.

• Predstavme si napríklad, že učiteľ zadá body, ktoré študenti dostali na písomke.

Maximum

Zrejme stačí čítať čísla postupne a pamätať si zatiaľ najväčšie číslo.

#include <iostream>
#include <cstdlib>

using namespace std;

int main(void) {
    int max, x, N;

    cout << "Zadaj pocet cisel: ";
    cin >> N;

    cout << "Zadavajte cisla: ";

    max = ?
    for (int i = 0; i < N; i++) {
        cin >> x;
        if (x > max) {
            max = x;
        }
    }

    cout << endl << "Maximum je " << max << endl;
}

Ako ale začať? Ako nastaviť maximum na začiatok?

• Jedna možnosť je nastaviť ho na nejakú veľmi malú hodnotu, aby sa iste neskôr zmenila. Kto nám ale zaručí, že používateľ nedá všetky čísla ešte menšie?
• Riešením je použiť najmenšie možné číslo - ale je príliš viazané na konkrétny rozsah, nebude fungovať po zmene typu premenných.
• Ďalšia možnosť je si pamätať, že ešte nemáme správne nastavené maximum a po načítaní prvého čísla ho nastaviť.

#include <iostream>
#include <cstdlib>

using namespace std;

int main(void) {
    int max, x, N;

    cout << "Zadaj pocet cisel: ";
    cin >> N;

    cout << "Zadavajte cisla: ";
    cin >> x;

    max = x;
    for (int i = 1; i < N; i++) {
        cin >> x;
        if (x > max) {
            max = x;
        }
    }

    cout << endl << "Maximum je " << max << endl;
}

Cvičenie:

• Ako by sme program rozšírili tak, aby vedel vypísať aj koľké číslo v poradí bolo najväčšie?
• Čo treba v programe zmeniť, ak chceme hľadať minimum namiesto maxima?
• Ako by sme spočítali priemer čísel?

Výskyty čísel 0...9

Na vstupe sú iba čísla od 0 do 9 a chceme vedieť, koľkokrát sa jednotlivé čísla na vstupe vyskytli. Mohli by sme to riešiť takto:

• Pre každú hodnotu 0...9 si vytvoríme jednu premennú (napríklad p0, p1, ..., p9) na začiatku nastavenú na 0.
• V prípade, že prečítané číslo bolo 0 zväčšíme hodnotu p0, ak bolo 1 zväčšíme p1 ...

Bol by to dlhý a komplikovaný program, v ktorom sa ľahko spraví chyba. Už vôbec by nebolo praktické to robiť takto, ak by hodnoty boli od 0 po milión...

• To, že štvrtá premenná je p4, vieme iba my ako programátori a počítač o tom nevie - nemá žiaden súvis medzi jednotlivými premennými.

Teraz ukážeme riešenie tohto príkladu pomocou poľa.

• int p[10] vytvorí pole dĺžky 10, t.j. tabuľku s prvkami p[0], p[1],..., p[9]
• s každým p[i] môžeme pracovať ako s premennou typu int

#include <iostream>
using namespace std;

int main(void) {
    int p[10];  // pole dlzky 10
    int N;
    cout << "Zadajte pocet cisel: ";
    cin >> N;

    for (int i = 0; i < 10; i++) {
       p[i] = 0; // inicializácia poľa p[0]=0; p[1]=0; ... p[9]=0;
    }

    cout << "Zadavajte " << N << "cisel z intervalu 0-9: ";
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        if (x >= 0 && x < 10) { // test, či je číslo z požadovaného rozsahu
            p[x]++;             // zvýšime počítadlo pre hodnotu x
        }
    }

    cout << endl;
    for (int i = 0; i < 10; i++) {
        cout << "Pocet vyskytov " << i << " je " << p[i] << endl; // výpis
    }
}

Podpriemer / nadpriemer

Chceme spočítať priemer a o každom vstupnom čísle vypísať, či je nadpriemerné alebo podpriemerné.

• Priemer vieme až keď načítame všetky čísla, musíme si ich teda zapamätať
• Keby sme vedeli dopredu, že čísel bude napr. 20, môžeme vytvoriť pole pevnej veľkosti podobne ako v predchádzajúcom príklade.

#include <iostream>
using namespace std;

int main(void) {
    const int N = 20; // premennu N uz nebude mozne menit, ma konstantnu hodnotu 20
    int p[N];
    double sucet = 0;

    cout << "Zadavajte " << N << " cisel: ";
    for (int i = 0; i < N; i++) {
        cin >> p[i];
        sucet += p[i];
    }

    double priemer = sucet / N;
    cout << "Priemer je " << priemer << "." << endl;
    for (int i = 0; i < N; i++) {
        if (p[i] > priemer) { 
             cout << p[i] << ": vacsie ako priemer." << endl;
        } else if (p[i] < priemer) {
             cout << p[i] << ": mensie ako priemer." << endl;
        } else {
             cout << p[i] << ": priemer." << endl;
        }
    }
}

• Pozor, chyby pri zaokrúhľovaní môžu spôsobiť, že niekedy priemerné číslo bude považované za nad/podpriemerné
  • Vedeli by ste program prerobiť tak, aby používal iba premenné typu int a nerobil žiadnu chybu v zaokrúhľovaní?
  • Môže aj po takejto zmene niekedy dať zlú odpoveď?

Polia

Rozsah poľa je konštantný výraz väčší ako 0. Prvky sa indexujú od 0 po počet - 1

int a[10];
const int N=20;
double b[N];

Ak nepoznáme vopred počet prvkov, ktoré chceme dať do poľa, môžeme odhadnúť, že ich nebude viac ako NMax, ktoré definujeme ako konštantu v programe.

• Vytvoríme pole veľkosti NMax, použijeme z neho len prých N hodnôt

#include <iostream>
using namespace std;

int main(void) {
    const int NMax = 1000;
    int p[NMax];
    int N;
    cout << "Zadaj pocet cisel: ";
    cin >> N;
    if (N > NMax) {
        cout << "Prilis velke N" << endl;
        return 1;  // ukončíme funkciu main a tým aj program
    }
   cout << "Zadavajte " << N << " cisel: ";
   ...

Čo ak ako veľkosť poľa použijeme premennú N, ktorú si prečítame od používateľa alebo inak spočítame za behu?

    int N;
    cout << "Zadaj pocet cisel: ";
    cin >> N;
    int p[N];

• V starších verziách C resp. C++ to nefunguje, aj keď niektoré novšie kompilátory to zvládajú
• Na prednáškach tento spôsob nebudeme používať
• Pole veľkosti N, ktorá nie je konštanta, sa naučíme vytvárať inak v druhej polovici semestra

Vytvorenie a inicializácia poľa

V definícii môžeme pole inicializovať zoznamom prvkov.

int A[4]={3, 6, 8, 10}; //spravne
int B[4]; //spravne
B[4]={3, 6, 8, 10};  //nespravne, pole tu nedefinujeme
B[0]=3; B[1]=6; B[2]=8; B[3]=10;  // spravne - menime prvky existujuceho pola

Indexovanie hodnotou mimo intervalu

Pozor, kompilátor nekontroluje indexy prvkov

  int a[10];
  a[10] = 1234;

• Skompiluje, ale hodnota 1234 sa zapíše do pamäti na zlé miesto
• Môže to mať nepredvídateľné následky: prepísanie obsahu iných premenných (chybný výpočet alebo „nevysvetliteľné“ správanie sa programu) alebo dokonca prepísanie časti kódu vášho programu

Kopírovanie a testovanie rovnosti

V prípade, že chceme vytvoriť pole, ktoré je kópiou už existujúceho poľa, ponúka sa možnosť príkazu priradenia b=a;. Takýto príkaz však neskompiluje – nedá sa takto priraďovať, treba kopírovať prvok po prvku.

  for (i=0; i<10; i++) b[i]=a[i];

Polia sa tiež nedajú porovnávať pomocou operátora ==. Podmienku if (a==b) cout << "Ok";. síce skompilujete, ale nikdy to nebude pravda – neporovná sa obsah poľa, ale niečo úplne iné (adresy polí v pamäti). Treba opäť porovnávať prvok po prvku.

  bool rovne = true;
  for (i = 0; i < 10; i++) { 
      rovne = rovne && a[i] == b[i]; 
  }
  if (rovne) cout << "Rovnaju sa" << endl; 

Ten istý kúsok programu môžeme napísať napr. aj takto:

  bool rovne = true;
  for (i = 0; i < 10; i++) { 
      if(a[i] != b[i]) {
          rovne = false;
          break;
      }
  }
  if (rovne) cout << "Rovnaju sa" << endl; 

Odbočka: grafická knižnica SVGdraw

Výsledný obrázok

• Aplikácie s grafickým rozhraním budeme programovať až budúci semester
• V tomto semestri, ale budeme kresliť obrázky v SVG formáte pomocou jednoduchej knižnice #SVGdraw
• Knižnicu si stiahnite a nainštalujte podľa návodu
• Na začiatku programu zapnite knižnicu pomocou #include "SVGdraw.h"
• Tu je malý ukážkový program, ktorý vykreslí zelený štvorec a v ňom červený kruh:

#include "SVGdraw.h"

int main(void) {
  /* Vytvor obrázok s šírkou 150 a výškou 100 a 
   * ulož ho do súboru stvorec.svg*/
  SVGdraw drawing(150, 100, "stvorec.svg");

  /* Nastav farbu vyfarbovania na zelenú. */
  drawing.setFillColor("green");
  /* Vykresli štvorec s ľavým horným rohom v bode (20,10)
   * a s dĺžkou strany 80, t.j. pravým dolným rohom 100,90 */
  drawing.drawRectangle(20,10,80,80);
  
  /* Nastav farbu vyfarbovania na červenú. */
  drawing.setFillColor("red");
  /* Vykresli kruh so stredom v bode (60,50) a polomerom 40. */
  drawing.drawEllipse(60,50,40,40);

  /* Ukonči vypisovanie obrázka. */
  drawing.finish();
}

Kreslíme kruhy

Nasledujúci program náhodne vygeneruje súradnice niekoľkých kruhov a vykreslí ich pomocou kružnice SVGdraw.

• Údaje o jednom kruhu si uloží do záznamu struct kruh, v programe používame pole takýchto kruhov.
• Navyše o každom kruhu zistí, či sa pretína s iným kruhom, a ak áno, pri vykresľovaní ho orámuje červenou farbou.

#include "SVGdraw.h"
#include <cstdlib>
#include <ctime>
#include <cmath>

struct kruh {
    int x, y; /* suradnice stredu */
    int polomer; /* polomer kruhu */
    bool pretinaSa; /* pretína sa s iným kruhom? */
};

void generujKruh(kruh &k, int velkost, int polomer) {
    /* inicializuj kruh s nahodnou polohou a danym polomerom */
    k.x = rand() % (velkost - 2 * polomer) + polomer;
    k.y = rand() % (velkost - 2 * polomer) + polomer;
    k.polomer = polomer;
}

bool pretinajuSa(kruh &k1, kruh &k2) {
    /* zisti, ci sa dva kruhy pretinaju */
    int dx = k1.x - k2.x;
    int dy = k1.y - k2.y;
    double d2 = sqrt(dx * dx + dy * dy);
    return d2 <= k1.polomer + k2.polomer;
}

int main(void) {
    const int pocet = 10; /* počet kruhov */
    const int velkost = 300; /* veľkosť obrázku */
    const int polomer = 15; /* polomer kruhu */

    /* inicializácia generátora pseudonáhodných čísel */
    srand(time(NULL));

    /* inicializácia obrázku */
    SVGdraw drawing(velkost, velkost, "kruhy.svg");

    /* pole kruhov */
    kruh kruhy[pocet];

    for (int i = 0; i < pocet; i++) {
        /* kazdemu kruhu vygeneruj nahodnu polohu */
        generujKruh(kruhy[i], velkost, polomer);
    }

    /* zisti, ktoré kruhy pretínajú iné kruhy */
    for (int i = 0; i < pocet; i++) {
        kruhy[i].pretinaSa = false;
        for (int j = 0; j < pocet; j++) {
            if (i != j && pretinajuSa(kruhy[i], kruhy[j])) {
                kruhy[i].pretinaSa = true;
            }
        }
    }

    /* vykresluj kruhy */
    drawing.setFillColor("gray");
    for (int i = 0; i < pocet; i++) {
        if (kruhy[i].pretinaSa) {
            drawing.setLineColor("red");
        } else {
            drawing.setLineColor("black");
        }
        drawing.drawEllipse(kruhy[i].x, kruhy[i].y,
                            kruhy[i].polomer, kruhy[i].polomer);
    }

    /* ukoncenie vykreslovania */
    drawing.finish();
}

Eratostenovo sito

Chceme vypísať všetky prvočísla medzi 2 a N. 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 (vypíšeme ho) a vyškrtáme jeho násobky.

#include <iostream>
using namespace std;

int main(void) {
    const int N = 25;
    bool A[N + 1];

    for (int i = 2; i <= N; i++) {
        A[i] = true;
    }
    for (int i = 2; i <= N; i++) {
        if (A[i]) {
            cout << i << " ";
            for (int j = 2 * i; j <= N; j = j + i) {
                A[j] = false;
            }
        }
    }
    cout << endl;
}

Výstup programu

2 3 5 7 11 13 17 19 23

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 poľa (ak by sme ich chceli použiť na ďalšie výpočty).

Ďalšie príklady na prácu s poľom

• Načítajte pole čísel a vypíšte ho v opačnom poradí.
• Skúste poradie povymieňať priamo v poli a nie iba pri výpise.

• Načítajte pole čísel, náhodne ich premiešajte a zase vypíšte.

Polia: zhrnutie

• Pole je tabuľka hodnôt. V poli dĺžky n máme hodnoty p[0], p[1], ..., p[n-1]
• Kopírovanie a porovnávanie polí si musíme naprogramovať
• C resp. C++ nekontrolujú, či index nie je mimo rozsahu poľa

Parametre funkcií - prehľad, opakovanie

• Jednoduché typy, napr. int, double, bool
  • Bez & sa skopíruje hodnota
  • S & premenná dostane vo funkcii nové meno

void f1(int x) {
    x++; // zmena x sa neprenesie do main (y zostane rovnaká)
    cout << x << endl;
}

void f2(int &x) {
    x++; // zmena x sa prenesie ako zmena y v main
    cout << x << endl;
}

int main(void) {
    int y = 0;
    f1(y);
    f2(y);
    f1(y + 1);
    //zle: f2(y+1);
}

• Polia odovzdávame bez &
  • väčšinou potrebujeme poslať aj veľkosť poľa, ak nie je globálne známa
  • zmeny v poli zostanú aj po skončení funkcie

void f(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << endl;
    }
}

int main(void) {
    int b[3] = {1, 2, 3};
    f(b, 3);
}

• SVGdraw obrázky sú v skutočnosti objekty, väčšinou ich chcete posielať s &
  • všetky zmeny na nich spravené pretrvávajú aj po skončení funkcie

#include "SVGdraw.h"
void kresli(SVGdraw &drawing, int n, int y, int rozostup, int velkost) {
   for(int i=0; i<n; i++) {
       drawing.drawRectangle(i*rozostup+velkost, y, velkost, velkost);
   }
}
int main(void) {
    SVGdraw drawing(320, 100, "stvorce.svg");
    kresli(drawing, 10, 50, 30, 10);
    drawing.finish();
}

• Štruktúry (struct) väčšinou tiež posielame pomocou &
• Návratové hodnoty:
  • ak je výsledkom funkcie jedno číslo alebo pravdivostná hodnota, vrátime ju príkazom return
  • ak je výsledkom viac hodnôt, alebo niečo zložitejšie (pole, struct,...), odovzdáme ho ako parameter pomocou &, návratová hodnota môže zostať void
• Tieto pravidlá súvisia so smerníkmi a správou pamäti, povieme si viac o pár týždňov