Študentské stránky | Bazár skrípt | Odkazovač | Linky

Hľadaj aj na .sk .cz webe


Maturitná otázka z informatiky č. 8

ŠTRUKTUROVANÁ TVORBA ALGORITMU

 

Vývojové diagramy - Pri zápise vychádzame z toho, že realizácia algoritmu začína 1. Krokom a každý krok algoritmu obsahuje informáciu o tom, ktorý krok sa bude vykonávať ako nasledujúci. Jednotlivé kroky algoritmu sa vykonávajú tak, ako sú napísané,, ak nie je explicitne dané poradie. Krok, ktorý sa realizuje má riadenie a po skončení ho odovzdá ďalšiemu kroku. Ak ním nie je bezprostredne nasledujúci, hovoríme o tzv. skoku. Odovzdávaniu riadenia z jedného kroku na druhý hovoríme tok riadenia, ktorý vyjadruje logickú následnosť vykonávania jednotlivých krokov algoritmu. Jedným z jazykov, ktoré zvýrazňujú tok riadenia, je aj jazyk vývojových diagramov.

Do značiek zapisujeme činnosť, ktorá sa má na danom mieste algoritmu urobiť. Tok riadenia sa zapisuje orientovanou spojnicou jednotlivých značiek tzv. hranou.

 

ZÁPIS ALGORITMICKÝCH KONŠTRUKCIÍ:

Začiatok algoritmu. Na tomto mieste sa začína realizácia algoritmu.

 

 

                                                                            Z

 

 

 


Koniec algoritmu. Na tomto mieste sa končí realizácia algoritmu.

 

 

                                                                           K

 

 

Operačný blok. Do operačného bloku zapisujeme akcie, ktoré sa majú vykonať, ak sa riadenie odovzdá tomuto bloku.

 

 

 

 

 

 


Rozhodovací blok. Do rozhodovacieho bloku zapisujeme podmienku. Jej splnenie alebo nesplnenie určí blok, ktorému sa v ďalšom kroku odovzdá riadenie.

 

 

 

 

 

 


    Základnou technikou konštrukcie algoritmov pre zložitejšie úlohy je ich rozklad na jednoduchšie podúlohy. Používame tri druhy rozkladov: konjunktívny, disjunktívny, repetičný.

    Konjunktívny rozklad – riešenie úlohy bude pozostávať z postupného riešenia všetkých podúloh, na ktoré sme danú úlohu rozložili.

    Disjunktívny rozklad – riešenie (konkrétnej) úlohy bude pozostávať z riešenia iba jednej, vybratej podúlohy.

    Repetičný rozklad  - riešenie úlohy bude pozostávať z niekoľko násobného opakovaného riešenia danej podúlohy.

    Týmto rozkladom zodpovedajú tieto algoritmické konštrukcie: konjunktívnemu rozkladu zodpovedá sekvencia, disjunktívnemu vetvenie a repetičnému rozkladu zodpovedá cyklus.

 

 

SEKVENCIA je alg. konštrukcia utvorená z akcií a1…..an zodpovedajúcich podúlohám p1…..pn na ktoré sme rozložili úlohu p. Sekvencia sa realizuje tak, že sa realizujú jednotlivé akcie a1…..an a to v poradí, v akom sú zapísané, ak nie je explicitne dané iné poradie. Zápis:

 


          a1                a2                              an

 

VETVENIE je alg. konštrukcia utvorená z podmienky b a akcií a1,a2. Realizuje sa tak, že ak je podmienka b splnená, realizuje akcia a1, inak akcia a2. Zápis:

 

 


                                                                         +    b   -

                                                                                       

 

 

 


Špeciálnym prípadom vetvenia je situácia, keď je jedna akcia, napríklad a2 prázdna. Potom ak je podmienka b splnená, realizuje sa akcia a1, inak sa nevykoná nič. Zápis:

 


                                                                                        b            -

 

 


                                                                                            +

                                                                                 a1

 

 

 


CYKLUS je alg. konštrukcia utvorená z podmienky b (podmienka opustenia cyklu) a akcie zodpovedajúcej podúlohe p, alebo akcií a1, a2 zodpovedajúcich podúlohám p1, p2.

Rozoznávame tri druhy cyklov: cyklus s podmienkou na konci, s podmienkou na začiatku, úplný cyklus (s podmienkou v „strede„ cyklu).

Cyklus s podmienkou na konci zapisujeme takto:

 

 

 

 


                                                                                        a

 

 

 


                                                                         -

                                                                                        b           

                                                                                             +

 

 

Realizuje sa akcia a potom sa zisťuje či je alebo nie je splnená podmienka. Otestujeme podmienku b. Ak je splnená, realizácia cyklu sa končí. Ak nie je splnená, opakuje sa proces realizácie akcie a testu podmienky b, a to dovtedy, kým podmienka b nie je splnená.

