Programovanie (2) v Jave
1-INF-166, letný semester 2023/24
Prednáška 3
Obsah
Oznamy
Budúci pondelok 5. októbra bude v čase prednášky teoretické cvičenie
- Budete písať krátky test zameraný učivo z prvých troch prednášok
- Úspešní riešitelia testu pre pokročilých sa testu zúčastniť nemusia
- Na teste bude povolené používať pero a ťahák vo forme jedného obojstranne popísaného listu A4
Ciele teoretického cvičenia
- Precvičiť si poriadnejšie základné konštrukty
- Vynechaním jednej prednášky vznikne väčší priestor precvičiť si základy
- Vyskúšať si prácu na papieri (bude treba na aj písomkách)
Prečo robíme toto cvičenie a písomné testy na papieri?
- Dobré na precvičenie porozumenia hotovým programom (treba na ďalších predmetoch aj pri štúdiu odbornej literatúry)
- Núti vás dobre si premyslieť každý detail, nie len náhodne skúšať meniť rôzne časti programu, kým nezačne fungovať
- Pri zložitejších programoch sa už nedá postupovať náhodne
- Na papieri miernejšie hodnotíme drobné chyby ako chýbajúca bodkočiarka, to vám na počítači pomôže nájsť kompilátor. Dôležitejšie je sa rozhodnúť, či má byť niekde napríklad i<n alebo i<=n.
Opakovanie: výpočet faktoriálu
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Zadajte n: ";
cin >> n;
int vysledok = 1;
for (int i = 1; i <= n; i++) {
vysledok = vysledok * i;
}
cout << n << "! = " << vysledok << endl;
}
Cvičenie: rozšírte program tak, aby okrem výpisu výsledku aj rozpísal faktoriál ako súčin:
Zadajte n: 4 4! = 1*2*3*4 = 24
Príklad behu programu pre n=4:
Zadajte n: 4 4! = 24
Cvičenie: rozšírte program tak, aby okrem výpisu výsledku aj rozpísal faktoriál ako súčin:
Zadajte n: 4 4! = 1*2*3*4 = 24
Ďalšie príklady na cyklus for
Simulovanie hodov kocky
Nasledujúci program od používateľa načíta číslo n a vypíše n simulovaných hodov kocky (každý na samostatný riadok).
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
// Inicializacia generatora pseudonahodnych cisel
srand(time(NULL));
int n;
cout << "Zadajte pocet hodov: ";
cin >> n;
for (int i = 1; i <= n; i++) {
// Vygenerovanie a vypisanie hodu kockou
cout << rand() % 6 + 1 << endl;
}
}
Príklad behu programu:
Zadajte pocet hodov: 6 2 6 1 2 1 4
- Program využíva funkciu rand(), ktorá generuje pseudonáhodné celé čísla.
- Nie sú v skutočnosti náhodné, lebo ide o pevne definovanú matematickú postupnosť, ktorá však má mnohé vlastnosti náhodných čísel.
- Aby bolo možné použiť túto funkciu, treba do hlavičky pridať #include <cstdlib>.
- Výstupom funkcie rand() je nezáporné celé číslo medzi nulou a nejakou veľkou konštantou.
- Zvyšok po delení tohto čísla šiestimi, t.j. rand() % 6, je potom číslo medzi 0 a 5. Ak k tomu pripočítame 1, dostaneme číslo od 1 po 6.
- Funkcia srand inicializuje generátor pseudonáhodných čísel na základe parametra určujúceho počiatočný bod pseudonáhodnej postupnosti.
- My ako tento parameter používame aktuálny čas (v sekundách od začiatku roku 1970), čo zaručuje dostatočný efekt náhodnosti.
- Aby bolo možné použiť funkciu time, je treba do hlavičky pridať #include <ctime>.
Vypisovanie deliteľov (podmienka v cykle)
Nasledujúci program načíta od používateľa prirodzené číslo n a vypíše zoznam jeho deliteľov.
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Zadajte cislo: ";
cin >> n;
cout << "Delitele cisla " << n << ":";
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
cout << " " << i;
}
}
cout << endl;
}
Príklad behu programu:
Zadajte cislo: 30 Delitele cisla 30: 1 2 3 5 6 10 15 30
Úprava a čitateľnosť programov
Pri písaní programov je potrebné myslieť na to, že ho typicky budú okrem počítača čítať aj ľudia (či už ide o vás samotných po dlhšom čase, učiteľov, alebo v praxi o spolupracovníkov na väčšom projekte). Je preto zvykom dodržiavať určité zásady, ktoré čitateľnosť zdrojového kódu zlepšujú:
- Odsadzovanie: príkazy vykonávané v cykle, či v podmienke (alebo vo všeobecnosti v ľubovoľnom bloku medzi { a }) odsadzujeme o niekoľko pozícií doprava (napríklad o 4 medzery).
- Pri vnorených cykloch, podmienkach a podobne odsadzujeme o ďalšie štyri pozície, atď.
- Väčšina editorov a IDE pre C/C++ nejakým spôsobom odsadzovanie podporujú
- Voľné riadky: ucelené časti programu je kvôli prehľadnosti často dobré oddeliť prázdnym riadkom.
- Medzery: odporúča sa (najmä v zložitejších výrazoch) písať okolo operátorov medzery.
- Napríklad zápis
for (int i = 1; i <= n; i++) {
a += i;
}
je o dosť prehľadnejší ako
for(int i=1;i<=n;i++){a+=i;}
- Dĺžka riadku: odporúča sa vyhýbať sa riadkom dlhším ako 80 znakov. S dlhými riadkami sú problémy pri tlači alebo zobrazovaní v menších oknách; aj na veľkom monitore čitateľa zbytočne namáhajú. V prípade potreby je možné dlhšiu podmienku alebo iný výraz rozdeliť na viac riadkov.
- Názvy premenných: najmä pri rozsiahlejších programoch je vhodné používať názvy premenných, ktoré vyjadrujú ich obsah (napríklad userCount alebo pocet_pouzivatelov namiesto h). Premenné v kratších programoch, alebo premenné používané iba lokálne v kratšom kuse programu možno označovať aj krátkymi zaužívanými názvami, ako napríklad i a j pre premenné v cykloch, n pre počet, alebo a pre pole.
- Komentáre: význam jednotlivých úsekov kódu je najmä pri rozsiahlejších programoch dobré popísať v komentároch.
Pri známkovaní budeme brať do úvahy aj prehľadnosť vašich programov.
Cyklus while
Okrem cyklu for možno v jazykoch C/C++ používať aj cyklus while s nasledujúcou schémou:
while (podmienka) {
telo cyklu
}
Telo takéhoto cyklu sa vykonáva, kým je podmienka cyklu splnená. Presnejšie sa pri vykonávaní cyklu while typicky deje nasledovné:
- Overí sa, či je podmienka cyklu splnená.
- Ak áno, vykoná sa telo cyklu a celý proces sa opakuje (čiže sa opätovne vykoná overenie podmienky z bodu 1, atď.).
- Ak nie, vykonávanie programu pokračuje prvým príkazom nasledujúcim za cyklom while.
Úroky v banke
- Predpokladajme, že na začiatku každého roku uložíme na účet nejakú pevnú sumu (napríklad 1000 EUR).
- Na konci každého roku sa vklad zúročí ročným úrokom (napríklad 5%).
- Za koľko rokov úspory dosiahnu danú cieľovú čiastku (napríklad 10000 EUR)?
Túto úlohu budeme riešiť programom pracujúcim nasledovne:
- V premennej ciastka budeme uchovávať aktuálny stav účtu
- V každom roku túto premennú zvýšime o vklad a úrok
- Toto opakujeme, kým suma uložená v premennej nie je rovná aspoň cieľovej čiastke.
To môžeme vyjadriť pomocou cyklu while.
#include <iostream>
using namespace std;
int main(void) {
double vklad, ciel, urok;
cout << "Zadaj kazdorocny vklad: ";
cin >> vklad;
cout << "Zadaj cielovu ciastku: ";
cin >> ciel;
cout << "Zadaj rocny urok (v %): ";
cin >> urok;
int rok = 0;
double ciastka = 0;
while (ciastka < ciel) {
rok++;
ciastka = (ciastka + vklad) * (1 + urok / 100);
cout << "Na konci roku " << rok << " je na ucte " << ciastka << " EUR." << endl;
}
}
Ukážkový vstup a výstup:
Zadaj kazdorocny vklad: 1000 Zadaj cielovu ciastku: 10000 Zadaj rocny urok (v %): 5 Na konci roku 1 je na ucte 1050 EUR Na konci roku 2 je na ucte 2152.5 EUR Na konci roku 3 je na ucte 3310.12 EUR Na konci roku 4 je na ucte 4525.63 EUR Na konci roku 5 je na ucte 5801.91 EUR Na konci roku 6 je na ucte 7142.01 EUR Na konci roku 7 je na ucte 8549.11 EUR Na konci roku 8 je na ucte 10026.6 EUR
Euklidov algoritmus
Euklidov algoritmus slúži na hľadanie najväčšieho spoločného deliteľa dvojice kladných celých čísel a, b.
- To znamená: hľadáme najväčšie kladné prirodzené číslo d, ktoré delí súčasne a aj b.
- Najväčší spoločný deliteľ čísel a, b označujeme gcd(a,b) (z angl. greatest common divisor). V slovenčine sa používa aj s označenie nsd(a,b).
- Ide o jeden z najstarších známych algoritmov vôbec. Jeho variant popísal už Euklides v diele Základy okolo roku 300 pred Kr.
Príklad:
- Delitele čísla 12 sú 1, 2, 3, 4, 6, 12.
- Delitele čísla 8 sú 1, 2, 4, 8.
- Spoločné delitele 8 a 12 teda sú 1, 2, 4.
- Najväčší spoločný deliteľ čísel 8 a 12 je teda gcd(8,12) = 4.
Euklidov algoritmus je založený na platnosti nasledujúcej lemy.
Lema. Pre všetky kladné celé čísla a, b platí:
- gcd(a,b) = gcd(b, a mod b).
Dôkaz.
- Nech X je množina spoločných deliteľov a a b, nech Y je množina spoločných deliteľov b a a mod b. Dokážeme rovnosť X = Y.
- Ak označíme r := a mod b, tak existuje celé číslo q také, že a = q b + r.
- Ak x ∈ Y, číslo x delí b aj r a z rovnosti a = q b + r vyplýva, že delí aj a. Teda x ∈ X.
- Ak naopak x ∈ X, číslo x delí a aj b a z rovnosti r = a - qb vyplýva, že delí aj r. Preto x ∈ Y.
- Dokázali sme teda, že platí X ⊆ Y a súčasne X ⊆ Y. Preto X = Y. ◻
Poznámka: môže sa stať, že a mod b je 0. Nakoľko ale každé celé číslo delí nulu, gcd(b, 0) = b pre každé kladné b.
- Euklidov algoritmus opakovane používa lemu: gcd(12,8) = gcd(8, 4) = gcd(4, 0) = 4
- Dostáva sa k stále menším číslam, až kým b neklesne na nulu
Implementácia tohto algoritmu teda môže vyzerať nasledovne:
#include <iostream>
using namespace std;
int main() {
int a, b;
cout << "Zadaj dvojicu kladnych celych cisel: ";
cin >> a >> b;
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
cout << "Najvacsi spolocny delitel je " << a << "." << endl;
}
Príklad behu programu:
Zadaj dvojicu kladnych celych cisel: 30 8 Najvacsi spolocny delitel je 2.
Tento výpočet prešiel cez dvojice:
30 8 8 6 6 2 2 0
Cvičenie: Ako bude fungovať Euklidov algoritmus pre vstupné čísla 8, 30?
Nekonečný cyklus
V cykle while typu
while (true) {
telo cyklu
}
je podmienka stále splnená; telo cyklu sa teda opakuje donekonečna resp. kým program nezastavíme (v prípade, že cyklus neukončíme umelo príkazom break, ktorý uvidíme o chvíľu).
Napríklad môžeme donekonečna niečo vypisovať:
#include <iostream>
using namespace std;
int main() {
while (true) {
cout << "Hello, World!" << endl;
}
}
Hra „hádaj číslo”
V nasledujúcom programe si počítač „myslí” číslo od 1 do 100 a užívateľ háda, o ktoré číslo ide (až kým nakoniec neuhádne).
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
srand(time(NULL));
int num = rand() % 100 + 1;
cout << "Myslim si cislo od 1 po 100. Tvoj tip: ";
bool correct = false;
while (!correct) {
int guess;
cin >> guess;
if (guess < num) {
cout << "Prilis nizko. Iny tip: ";
} else if (guess > num) {
cout << "Prilis vysoko. Iny tip: ";
} else {
correct = true;
cout << "Spravne!" << endl;
}
}
}
Príklad behu programu:
Myslim si cislo od 1 po 100. Tvoj tip: 50 Prilis nizko. Iny tip: 70 Prilis nizko. Iny tip: 90 Prilis vysoko. Iny tip: 80 Spravne!
Príkazy break a continue
V C/C++ existuje dvojica príkazov umožňujúcich umelo prerušiť vykonávanie cyklu resp. jednej jeho iterácie:
- Príkaz break ukončí cyklus, v ktorom sa program práve nachádza; vykonávanie programu pokračuje prvým príkazom za cyklom.
- Príkaz continue „skočí” na ďalšiu iteráciu cyklu, pričom nevykoná zvyšok tela cyklu.
Tieto príkazy treba používať s mierou, keďže robia program menej prehľadným a sú častým zdrojom chýb.
Hra „hádaj číslo” s príkazom break
Program uvedený vyššie môžeme prepísať bez boolovskej premennej s použitím nekonečného cyklu, z ktorého ale „vyskočíme” príkazom break, keď používateľ uhádne.
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
srand(time(NULL));
int num = rand() % 100 + 1;
cout << "Myslim si cislo od 1 po 100. Tvoj tip: ";
while (true) {
int guess;
cin >> guess;
if (guess < num) {
cout << "Prilis nizko. Iny tip: ";
} else if (guess > num) {
cout << "Prilis vysoko. Iny tip: ";
} else {
cout << "Spravne!" << endl;
break;
}
}
}
Viac o cykle for
Schéma cyklu for
Cyklus for sme doposiaľ používali iba veľmi základným spôsobom; jeho možnosti sú omnoho väčšia. Vo všeobecnosti možno schému cyklu for popísať nasledovne:
for (prikaz1; podmienka; prikaz2) {
postupnost_prikazov
}
Takýto cyklus potom pracuje nasledovne:
- Vykoná sa príkaz prikaz1.
- Kým platí podmienka podmienka, vykonáva sa telo cyklu postupnost_prikazov zakaždým nasledované príkazom prikaz2.
Uvedený cyklus for je teda typicky ekvivalentný nasledujúcemu cyklu while:
prikaz1;
while (podmienka) {
postupnost_prikazov
prikaz2;
}
(Drobnou výnimkou je prípad, keď telo cyklu for obsahuje príkaz continue. V takom prípade sa príkaz prikaz2 aj tak vykoná.)
Nasledujúce kúsky kódu napríklad obidva vypisujú čísla 1 až 9:
for (int i = 1; i <= 9; i++) {
cout << " " << i;
}
int i = 1;
while (i <= 9) {
cout << " " << i;
i++;
}
Cyklus for spravidla používame, ak má náš cyklus krátky a jednoduchý iterátor (prikaz2) a jednoduchú podmienku. V opačnom prípade väčšinou používame cyklus while.
Vypisovanie deliteľov od najväčších
Vráťme sa k programu na vypisovanie všetkých deliteľov čísla n z úvodu tejto prednášky. Tam sme deliteľov vypisovali v poradí od najmenšieho po najväčší, a to použitím cyklu
for (int i = 1; i <= n; i++)
Nahradením tohto cyklu cyklom
for (int i = n; i >= 1; i--)
získame program vypisujúci delitele v poradí od najväčšieho po najmenší.
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Zadajte cislo: ";
cin >> n;
cout << "Delitele cisla " << n << ":";
for (int i = n; i >= 1; i--) {
if (n % i == 0) {
cout << " " << i;
}
}
cout << endl;
}
Príklad behu programu:
Zadajte cislo: 30 Delitele cisla 30: 30 15 10 6 5 3 2 1
Rýchlejšie hľadanie deliteľov
Program na vypisovanie deliteľov môžeme o niečo urýchliť:
- Stačí si všimnúť, že i je deliteľ čísla n práve vtedy, keď je deliteľom čísla n číslo n/i.
- Číslo n/i teda môžeme rovno vypísať spoločne s i.
- Aspoň jedno z tejto dvojice čísel je navyše menšie alebo rovné odmocnine z n, čo znamená, že stačí prehľadať iba čísla i spĺňajúce túto podmienku.
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Zadajte cislo: ";
cin >> n;
cout << "Delitele cisla " << n << ":";
for (int i = 1; i*i <= n; i++) {
if (n % i == 0) {
cout << " " << i << " " << n / i;
}
}
cout << endl;
}
Cvičenie 1: Občas sa môže stať, že program vypíše niektorého deliteľa dvakrát. Kedy? Modifikujte telo cyklu for tak, aby program každého deliteľa vypísal práve raz.
Cvičenie 2: Vyskúšajte si rýchlosť rôznych variantov programu na vypisovanie deliteľov na veľkom vstupe, napríklad pre n = 1234567890.
Nekonečný cyklus for
V cykle
for (prikaz1; podmienka; prikaz2) {
postupnost_prikazov
}
môžu byť príkazy prikaz1 a prikaz2 aj prázdne – v takom prípade sa na ich mieste nič nevykoná. Podobne môže byť prázdna aj podmienka podmienka, ktorá sa v takom prípade interpretuje ako true.
Nekonečný cyklus možno teda napísať aj ako
for ( ; true; ) {
cout << "Hello, World!" << endl;
}
prípadne ako
for ( ; ; ) {
cout << "Hello, World!" << endl;
}
Vnorené cykly
Vypíšeme tabuľku násobilky, v ktorej bude v riadku i a stĺpci j súčin i ⋅ j.
- Použijeme dva vnorené cykly: jeden pôjde cez riadky, druhý cez stĺpce.
#include <iostream>
using namespace std;
int main() {
int n; // pokial ma ist nasobilka
cin >> n;
for (int riadok = 1; riadok <= n; riadok++) {
for (int stlpec = 1; stlpec <= n; stlpec++) {
cout << " " << riadok * stlpec;
}
cout << endl;
}
}
Ukážka výstupu pre n=5:
1 2 3 4 5 2 4 6 8 10 3 6 9 12 15 4 8 12 16 20 5 10 15 20 25
Ak pred každé číslo vypíšeme namiesto medzery " " tabulátor "\t", dostaneme krajší výstup
1 2 3 4 5 2 4 6 8 10 3 6 9 12 15 4 8 12 16 20 5 10 15 20 25
Cykly: zhrnutie
- Videli sme niekoľko príkladov využitia cyklov for a while.
- Cyklus for je možné zapísať ako while (a naopak).
- Z cyklu vieme vyskočiť príkazom break, prejsť na ďalšiu iteráciu príkazom continue. Používať s mierou.
- Euklidov algoritmus rýchlo nájde najväčšieho spoločného deliteľa dvoch čísel.