Programovanie (1) v C/C++
1-INF-127, ZS 2024/25
Prednáška 5
Obsah
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