Diagrami poteka in psevdokod

 

V prejšnjem poglavju smo spoznali nekaj načinov kako predstavimo algoritem. V tem poglavju bomo spoznali način predstavitve, ki jo bomo uporabljali za opis naših algoritmov. Uporabljali bomo grafično predstavitev s pomočjo diagramov poteka in besedilno predstavitev s pomočjo psevdokoda.

 

Psevdokod

Psevdokod predstavlja zapis algoritma  z množico korakov, zapisanih v mešanici naravnega jezika in matematične notacije. Oblika zapisov korakov v psevdokodu je podobna zapisu stavkov v postopkovnih programskih jezikih. Če zapisujemo algoritme s pomočjo psevdokoda, se je pametno zmeraj najprej vprašati:

• katere vhodne podatke moramo vnesti (kaj je vhod v algoritem),
• kaj je rezultat izvedbe algoritma (kaj je njegov izhod),
• katere operacije moramo izvesti, da iz vhodnih podatkov dobimo izhodni rezultat in
• kakšen je algoritem? Omogočati mora vnos vhodnih podatkov, izvedbo operacij in vračanje oziroma izpis rezultatov njegovega .

Poglejmo si primere psevdokodov za zapis zaporedja ukazov, odločitvenega stavka in iteracije.

 

Zaporedje ukazov

 

Primer psevdokoda, ki definira zaporedje ukazov, je algoritem za opis postopka izračuna obsega in ploščine kroga:

 

VHOD:

• polmer kroga

IZHOD:

• ploščina
• obseg

Kako izračunamo obseg in ploščino?

• Ploščina = ∏ r²
• Obseg = 2 ∏ r

ALGORITEM:

• Vnesi polmer.
• Izračunaj ploščino.
• Izračunaj  obseg.
• Izpiši rezultat izračuna obsega in ploščine.

 

Odločitveni stavek (izbira)

 

V večini računalniških programov se pogosto vprašamo ali podatki, ki smo jih dobili iz vhoda oz. iz predhodnih izračunov, ustrezajo določenemu pogoju.  V vsakdanjem življenju bi se lahko vprašali ali je kava že skuhana. V  tem primeru, bi preverili, če je mešanica vode, sladkorja in kave že zavrela. Če je mešanica že zavrela, izklopimo stikalo in odstavimo pripravljeno kavo. Podobno je v svetu programiranja.

 

Pogledali si bomo primer psevdokoda za algoritem, ki poišče večjega od dveh števil:

 

VHOD:

  dve števili

 

IZHOD:

  vrednost večjega izmed dveh števil

 

ALGORITEM:

    vnesi števili

     if (prvo število > drugo število)

         izpiši prvo število

    else

         izpiši drugo število

 

Iz algoritma lahko vidimo, da je naš pogoj (prvo število > drugo število). Če je pogoj izpolnjen (prvo število je večje od drugega), izpišemo prvo število. Če pogoj ni izpolnjen (prvo število ni večje od drugega), izpišemo drugo število. Pred zapisom pogoja uporabljamo besedo if, ki v slovenščini pomeni "če" oziroma "ali je".  S stavkom if (prvo število > drugo število), se v našem primeru vprašamo, če je prvo število večje od drugega. Z ukazi, ki so za besedo if, povemo, kaj narediti, če je pogoj izpolnjen. Z ukazi, ki so za besedo else pa povemo kaj narediti, če pogoj ni izpolnjen.

 

Nasvet:

 

Vse ukaze, za katere bi želeli, da se izvedejo v okviru dela if ali else, zamaknite za nekaj praznih mest, da boste lažje razločili, kateri ukazi se naj izvedejo, če je pogoj izpolnjen in kateri,  če pogoj ni izpolnjen.

 

Ponavljanje

 

Poglejmo si primer algoritma, ki sešteje tri števila.

 

VHOD:

• tri števila

IZHOD:

• Vsota treh števil

Operacije, ki jih moramo izvesti:

• Inicaliziramo vsoto in števec vnesenih števil na 0.
• Vnašamo števila ter jih prištevamo vsoti tako dolgo, dokler nismo vnesli vseh treh števil.
• Izpišemo vsoto števil.

ALGORITEM:

 

Inicializiraj vsoto.

Inicializiraj števec na 0.

while  (števec < 3)

    Števcu prištej 1.

    Vpiši število.

    Vsoti prištej število.

Izpiši vsoto.

 

V algoritmu uporabljamo besedo while za opis ponavljanja zaporedja stavkov, ki so zapisani nekoliko zamaknjeno. To zaporedje ponavljamo tako dolgo dokler je pogoj izpolnjen (dokler je števec manjši od 3).

 

