Programovanie (2) v Jave
1-INF-166, letný semester 2023/24
Prednáška 6: Rozdiel medzi revíziami
(→Oznamy) |
|||
(14 medziľahlých úprav od 3 ďalších používateľov nie je zobrazených) | |||
Riadok 3: | Riadok 3: | ||
Prebrali sme premenné, polia, podmienky, cykly a funkcie. | Prebrali sme premenné, polia, podmienky, cykly a funkcie. | ||
* Z týchto stavebných prvkov sa dajú vystavať pomerne komplikované programy. | * 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 | + | * 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 | Čo nás čaká v najbližšom čase | ||
− | * DÚ1 do | + | * 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ť [https://youtu.be/Uml5x1K8CJU video] s príkladom použitia knižnice [[SVGdraw]] na [[Predn%C3%A1%C5%A1ka_5#Kresl.C3.ADme_kruhy|kreslenie kruhov]]. |
− | * Dnes algoritmy s poliami | + | * Dnes algoritmy s poliami. |
− | * Rozcvička zajtra sa tiež bude týkať polí | + | * 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== | ==Parametre funkcií: prehľad, opakovanie== | ||
Riadok 149: | Riadok 94: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | #include < | + | #include <cassert> |
#include <iostream> | #include <iostream> | ||
using namespace std; | using namespace std; | ||
− | |||
void readArray(int a[], int &n, int maxN) { | void readArray(int a[], int &n, int maxN) { | ||
Riadok 162: | Riadok 106: | ||
cin >> n; | cin >> n; | ||
− | + | assert(n <= maxN); | |
− | + | ||
− | |||
− | |||
for (int i = 0; i < n; i++) { | for (int i = 0; i < n; i++) { | ||
cin >> a[i]; | cin >> a[i]; | ||
Riadok 387: | Riadok 329: | ||
'''Cvičenie:''' | '''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í) | * Na vstupe sú dve n-prvkové množiny (čísla v množine sa neopakujú, ale môžu byť zadané v ľubovoľnom poradí) | ||
− | * Zistite, tieto množiny obsahujú rovnaké prvky | + | * Zistite, či tieto množiny obsahujú rovnaké prvky |
** Viete pri tom použiť triedenie? | ** 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 <tt>true</tt>, 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 <tt>false</tt>. | ||
+ | * Potom prechádzame v poli, kým nenájdeme najbližšiu ďalšiu hodnotu <tt>true</tt>. Toto číslo je prvočíslo, teda ho vypíšeme a vyškrtáme jeho násobky. | ||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
+ | #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; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Výstup programu | ||
+ | <pre> | ||
+ | 2 3 5 7 11 13 17 19 23 29 | ||
+ | </pre> | ||
+ | |||
+ | Priebeh programu: | ||
+ | <pre> | ||
+ | 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 | ||
+ | </pre> | ||
+ | |||
+ | '''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== | ==Zdrojový kód programu s triedeniami== | ||
Riadok 395: | Riadok 390: | ||
http://compbio.fmph.uniba.sk/vyuka/prog/index.php/Predn%C3%A1%C5%A1ka_6 */ | http://compbio.fmph.uniba.sk/vyuka/prog/index.php/Predn%C3%A1%C5%A1ka_6 */ | ||
#include <iostream> | #include <iostream> | ||
− | #include < | + | #include <cassert> |
using namespace std; | using namespace std; | ||
Riadok 413: | Riadok 408: | ||
cin >> n; | cin >> n; | ||
− | + | assert(n <= maxN); | |
− | |||
− | |||
− | |||
for (int i = 0; i < n; i++) { | for (int i = 0; i < n; i++) { | ||
cin >> a[i]; | cin >> a[i]; | ||
Riadok 455: | Riadok 447: | ||
index = i; | index = i; | ||
} | } | ||
− | /* invariant: a[j]<=a[index] pre | + | /* invariant: a[j]<=a[index] pre všetky j=0,...,i*/ |
} | } | ||
return index; | return index; |
Aktuálna revízia z 17:21, 8. október 2023
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);
}