Prednáška 5

Š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:

• Č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 pola 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čítdlo 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, koľko ich bude, vedeli by sme to urobiť 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: ";
   ...

Nie je možné priamo zadefinovať ako veľkosť poľa 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 niektorých verziách C resp. C++ to funguje
• Pole veľkosti N, ktorá nie je konštanta, sa naučíme vytvárať trochu 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

Pri inicializácii sa dá dodať aj menej hodnôt ako má pole. Pri čiastočnej inicializácii nastaví prekladač ostatné prvky na nulu.

double C[5]={5.0, 13.9}; // inicializuje C[0]=5.0, C[1]=13.9 a C[2]..C[4]=0
double C[5]={0}; // jednoduchá inicializácia všetkých prvkov na 0

Ak pri inicializácii poľa necháme hranaté zátvorky prázdne, prekladač si sám spočíta prvky poľa. Nie je to však odporúčaný postup.

int A[]={1, 5, 3, 8}; // zistí rozsah poľa 0..3

Indexovanie hodnotou mimo intervalu

Pozor, kompilátor nekontroluje indexy prvkov

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

• Skompilujete, 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 neskompilujete – 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 << "Ok\n"; 

Kreslíme padajúce kruhy

Chceme vykresliť animáciu padajúcich kruhov

• Vytvoríme si polia pre x-ovú a y-ovú súradnicu kruhu.
• Potrebujeme aj pole, do ktorého si budeme dávať celočíselné identifikátory nakreslených kruhov, aby sme ich neskôr mohli zmazať.

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

int main(void) {
    const int count = 10; /* počet kruhov */
    const int size = 300; /* veľkosť obrázku */
    const int radius = 15; /* polomer kruhu */
    const int step = 4; /* o kolko padne dolu v jednom kroku */
    const int repeat = 100; /* pocet iteracii */
    double wait = 0.2; /* cakaj po kazdej iteracii */

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

    SVGdraw drawing(size, size, "kruhy.svg");
    drawing.setFillColor("lightblue");

    int x[count]; /* x-ova poloha kruzku */
    int y[count]; /* y-ove poloha kruzku */
    int id[count]; /* id objektu na obrazovke */

    /* kazdemu kruzku vygeneruj nahodnu polohu */
    for (int i = 0; i < count; i++) {
        x[i] = rand() % (size - 2*radius) + radius;
        y[i] = rand() % (size - 2*radius) + radius;
    }

    /* opakuj repeat iteracii */
    for (int r = 0; r < repeat; r++) {
        /* chod cez vsetky kruhy */
        for (int i = 0; i < count; i++) {
            /* ak nie sme v prvej iteracii, treba zmazat kruh */
            if (r > 0) {
                drawing.hideItem(id[i]);
            }
            /* zvys y-ovu suradnicu o step */
            y[i] += step;
            /* ak sme prilis nizko, zacni na vrchu na nahodnom x */
            if (y[i] >= size - radius) {
                y[i] = radius;
                x[i] = rand() % (size - 2*radius) + radius;
            }
            /* vykresli kruzok na novom mieste */
            id[i] = drawing.drawEllipse(x[i], y[i], radius, radius);
        }
        /* na konci iteracie chvilu pockaj */
        drawing.wait(wait);
    }
}

• Takéto polia nie sú ideálne, lebo údaje o jednom kruhu sú v troch rôznych poliach a bolo by logickejšie ich mať pokope.
• Situácia by bola ešte horšia, ak by každý kruh mal napr. aj náhodnú farbu s troma zložkami R,G,B. To by sme potrebovali šesť polí.
• Na spojenie údajov k jednému kruhu použijeme dátovú štruktúru struct

Padajúce kruhy so struct

Výsledok

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

struct kruh {
    int x, y; /* suradnice */
    int id;   /* id na mazanie */
    int r, g, b; /* zlozky farby: red, green, blue */
};

void generujKruh(kruh &k, int size, int radius) {
    k.x = rand() % (size-2*radius) + radius;
    k.y = rand() % (size-2*radius) + radius;
    k.r = rand() % 256;
    k.g = rand() % 256;
    k.b = rand() % 256;
    k.id = -1;
}

int main(void) {
    const int count = 10; /* počet kruhov */
    const int size = 300; /* veľkosť obrázku */
    const int radius = 15; /* polomer kruhu */
    const int step = 4; /* o kolko padne dolu v jednom kroku */
    const int repeat = 100; /* pocet iteracii */
    const double wait = 0.2; /* cakaj po kazdej iteracii */

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

    SVGdraw drawing(size, size, "kruhy2.svg");

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

    /* kazdemu kruzku vygeneruj nahodnu polohu */
    for (int i = 0; i < count; i++) {
        generujKruh(kruhy[i], size, radius);
    }

    /* opakuj repeat iteracii */
    for (int r = 0; r < repeat; r++) {
        /* chod cez vsetky kruhy */
        for (int i = 0; i < count; i++) {
            /* ak nie sme v prvej iteracii, treba zmazat kruh */
            if (r > 0) {
                drawing.hideItem(kruhy[i].id);
            }
            /* zvys y-ovu suradnicu o step */
            kruhy[i].y += step;
            /* ak sme prilis nizko, zacni na vrchu na nahodnom x */
            if (kruhy[i].y >= size - radius) {
                generujKruh(kruhy[i], size, radius);
                kruhy[i].y = radius;
            }
            /* vykresli kruzok na novom mieste */
            drawing.setFillColor(kruhy[i].r, kruhy[i].g, kruhy[i].b);
            kruhy[i].id = drawing.drawEllipse(kruhy[i].x, kruhy[i].y,
                    radius, radius);
        }
        /* na konci iteracie chvilu pockaj */
        drawing.wait(wait);
    }
}

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 povymienať priamo v poli a nie iba pri výpise.

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

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
• Súvisiace informácie o nejakom prvku môžeme spojiť do štruktúry pomocou struct

Oznamy

• Nezabudnite do zajtra odovzdať DÚ2, objaví sa DÚ3
• V piatok 17.10. od 13:00 v H6 školské kolo programátorskej súťaže ACM