Prednáška 5

Organizačné poznámky

• Dnes cvičenia podľa rozvrhu
• Odovzdávanie DU1 do 22:00
• Už by ste mali mať zapísané správne predmety (ak nie bežte na štúdijné) a v prípade zmien do 5.10. potvrdiť finálnu verziu na študijnom oddelení

Štatistika z N čísel

Úlohou je zistiť o N prečítaných číslach nejaké štatistické údaje.

Maximum a minimum

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

• Ako ale začať? Ako nastaviť maximum a minumum na začiatok?
  • Jedna možnosť je nastaviť ich tak, aby to boli nezmyselné hodnoty a iste sa zmenili - napriklad maximum veľmi malé a minumum veľké. Kto nám ale zaručí, že používateľ nedá všetky čísla ešte menšie? Riešením je použiť najväčšie resp. najmenšie možné číslo - ale je to škaredé.
  • Druhá možnosť je si pamätať, že ešte nemáme správne nastavené minimum a maximum a pri prvej príležitosti ich nastaviť.
  • A prvá príležitosť je pri prvom čísle. Môžeme to teda urobiť priamo. Minimum iste nebude väčšie ako toto prvé číslo a maximum iste nebude menšie.

#include <iostream>
#include <cstdlib>

using namespace std;

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

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

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

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

  cout << endl << "Maximum je " << max << " a minumum je " << min << endl;  
}

Výskyty čísel 0..9

Ak vieme, že na vstupe sú iba čísla od 0 do 9, tak by sme chceli vedieť, koľko jednotlivých čísel je. Mohli by sme to riesiť takto:

• Pre každú možnú hodnotu si vytvoríme jednu premennú (dokopy ich bude teda 10 - 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 ...

Je to však pomerne komplikovaný spôsob - a to máme iba 10 rôznych premenných. Problém je v tom, ž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 tohoto príkladu pomocou poľa.

#include <iostream>
using namespace std;

int main(void) {
  int p[10];
  int c,N;
 
  for (int i=0; i<10; i++) p[i]=0;   // inicializácia pola p[0]=0; p[1]=0; ... p[9]=0;

  cout << "Zadajte pocet cisel: ";
  cin >> N;
  cout << "Zadavajte " << N << "cisel z intervalu 0-9: ";
  for (int i=0; i<N; i++){
    cin >> c;
    if (c>=0 && c<10) p[c]++;    // test, či je číslo z požadovaného rozsahu
  }

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

Priemer

Podobne ako pri maxime a minime si aj priemer vieme počítať postupne.

• Budeme si počítať súčet doterajších čísel a na záver ho vydelíme ich počtom.
• Dá sa robiť aj postupne - aby sme nemali zapamätané príliš veľké číslo (súčet)?

Ak by sme chceli o každom čísle vedieť, či je nadpriemerné alebo podpriemerné zjavne by sme si museli čísla 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) {
  int N=20;
  int p[20];
  double sucet=0;
  double priemer;
 
  cout << "Zadavajte " << N << " cisel: ";
  for (int i=0; i<N; i++){
    cin >> p[i];
    sucet=sucet+p[i];
  }

  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;
}

• Ak by sme nevedeli počet čísel, môžeme aspoň odhadnúť, že ich nebude viac ako NMax, ktoré definujeme ako konštantu v programe.
• A prečo vlastne nemôžeme dať ako veľkosť poľa N, ktoré si prečítame od používateľa?

Polia

• Rozsah poľa je konštantný výraz väčší ako 0. Prvky sa indexujú od 0 po počet - 1
• Občas sa dá ako rozsah použiť aj dopredu zadefinovaná premenná, ale napr. nasledovný program v C++ skompilujete ale v C nie. Takže opatrne!

  int i=100;
  int p [i]; // i je premenná, ktorá vznikne až počas behu programu, a teda jej hodnota nie je počas kompilácie známa.

• Radšej použijeme konštantu const int N=100
• Veľkosť poľa môže byť ohraničená v závislosti od kompilátora.

Vytvorenie a inicializácia poľa

V C++ je niekoľko pravidiel, ktoré určujú kedy ich môže používať a čo sa stane, ak počet prvok neodpovedá počtu hodnôt v inicializácii. Pole je možné inicializovať iba v definícii.

int A[4]={3, 6, 8, 10}; //spravne
int B[4]; //spravne
B[4]={3, 6, 8, 10};  //nespravne
B[0]=3; B[1]=6; B[2]=8; B[3]=10;

Pri inicializácii sa dá dodať aj menej hodnôt ako má pole. Napr. inicializácia iba dvoch prvých hodnôt. 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

  int a [10], b [10];
  int i;
  for (i=0; i<10; i++) a [i]=random (100); // náhodné hodnoty

Pozor, kompilátor nekontroluje indexy prvkov

 a [11]=1234;.

• Skompilujete, ale hodnota 12345 sa zapíše do pamäte 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 prepísane časti kódu vášho programu (čo vo väčšine prípadov spôsobí „zamrznutie“ alebo reset počítača),

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];

Podobne sa nedá porovnávať polia pomocou podmienky if (a==b) cout << "Ok";. Takúto podmienku síce skompilujete, ale nikdy to nebude pravda – neporovná sa obsah poľa, ale niečo úplne iné (adresy polí v pamäti). Treba to riešiť opäť prvok po prvku.

  bool r=true;
  for (i=0; i<10; i++) { r=r && (a [i]==b [i]); }
  if (r) cout << "Ok\n"; 

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 a vypíšte ho v náhodnom poradí.
• Ako by ste pole náhodne povymieňali priamo v pamäti?

Kreslíme padajúce kruhy

• 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 "../SimpleDraw.h"
#include <cstdlib>
#include <ctime>

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

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

    SimpleDraw window(size, size);
    window.setBrushColor("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 - diameter);
        y[i] = rand() % (size - diameter);
    }

    /* 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) {
                window.removeItem(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 - diameter) {
                y[i] = 0;
                x[i] = rand() % (size - diameter);
            }
            /* vykresli kruzok na novom mieste */
            id[i] = window.drawEllipse(x[i], y[i], diameter, diameter);
        }
        /* na konci iteracie chvilu pockaj */
        window.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 päť polí.
• Na spojenie údajov k jednému kruhu použijeme dátovú štruktúru struct

Padajúce kruhy so struct

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

struct kruh {
    int x, y; /* coordinates */
    int id;   /* id for deleting */
    int r, g, b; /* red, green, blue */
};

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

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

    int max = size - diameter; /* maximum possible coordinate */

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

    SimpleDraw window(size, size);
    window.setBrushColor("lightblue");

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

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

    /* 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) {
                window.removeItem(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 >= max) {
                generujKruh(kruhy[i], max);
                kruhy[i].y = 0;
            }
            /* vykresli kruzok na novom mieste */
            window.setBrushColor(kruhy[i].r, kruhy[i].g, kruhy[i].b);
            kruhy[i].id = window.drawEllipse(kruhy[i].x, kruhy[i].y,
                    diameter, diameter);
        }
        /* na konci iteracie chvilu pockaj */
        window.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 žadnu 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.

Zhrnutie

• V prípade využívania viacerých premenných, ktoré sú vlastne jednotlivé prvky nejakej postupnosti (načítávané čísla, ..) môžeme využívať polia
• Jednotlivé spolu súvisiace informácie (vlastnosti) o nejakom prvku spojíme do štruktúry pomocou struct