Cyklus s podmienkou na začiatku zapisujeme takto:

 

 

 

 


                                                                                                       +

                                                                                        b

 

 


                                                                                             -

                                                                                        a

 

 

Realizuje sa takto: Testuje sa podmienka b. Ak je splnená, realizácia cyklu sa končí. Ak nie je splnená, opakuje sa realizácia akcie a, a testu podmienky b, a to dovtedy, kým podmienka b nie je splnená.

Úplný cyklus zapisujeme takto:

 

 

 


                                                                                a1

 


                                                                                                         +

                                                                                        b

                                                                                           -

                                                                                a2                              

 

 

 

Realizuje sa takto: Realizuje sa akcia a1. Potom sa testuje podmienka b. Ak je splnená, realizácia cyklu sa končí. Ak nie je splnená, opakuje sa realizácia akcie a2, akcie a1 a testu podmienky b, a to dovtedy, kým podmienka b nie je splnená.

 

 

Na samotnú transformáciu vstupných údajov na výstupných používame operačné konštrukcie. Ich základom je výraz. Pod výrazom rozumieme predpis na získanie hodnoty. Určenie tejto hodnoty po dosadení hodnôt za premenné vyskytujúce sa vo výraze, nazývame vyhodnotením výrazu. Formálne výraz je utvorený z operandov a operátorov, prípadne zátvoriek. Operátory nám určujú, čo robiť, operandy, s čím to robiť.

OPERÁTORY: ÷, -, ×, /, div, mod.

RELAČNÉ OPERÁTORY: =, >, <.

Hodnotou relačných výrazov je tzv. logická hodnota pravda, nepravda. Logické výrazy utvorené s operandov nadobúdajúcich log. hodnoty pravda, nepravda a operátorov- konjunkcia (logický súčin)- disjunkcia (logický súčet) ù – negácia.

Logickým výrazom budeme hovoriť podmienky.

Pretože operátor negácie (ù ) mení log. hodnotu pravda na nepravda a naopak. Možno ním ovplyvňovať tok riadenia v algoritmoch s algoritmickými konštrukciami s rozhodovacím blokom. Ak je daná podmienka b a akcie a1 a a2, tak nasledujúce algoritmické konštrukcie vetvenia sú z hľadiska realizácie ekvivalentné. (obr.)

 

 

 

 

 

 

                         -          +                                    -            +

                                   b                                           b

 

 

     a2                      a1                      a1             a2

 

 

 

 

 


            Ak b tak a1 a2 * ak                                   ak ù b tak a1 inak a2 * a

 

Ak je podmienka b splnená, tj. b má hodnotu pravda, tak ù má hodnotu nepravda a v obidvoch prípadoch sa vykoná akcia a1. Ak je podmienka b nesplnená, tak ù b je splnená, v obidvoch prípadoch sa vykoná a2.

Podobne možno ovplyvňovať tok riadenia aj v cykle. Zápis cyklov s negovanou podmienkou ukončenia cyklu (zotrvania v cykle) sú na obr. 1.

Ak ako operandy vo výrazoch používame premenné, tak nato, aby sme výraz mohli vyhodnotiť, musí mať premenná pred vyhodnocovaním výrazy nejakú hodnotu. Môže je nadobudnúť dvoma spôsobmi: príkazom vstupu alebo príkazom priradenia.

Príkaz vstupu budeme písať v tvare: ( a1, a2…..an), kde a1…asú premenné.

Realizácia: zo vstupného zariadenia procesora sa prečíta a hodnôt, ktoré nadobudnú premenné a1…..an v poradí, ako sú uvedené.

Príkaz priradenia má tvar p: =v, kde p je premenná, v je výraz.

 

 

 


                                                                                             -

         a                                 b                                    a1

 


                                                                               +                                                               -

+           b                            a                                       b

                         -                                                                 +

                                                                                                                                                         a2

 opakuj a pokiaľ ù b                   opakuj pokiaľ ù b                           opakuj a1 pokiaľ ù b

 *opakuj                                   rol a                                             rol a2

                                        *opakuj                                         *opakuj

 

Realizácia: vyhodnotí sa výraz v a jeho hodnota sa priradí premennej p. Po realizácii príkazu bude mať premenná p hodnotu, ktorú mal výraz v s hodnotami premenných platnými pred jeho realizáciou.

 

VÝSTUP – tlač hodnôt získaných realizáciou algoritmu možno zabezpečiť príkazom výstupu, ktorý má tvar: pis (a1…..an).

 

Projekt hostuje Slovaknet.
Ubytovanie | Kúpele | Austrália | Práca v Kanade | Catering | Last minute dovolenka