Programovanie (2) v Jave
1-INF-166, letný semester 2023/24
Prednáška 5
Obsah
Štatistika z N čísel
Od užívateľa postupne načítame N čísel a chceme o nich zistiť nejaké štatistické údaje.
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ľko jednotlivých čísel je. Mohli by sme to riešiť 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 ...
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) p[x]++; // test, či je číslo z požadovaného rozsahu } 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[20];
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
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; } 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 to 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ä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 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];
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 rovne = true; for (i = 0; i < 10; i++) { rovne = rovne && a[i] == b[i]; } if (rovne) 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 "../SVGdraw.h" #include <cstdlib> #include <ctime> int main(void) { const int count = 10; /* 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 = 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 - 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) { 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 - diameter) { y[i] = 0; x[i] = rand() % (size - diameter); } /* vykresli kruzok na novom mieste */ id[i] = drawing.drawEllipse(x[i], y[i], diameter, diameter); } /* 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
#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 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 = 10; /* 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 = 100; /* pocet iteracii */ double wait = 0.2; /* cakaj po kazdej iteracii */ int max = size - diameter; /* maximalna mozna suradnica */ /* 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], 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) { 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 >= max) { generujKruh(kruhy[i], max); kruhy[i].y = 0; } /* 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, diameter, diameter); } /* 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).
Zhrnutie
- V prípade využívania viacerých premenných, ktoré sú vlastne jednotlivé prvky nejakej postupnosti (načítavané čísla, ..) môžeme využívať polia
- Jednotlivé spolu súvisiace informácie (vlastnosti) o nejakom prvku spojíme do štruktúry pomocou struct
Reklama
- V piatok od 13:10 v H6 školské kolo programátorskej súťaže ACM