Video (08.10.2024)
Prezentácia
Zdrojový kód
Poznámky k prednáške
Vlastnosti algoritmov - Karel goes Fibonacci
- Dnes budeme pokračovať riešením rôznych úloh pomocou robota Karla, pričom sa pokúsime zamerať na rôzne vlastnosti algoritmov.
- Fibonacciho postupnosť je typickým problémom, ktorý sa rieši počas základov algoritmizácie. Viac info tu.
- Pozrime sa na nasledujúci príklad, kde robot Karel na prázdnej ulici položí značky tak, aby vyjadrovali Fibonacciho postupnosť (fibonacci.c, fibonacci.kw, fibonacci2.kw):
CORNER FACING BEEP-BAG BEEP-CORNER
(1, 1) EAST 100 0
ST.+-------------------------------+
2 | . . . . . . . . |
| |
1 | > . . . . . . . |
+-------------------------------+
1 2 3 4 5 6 7 8 AVE.
- Príklad rieši Fibonacciho postupnosť pomocou robota Karla, ktorý ale nevie počítať. Podstatou príkladu je ukázať, ako je v Karlovom svete možné spočítať dve čísla bez toho, aby bolo nutné použiť premenné a matematiku.
- Príklad je riešený pomocou rekurzie. Prvok je rekurzívny, ak sa čiastočne skladá, alebo je definovaný pomocou samého seba.
- Rekurzia je silným nástrojom najmä pri matematických definíciách, napr. prirodzené čísla, stromové štruktúry, funkcie (faktoriál, Fibonacciho čísla, atď.).
- Prostriedkom pre vyjadrenie rekurzie v programoch je podprogram (funkcia), ktorej identifikátor slúži na rekurzívnu aktiváciu jeho tela.
- Rekurzívne funkcie dávajú možnosť nekonečných výpočtov a je potrebné riešiť problém ukončenia výpočtu.
- Kedy používať rekurziu:
- Rekurzívny program je vhodný, ak riešený problém alebo používané údaje sú definované rekurzívne.
- Použitie rekurzie nezaručuje, že algoritmus predstavuje najlepšie riešenie problému.
- Každý rekurzívny program možno transformovať na iteratívny tvar (pomocou cyklov).
- Pri zložitejších rekurzívnych schémach je však transformácia na iteratívny tvar veľmi nepraktická.
- Programy, ktoré sú svojou podstatou rekurzívne (skôr než iteratívne), majú byť implementované pomocou rekurzívnych funkcií.
Podmienené výrazy
- AND
- Reprezentujú ho znaky &&
- Pravdivostná tabuľka:
- 1 && 1 vráti 1, true && true vráti true
- 1 && 0 vráti 0, true && false vráti false
- 0 && 1 vráti 0, false && true vráti false
- 0 && 0 vráti 0, false && false vráti false
- OR
- Reprezentujú ho znaky ||
- Pravdivostná tabuľka:
- 1 || 1 vráti 1, true || true vráti true
- 1 || 0 vráti 1, true || false vráti true
- 0 || 1 vráti 1, false || true vráti true
- 0 || 0 vráti 0, false || false vráti false
- NOT (negácia)
- Reprezentuje ju znak !
- Pravdivostná tabuľka:
- !1 vráti 0, !true vráti false
- !0 vráti 1, !false vráti true
- V nasledujúcom príklade chceme, aby robot Karel neustále prechádzal od jednej hranice sveta k druhej vo vertikálnom smere. Podmienku otočenia robota na začiatku programu (do vertikálneho smeru) môžeme zapísať rôznymi spôsobmi (eternal_and.c, empty.kw):
not_facing_north() && not_facing_south()
vs
facing_east() || facing_west()
vs
!facing_north() && !facing_south()
return
- Umožňuje predčasne ukončiť vykonávanie aktuálnej funkcie.
- Ak funkcia má návratovú hodnotu,
return
sa použije spolu s konkrétnou návratovou hodnotou (eternal_or.c, empty.kw):
int facing_horizontal() {
if (facing_east() || facing_west()) {
return 1;
}
return 0;
}
- Ak nechceme vrátiť celočíselnú hodnotu, môžeme vrátiť pravdivostnú hodnotu
true
alebofalse
:
bool facing_horizontal() {
if (facing_east() || facing_west()) {
return true;
}
return false;
}
- Avšak v takom prípade sa musíme obrátiť na knižnicu, v ktorej je typ
bool
zadefinovaný:#include <stdbool.h>
. - V prípade robota Karla je knižnica
stdbool
už zahrnutá v rámci hlavičkových súborovkarel.h
asuperkarel.h
. - Pozrime sa na iný príklad pre vyplnenie dier na ceste: road_incomplete.c. Na prvej mape road.kw sa algortimus zdá byť úplný:
CORNER FACING BEEP-BAG BEEP-CORNER
(1, 2) EAST 2 0
ST.+-------------------+
2 | > . . . . |
|---+ +---+ +---|
1 | . | 1 | . | . | . |
+-------------------+
1 2 3 4 5 AVE.
- No na mape road2.kw vidíme, že algoritmus je neúplný:
CORNER FACING BEEP-BAG BEEP-CORNER
(1, 2) EAST 5 0
ST.+---------------------------+
2 | > . . . . . . |
| | +-------+ +---+ |
1 | . | . | . . | 1 | . | . |
+---------------------------+
1 2 3 4 5 6 7 AVE.
- Opravíme ho pridaním podmienky pred hlavný cyklus:
int main(){
turn_on("road2.kw");
if (right_is_clear()) { // this was added
fill_pothole();
}
while (front_is_clear()) {
step();
if (right_is_clear()) {
fill_pothole();
}
}
turn_off();
return 0;
}
- Vráťme sa však k príkazu
return
. Ak funkcia nemá návratovú hodnotu,return
sa použije ako samostatný príkaz (road_return.c, road2.kw):
void fill_pothole() {
if (right_is_blocked()) {
return;
}
turn_right();
step();
if (no_beepers_present()) {
put_beeper();
}
turn_back();
step();
turn_right();
}
Object-like Macros
- Čo je to makro? Príkaz preprocesora.
- Makrá používame, ak potrebujeme zjednotiť výskyt hodnôt v kóde, napr. (road_macro.c, road2.kw):
#define SPEED 200
void turn_right() {
set_step_delay(0);
turn_left();
turn_left();
set_step_delay(SPEED);
turn_left();
}
break vs continue
- Skomplikujme si náš príklad: highway.c, highway.kw:
CORNER FACING BEEP-BAG BEEP-CORNER
(1, 4) EAST 99 0
ST.+-----------------------------------+
6 | . . . . . . . . . |
| |
5 | . . . . . . . . . |
| |
4 | > . . . . . . . . |
| | +---+ | +---+ | | |
3 | . | 1 | . | . | . | . | . | 1 | . |
| | | +---+ | | | | |
2 | . | 1 | . . | 1 | . | 1 | . | . |
| +---+ | | +---+ | |
1 | . | . . . | . | . . | . | . |
+-----------------------------------+
1 2 3 4 5 6 7 8 9 AVE.
- Čo sa stane, ak chceme vynechať tú dieru na ceste, ktorá už je označená značkou (highway2.kw)?
CORNER FACING BEEP-BAG BEEP-CORNER
(1, 4) EAST 99 0
ST.+-----------------------------------+
6 | . . . . . . . . . |
| |
5 | . . . . . . . . . |
| |
4 | > . . . 1 . 1 . . |
| | +---+ | +---+ | | |
3 | . | 1 | . | . | . | . | . | 1 | . |
| | | +---+ | | | | |
2 | . | 1 | . . | 1 | . | 1 | . | . |
| +---+ | | +---+ | |
1 | . | . . . | . | . . | . | . |
+-----------------------------------+
1 2 3 4 5 6 7 8 9 AVE.
- Pozrime sa teraz na príkazy
break
acontinue
. Umožňujú predčasne ukončiť vykonávanie aktuálnej iterácie (slučky cyklu). - Príkaz
break
ukončí vykonávanie aktuálnej slučky cyklu a navyše ukončí vykonávanie celého cyklu (highway_break.c, highway2.kw):
while (front_is_clear()) {
step();
if (beepers_present()) {
break;
}
fill_pothole();
}
- Kým príkaz
continue
ukončí vykonávanie aktuálnej slučky cyklu a pokračuje opäť podmienkou cyklu (neukončí vykonávanie cyklu) (highway_continue.c, highway2.kw):
while (front_is_clear()) {
step();
if (beepers_present()) {
continue;
}
fill_pothole();
}
- Samozrejme, aj tu platí, že úloha má viac riešení. V našom prípade sa dokonca môžeme vyhnúť príkazom
break
čicontinue
:
while (front_is_clear()) {
step();
if (no_beepers_present()) {
fill_pothole();
}
}
Doplňujúce zdroje
- Break vs continue
- Typ
bool
: c-reference, cplusplus.com