Poglejmo si še algoritem, ki izračuna  koliko denarja boste dobili od banke po n letih ob začetni vlogi. Po vsakem letu varčevanja  izpišemo  glavnico. Za definiranje ponavljanja bomo uporabili stavek for:

 

 

VHOD:

• vrednost vloge,
• obrestna mera v procentih,
• število let varčevanja.

 

IZHOD:

• vrednost glavnice po n letih.

 

Operacije, ki jih moramo izvesti:

• Vpisati moramo vrednost vloge, obrestno mero in število let varčevanja.
• Za vsako leto moramo izračunati novo glavnico in izpisati njeno vrednost. Izračun glavnice se izvaja po naslednji formuli:
  • nova glavnica = začetna glavnica * ( 1 + obrestna mera) ^{število let}

 

 ALGORITEM:

            Vpiši obrestno mero, vrednost vloge ter število let varčevanja

            for  za vsa leta varčevanja

                        Izračun nove glavnice.

                        Izpis nove glavnice.

 

Vidimo, da je v določenih primerih pametno uporabiti zapis algoritma, ki uporablja besedo for. Takšen zapis uporabljamo takrat, ko lahko določimo kolikokrat se bo v odvisnosti od vhodnih podatkov ponavljanje izvedlo.

Diagram poteka

Diagrami poteka omogočajo grafični prikaz izvajanja posameznih delov programa (ukazov, podprogramov, segmentov programske kode). Uporabljamo jih predvsem v primerih, ko želimo z naročnikom programa razjasniti ali naš algoritem ustreza željam naročnika. Večina ljudi lažje iz narisane slike razbere korake postopka, kot pa če za razlago postopka napišemo besedilo, ki je dolgo nekaj strani.

 

Osnovne komponente digramov poteka so:

• Rombi – predstavljajo stavke, ki omogočajo komunikacijo algoritma z zunanjim svetom. S temi stavki vnašamo podatke ali izpisujemo rezultate;
  
• Škatle predstavljajo stavke, kjer nekaj izračunavamo (npr. izračunamo obseg in kvadraturo parcele);
• Deltoidi predstavljajo pogojne stavke. V teh stavkih algoritem preveri pogoj in glede na to ali je pogoj izpolnjen ali ne, preusmeri tok izvajanja programa v eno ali drugo vejo ;
• Krogi predstavljajo začetek in konec algoritma. V večini primerov jih izpustimo.
• Črte s puščicami – predstavljajo tok izvajanja programa.

Poglejmo si primere diagramov poteka za zapis zaporedja ukazov, odločitvenega stavka in ponavljanja.

 

Zaporedje ukazov

 

S takšnimi diagrami opisujemo kako se zaporedno izvedejo ukazi v programu. Poglejmo si primer diagrama poteka za algoritem, ki opisuje postopek izračuna obsega in ploščine kroga. Najprej vnesemo polmer, nato izračunamo obseg in ploščino kroga, zatem pa izpišemo izračunana obseg in ploščino. Kroga, ki predstavljata zaćetek in konec algoritma v večini algoritmov izpustimo.

 

 

 

Odločitveni stavek ( izbira)

 

 

Na zgornji sliki vidite diagram poteka, v katerem algoritem najprej preveri ali je vnesena ocena večja od 5. Če je ocena večja od 5, algoritem izpiše, da je študent opravil izpit, če je ocena manjša od 5, pa algoritem izpiše, da študent ni opravil izpita.

 

 

Ponavljanje

 

 

Iz gornje slike vidimo kako se izvaja ponavljanje v odvisnosti od vrednosti pogoja (i<j). V primeru, da je i manjši od j, se izvede stavek, ki poveča i za 1. V primeru, da je i enak ali večji od j, pa se ponavljanje konča.

 

 

Poglejmo si še primer diagrama poteka pri  stavku do while:

 

 

 

Za domačo nalogo napišite algoritem za program, ki bo izračunal porabo goriva na 100 km. Če rešitve ne znate sami določiti, si pomagajte z namigom:

1. VHOD:
       - Število prevoženih kilometrov - kilometri   
       - Število litrov, ki smo jih natočili - količina_goriva
2. IZHOD:
       - Poraba na 100 km - poraba_na_100_km         
3. ALGORITEM:
       - Vnesi število prevoženih kilometrov in porabo goriva.
       - Izračunaj porabo goriva na 100 km.
       - Izpiši porabo na 100 km.
4. Izračunaj porabo na 100 km - za izračun uprabimo sklepni račun
       - kilometri   ... količina_goriva
       - 100          ... poraba_na_100_km
5.     - Poraba se izračuna po formuli: poraba_na_100_km = (količina_goriva * 100) / kilometri