Programovanie (1) v C/C++
1-INF-127, ZS 2024/25
Prednáška 6
Skočit na navigaci
Skočit na vyhledávání
Obsah
Oznamy
Prebrali sme premenné, polia, podmienky, cykly a funkcie.
- Z týchto stavebných prvkov sa dajú vystavať pomerne komplikované programy.
- Menej skúsení programátori si potrebujú prácu s týmito pojmami čo najviac precvičiť. Skúste vyriešiť všetky príklady z cvičení, pracujte na domácej úlohe.
- Neodpisujte, nič sa tým nenaučíte.
- Kontaktujte nás, ak potrebujete pomôcť.
- Účasť na piatkových cvičeniach nie je "za trest", ale spôsob, ako vám môžeme pomôcť zvládnuť predmet.
Čo nás čaká v najbližšom čase
- DÚ1 je zverejnená, riešte do utorka 24.10. 22:00. Každá DÚ má váhu 5% známky, t.j. ako cca 2 týždne cvičení.
- Môže sa vám zísť video s príkladom použitia knižnice SVGdraw na kreslenie kruhov.
- Dnes algoritmy s poliami.
- Rozcvička zajtra sa tiež bude týkať polí.
- Účasť v piatok povinná pre tých, ktorí v utorok nezískajú aspoň 4 body.
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() {
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() {
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() {
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 (pri poli & nedávame)
Tieto pravidlá súvisia so smerníkmi a správou pamäti, povieme si viac o pár týždňov
Funkcie a polia: načítanie a vypísanie poľa
Dve základné funkcie, ktoré sa nám môžu zísť v programoch
- precvičíme si tiež ako sa pracuje s poliami vo funkciách
#include <cassert>
#include <iostream>
using namespace std;
void readArray(int a[], int &n, int maxN) {
/* Od užívateľa načíta počet vstupných čísel,
* tento počet uloží do premennej n.
* Potom načíta n celých čísel a uloží ich do poľa a,
* Hodnota maxN je veľkosť poľa,
* ktorú nemožno prekročiť. */
cin >> n;
assert(n <= maxN);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
}
void printArray(int a[], int n) {
for (int i = 0; i < n; i++) {
cout << " " << a[i];
}
cout << endl;
}
int main() {
const int maxN = 100;
int n;
int a[maxN];
readArray(a, n, maxN);
// tu môžeme pole nejako upraviť
printArray(a, n);
}
Triedenia
Máme pole čísel, chceme ich usporiadať od najmenšieho po najväčšie.
- Napr. pre pole 9 3 7 4 5 2 chceme dostať 2 3 4 5 7 9
- Jeden z najštudovanejších problémov v informatike.
- Súčasť mnohých zložitejších algoritmov.
- Veľa spôsobov, ako triediť, dnes si ukážeme zopár najjednoduchších.
Bublinkové triedenie (Bubble Sort)
Idea: Kontrolujeme všetky dvojice susedných prvkov a keď vidíme menšie číslo za väčším, vymeníme ich
for (int i = 1; i < n; i++) {
if (a[i] < a[i - 1]) {
swap(a[i - 1], a[i]);
}
}
- Ak sme nenašli v poli žiadnu dvojicu, ktorú treba vymeniť, skončili sme.
- Inak celý proces opakujeme znova.
Celé triedenie:
void swap(int &x, int &y) {
/* Vymeň hodnoty premenných x a y. */
int tmp = x;
x = y;
y = tmp;
}
void sort(int a[], int n) {
/* usporiadaj prvky v poli a od najmenšieho po najväčší */
bool hotovo = false;
while (!hotovo) {
bool vymenil = false;
/* porovnávaj všetky dvojice susedov,
vymeň ak menší za väčším */
for (int i = 1; i < n; i++) {
if (a[i] < a[i - 1]) {
swap(a[i - 1], a[i]);
vymenil = true;
}
}
/* ak sme žiadnu dvojicu nevymenili,
môžeme skončiť. */
if (!vymenil) {
hotovo = true;
}
}
}
- Čo ak vo for cykle dáme for (int i = 0; i < n; i++) { ?
- Ako nahradíme premennú hotovo príkazom break?
Príklad behu:
prvá iterácia while cyklu 9 3 7 4 5 2 3 9 7 4 5 2 3 7 9 4 5 2 3 7 4 9 5 2 3 7 4 5 9 2 3 7 4 5 2 9 druhá iterácia while cyklu 3 7 4 5 2 9 3 4 7 5 2 9 3 4 5 7 2 9 3 4 5 2 7 9 tretia iterácia while cyklu 3 4 5 2 7 9 3 4 2 5 7 9 štvrtá iterácia while cyklu 3 4 2 5 7 9 3 2 4 5 7 9 piata iterácia while cyklu 3 2 4 5 7 9 2 3 4 5 7 9
Cvičenie: Ako sa bude správať algoritmus na nasledujúcich vstupoch, koľkokrát zopakuje vonkajší while cyklus?
- Utriedené pole 1,2,...,n
- Pole n,1,2,...,n-1
- Pole 2,3,...,n,1
- Pole n,n-1,...,1
Triedenie výberom (selection sort, max sort)
Idea: nájdime najväčší prvok a uložme ho na koniec. Potom nájdime najväčší medzi zvyšnými a uložme ho na druhé miesto odzadu atď.
- V cykle uvádzame ako komentár invariant, podmienku, ktorá na tom mieste vždy platí. Takýto invariant nám pomôže si uvedomiť, že je náš program správny.
int maxIndex(int a[], int n) {
/* vráť index, na ktorom je najväčší prvok
z prvkov a[0]...a[n-1] */
int index = 0;
for(int i=1; i<n; i++) {
if(a[i]>a[index]) {
index = i;
}
/* invariant: a[j]<=a[index] pre vsetky j=0,...,i*/
}
return index;
}
void sort(int a[], int n) {
/* usporiadaj prvky v poli a od najmenšieho po najväčší */
for(int kam = n - 1; kam >= 1; kam--) {
/* invariant: a[kam+1]...a[n-1] sú utriedené
* a pre každé i,j také že 0<=i<=kam, kam<j<n
* platí a[i]<=a[j] */
int index = maxIndex(a, kam + 1);
swap(a[index], a[kam]);
}
}
Príklad behu programu
Vstup 9 3 7 4 5 2 Po výmene (9,2) 2 3 7 4 5 9 Po výmene (7,5) 2 3 5 4 7 9 Po výmene (5,4) 2 3 4 5 7 9 Po výmene (4,4) 2 3 4 5 7 9 Po výmene (3,3) 2 3 4 5 7 9
Cvičenie: Bude čas behu algoritmu výrazne odlišný pre pole utriedené správne a pole utriedené v opačnom poradí?
Triedenie vkladaním (Insertion Sort)
Idea:
- v prvej časti poľa prvky v utriedenom poradí
- zober prvý prvok z druhej časti a vlož ho na správne miesto v utriedenom poradí
Príklad behu algoritmu:
9 3 7 4 5 2 3 9 7 4 5 2 3 7 9 4 5 2 3 4 7 9 5 2 3 4 5 7 9 2 2 3 4 5 7 9
Ako spraviť vkladanie:
- Vkladaný prvok si zapamätáme v pomocnej premennej
- Utriedené prvky posúvame o jedno doprava, kým nenájdeme správne miesto pre odložený prvok
void sort(int a[], int n) {
/* usporiadaj prvky v poli a od najmenšieho po najväčší */
for (int i = 1; i < n; i++) {
int prvok = a[i];
int kam = i;
while (kam > 0 && a[kam - 1] > prvok) {
a[kam] = a[kam - 1];
kam--;
}
a[kam] = prvok;
}
}
- Všimnime si podmienku (kam > 0 && a[kam - 1] > prvok)
- Ak kam==0, prvá časť je false, druhá časť sa už nevyhodnocuje
- Ak by sme prehodili časti, program by mohol spadnúť (a[kam - 1] > prvok && kam > 0)
Cvičenie: Ako sa bude správať algoritmus na nasledujúcich vstupoch, koľkokrát zopakuje priradenie a[kam]=a[kam-1]?
- Utriedené pole 1,2,...,n
- Pole n,1,2,...,n-1
- Pole 2,3,...,n,1
- Pole n,n-1,...,1
Triedenia: zhrnutie
- Videli sme tri jednoduché algoritmy na triedenie
- Neskôr sa naučíme rýchlejšie algoritmy na triedenie, ktoré používajú rekurziu
- Precvičili sme si funkcie, parametre a polia
- K funkciám je dobré napísať, čo robia
- Do cyklov si môžeme písať invarianty
- Používajú sa pri formálnom dokazovaní správnosti
- Pomáhajú pochopeniu kódu
- Môžeme ich použiť na ručnú alebo automatickú kontrolu správnosti hodnôt premenných
- Príkaz assert v knižnici cassert kontroluje podmienku, napr. assert(i>=0 && i<n); ukončí program s chybovou hláškou ak podmienka neplatí
Cvičenie:
- Na vstupe sú dve n-prvkové množiny (čísla v množine sa neopakujú, ale môžu byť zadané v ľubovoľnom poradí)
- Zistite, či tieto množiny obsahujú rovnaké prvky
- Viete pri tom použiť triedenie?
Eratostenovo sito
- Prvočíslo je prirodzené číslo väčšie ako 1, ktoré je deliteľné len samo sebou a číslom 1.
- Chceli by sme nájsť všetky prvočísla medzi 2 a n.
- Napríklad ak n=30, výsledok má byť 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
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, teda ho vypíšeme a vyškrtáme jeho násobky.
#include <iostream>
using namespace std;
int main() {
const int n = 30;
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 29
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).
Zdrojový kód programu s triedeniami
/* Program s triedeniami z prednášky 6.
http://compbio.fmph.uniba.sk/vyuka/prog/index.php/Predn%C3%A1%C5%A1ka_6 */
#include <iostream>
#include <cassert>
using namespace std;
void swap(int &x, int &y) {
/* Vymeň hodnoty premenných x a y. */
int tmp = x;
x = y;
y = tmp;
}
void readArray(int a[], int &n, int maxN) {
/* Od užívateľa načíta počet vstupných čísel,
* tento počet uloží do premennej n.
* Potom načíta n celých čísel a uloží ich do poľa a,
* Hodnota maxN je veľkosť poľa,
* ktorú nemožno prekročiť. */
cin >> n;
assert(n <= maxN);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
}
void printArray(int a[], int n) {
for (int i = 0; i < n; i++) {
cout << " " << a[i];
}
cout << endl;
}
void bubbleSort(int a[], int n) {
/* usporiadaj prvky v poli a od najmenšieho po najväčší */
bool hotovo = false;
while (!hotovo) {
bool vymenil = false;
/* porovnávaj všetky dvojice susedov, vymeň ak menší za väčším */
for (int i = 1; i < n; i++) {
if (a[i] < a[i - 1]) {
swap(a[i - 1], a[i]);
vymenil = true;
}
}
/* ak sme žiadnu dvojicu nevymenili, môžeme skončiť. */
if (!vymenil) {
hotovo = true;
}
}
}
int maxIndex(int a[], int n) {
/* vráť index, na ktorom je najväčší prvok z prvkov a[0]...a[n-1] */
int index = 0;
for(int i=1; i<n; i++) {
if(a[i]>a[index]) {
index = i;
}
/* invariant: a[j]<=a[index] pre všetky j=0,...,i*/
}
return index;
}
void selectionSort(int a[], int n) {
/* usporiadaj prvky v poli a od najmenšieho po najväčší */
for(int kam=n-1; kam>=1; kam--) {
/* invariant: a[kam+1]...a[n-1] sú utriedené
* a pre každé i,j také že 0<=i<=kam, kam<j<n platí a[i]<=a[j] */
int index = maxIndex(a, kam+1);
swap(a[index], a[kam]);
}
}
void insertionSort(int a[], int n) {
/* usporiadaj prvky v poli a od najmenšieho po najväčší */
for (int i = 1; i < n; i++) {
// inv1
int prvok = a[i];
int kam = i;
while (kam > 0 && a[kam - 1] > prvok) {
// inv2
a[kam] = a[kam - 1];
kam--;
}
a[kam] = prvok;
}
}
int main() {
const int maxN = 100;
int n;
int a[maxN];
readArray(a, n, maxN);
printArray(a, n);
insertionSort(a, n);
printArray(a,n);
}
