Ciele cvičenia

Cvičenie bude zamerané na precvičovanie algoritmizácie pomocou Karla s použitím knižnice superkarel.h. V rámci cvičenia bude vysvetlená problematika rekurzie v programovaní a tiež si ukážeme dôležitosť plánovania algoritmu, ešte pred samotným písaním kódu, aj za použitia vývojových diagramov. Pre dosiahnutie uvedených cieľov je  nutné osvojiť si aj logické výrazy a logické operátory (AND, OR, NOT).




Dôležité linky a odporúčaná literatúra

[1] KPI-FEI-TUKE, Cvičenie č. 4

[2] Microsoft, Vytvorenie základného vývojového diagramu vo Visiu

[3] Tutorialspoint, Logical Operators in C

[4] KPI-FEI-TUKE, Prednáška č. 3 


Úloha 1.1

(úlha prevzaná z [1])

Vytvorte program multiplier, v ktorom bude Karol prechádzať postupne celým svetom a zdvojnásobovať počet značiek, ktoré nájde. Samozrejme, bez použitia premenných. Nakoniec sa Karol vráti na pozíciu kde začal. Vaše riešenie otestujte na svete multiplier.kw. 


Svoj program skompilujete nasledovne:

gcc -Werror -Wall multiplier.c -lsuperkarel -lcurses -o Multiplier




 

Kostra programu (aby sme urýchlili priebeh cvičenia):

// HLAVICKY
#include <karel.h>
#include <superkarel.h>
// DEKLARACIE VLASTNYCH FUNKCII
void new_line();
void turn_right();
void multiply();
void go_home();
// MAIN
int main()
{
    turn_on("multiplier.kw");
    // TU BUDE HLAVNY CYKLUS   
    turn_off();
    return 0;
}
// TU BUDU DEFINICIE FUNKCII


Začiatočná situácia

Koncová situácia

Najprv algoritmus potom kód!

Pri programovaní je dobrým zvykom najprv premyslieť prečo, čo a ako chcem spraviť. Mnoho programátorov začína písaním kódu. To však neznamená, že si nepremysleli svoj postup. Jednoducho sú skúsení. Predmet ZAP má študentom pomôcť naučiť sa myslieť algoritmicky. V nasledujúcom texte si na príklade uvedenom vyššie ukážeme ako by taká tvorba algoritmu mala prebiehať. 

PREČO?

Táto otázka znie triviálne ale je potrebné si ju položiť minimálne jedného dôvodu - má zmysel daný problém riešiť? Dôvodov pre riešenie problému môže byť nespočetne veľa. Uvedieme len príklady niekoľkých. 

  • Aby som sa niečo naučil a čas strávený na univerzite nebol iba strateným časom.  
  • Aby som získal zápočet/skúšku.
  • Aby som dostal svoju výplatu.
  • Aby som vyvinul nové zariadenie/aplikáciu, ktoré mi uľahčia život.
  • ...

ČO?

Túto otázku si programátor kladie hneď ako je rozhodnutý ísť "do toho". Rovnako ju kladie aj svojím klientom, ktorí od neho chcú, aby im vyvinul aplikáciu/program.

  • Čo má daný program robiť? 
  • Čo bude vstupom daného programu?
  • Čo má byť jeho výstupom?

Pre náš príklad: 

  • Čo má daný program robiť?  - Robot Karol má prejsť cez všetky pozície a ak na pozícii nájde značku, tak jej hodnotu zdvojnásobí. Nakoniec sa vráti na začiatočnú pozíciu.  
  • Čo bude vstupom daného programu? - Vstupom programu je zadaná mapa multiplier.kw.
  • Čo má byť jeho výstupom? - Výstupom bude mapa zobrazená na obrazovku. Tam bude Karol na svojej počiatočnej pozícií a značky budú zdvojnásobené. 


AKO?

Tu prichádza ku slovu ALGORITMIZÁCIA. Tu si musí programátor klásť ďalšie otázky tie môžu byť rôzneho charakteru ale určite by si mal položiť tieto:

  • Aké vstupné parametre je potrebné nastaviť a aké sú vstupné predpoklady?
  • Aké hlavné cykly (režimy) bude program vykonávať?
  • Aké sú rozhodovacie podmienky pri zmene rutiny a ukončenia programu?
  • Mám dostatočnú úroveň poznania problematiky? - poznanie sa zlepší jedine praxou 
  • Ak je program funkčný, je potrebné si položiť otázku: Je môj program optimálny? Je možné niečo vylepšiť?

Poďme odpovedať na tieto otázky pre náš príklad:

  • Aké vstupné parametre je potrebné nastaviť a aké sú vstupné predpoklady? - Predpokladáme, že veľkosť mapy bude pre tento príklad vždy rovnaká a Karol bude vždy štartovať z ľavého dolného rohu smerom na východ. 
  • Aké hlavné cykly (režimy) bude program vykonávať? -
    • 1. Karol musí prechádzať celým svetom.
    • 2. Ak je Karol v pravom hornom rohu, musí sa vrátiť tam kde štartoval.
    • 3. Ak narazí na značku, musí ju zdvojnásobiť
  • Aké sú rozhodovacie podmienky pri zmene rutiny?
    • Pri prechode celým svetom - Nemal by prejsť o riadok vyššie? Je už v pravom hornom rohu? 
    • Pri značkách - Stojí na značke?
    • Návrat na štart - Skončil sa už hlavný cyklus prechádzania celého sveta?

Ak máme zodpovedané tieto otázky mali by sme mať oveľa lepšiu predstavu ako chceme úlohu vyriešiť. Všimnime si, že stále nebol napísaný ani riadok kódu a pritom sme pri riešení úlohy výrazne pokročili.

Je nezmysel programovo implementovať všetko naraz. Z otázok zodpovedaných vľavo je jasné, že úlohu musíme riešiť postupne. Svoj postup môžeme zapísať v textovej podobe napríklad takto:

  1. Najprv vytvoríme hlavný cyklus, tak aby Karol prechádzal celým svetom.
  2. Ak ním prešiel tak naprogramujeme jeho návrat na štart.
  3. Ak sme spravili bod 1. a 2. tak máme spravenú kostru programu a môžeme sa zamýšľať nad zdvojnásobovaním značiek, ktoré budeme robiť rekurentne. O rekurzívnom programovaní si povieme  viac tu.  


Vývojový diagram

Samotný algoritmus môžeme vyjadriť v grafickej podobe vo forme vývojového diagramu. Vývojové diagramy sú užitočné ale častokrát časovo veľmi náročné. Pre túto úlohu si ukážeme ako by taký "vývojak" mohol vyzerať ale pri riešení Vašich zadaní ho kresliť nebudete. Ak budete pracovať na zložitejších problémoch v rámci BC prác, tak je vhodné dokumentáciu doplniť vývojovým diagramom.  

Vývojový diagram bude pozostávať z troch čiastkových diagramov.

  • Diagram pre hlavný program
  • Diagram pre posun na ďalší riadok ( napr. new_line() )
  • Diagram pre návrat na štart ( napr. go_home() )
  • Diagram pre zdvojnásobenie (napr. multiply() ).


Flowchart Tutorial ( Complete Flowchart Guide with Examples )

Význam jednotlivých symbolov nájdete aj v literatúre [2].

Hlavný program 

Funkcia návratu na začiatok sveta go_home()



Funkcia zdvojnásobenia značiek multiply()

Funkcia posunu o riadok vyššie new_line()