Návrat na detail prednášky / Stiahnuť prednášku / Technická Univerzita Košice / Fakulta Elektrotechniky a Informatiky / Počítače a algoritmizácia

prednáška 3 (3_pr.doc)

3. Metódy algoritmizácie a základné zložky algoritmu

3.1.Metódy algoritmizácie - metóda "zhora nadol"

                                 - metóda " zdola nahor"

                                 - hybridná metóda

● metóda "zhora nadol" → Algoritmus je zápis postupu, kt. je použiteľný pre riešenie určitej triedy problémov Ak postup riešenia rozkladáme na jednoduchšie operácie, až dospejeme k elementárnym krokom → potom tento postup návrhu algoritmu označujeme metóda "zhora nadol"

Pr. Kvadrantická rovnica- budeme chcieť na základe navrhnutého algoritmu napísať program, kt. bude riešiť rovnice, kt. koeficienty sú uložené v súbore A. Výsledok sa má uložiť do súboru B.

Najhrubšia formulácia môže mať tvar:

Pokiaľ nenarazíte na koniec súboru A riešte rovnice, určené koeficientami uloženými v súbore A a výsledky zapisujte do súboru B.

- je nutné upresniť význam:

"riešte rovnice, určené..." - rozklad na jednoduchšie kroky"

Algoritmus hrubého riešenia:

1. Vykonaj úvodné operácie.

2. pokiaľ nenarazíš na koniec súboru A, opakuj kroky 3-5, potom prejdi na krok 6.

3. Prečítaj zo súboru koeficienty a,b,c

4.Vyrieš kvadrantickú rovnicu s koeficientami a,b,c.

5.Zapíš výsledky do súboru B a vráť sa na krok 2.

6. Vykonaj záverečné operácie.

Kroky 1., 4., 6 sa dajú spresniť.

Budeme sa zaoberať iba krokom 4. na riešenie KR.

4a. Vypočítaj d=b2-4ac

4b. Ak je d<0, pokračuj bodom 4f, inak pokračuj bodom 4c

4c. Priraď d=odmocnina D

4d. Rovnica má korene x1,2=-b+-d/2a

4e. Pokračuj krokom 5

4f. Priraď d=odmocnina-d

4g. Rovnica má korene x1,2=-b+-id/2a

i je imaginárna jednotka

Poz.Upresniť postup, ak nastane chyba pri otvorení súboru, prípadne obsahuje chybné údaje,... formát vstupných a výstupných údajov

● metóda "zdola nahor": postupujeme od elementárnych krokov - vytvárame prostriedky, kt. umožnia vyriešiť daný problém.

● hybridná metóda: kombinácia predošlých dvoch metód (vytváranie programov CASE).

3.2 Základné zložky algoritmov-základné riadiace štruktúry

V algoritmoch sa stretávame s troma základnými konštrukciami, kt. označujeme:

● postupnosť (sekvencia)

● vetvenie (selekcia)

● cyklus (iterácia)

Postupnosť(sekvencia) → najjednoduchšia riadiaca štruktúra. Je tvorená jedným alebo niekoľkými krokmi, kt. sa vykonávajú práve raz v danom poradí.

(Príklad KR: kroky 4c-4e)

So sekvenciou sa stretávame pri globálnom popise algoritmu → pri upresnení → zložitejšie konštrukcie!

Vetvenie(selekcia) → je taká štruktúra, kt. v procese vykonávania algoritmu umožňuje vyberať rôzne alternatívy riešenia podľa splnenia či nesplnenia zadaných podmienok.

Vetvenie môže byť realizované:

Preskok

činnosť

Podmienka

Čin 2

Čin 1

splnená

nesplnená

Dvojcestné vetvenie

a. Preskok - po vyhodnotení podmienky sa uvedená činnosť (sekvencia operácií) buď vykoná, alebo sa preskočí (v príklade 4b)

b. Dvojcestné vetvenie - po vyhodnotení logickej podmienky sa vykoná práve jedna z uvedených činností

(Ak je podmienka splnená- potom sa vykoná sekvencia príkazov tvoriacich činnosť Čin1; v opačnom prípade sa vykoná sekvencia príkazov Čin2)

Po ukončení ľubovoľnej z týchto dvoch alternatív sa pokračuje ďalej v algoritme (viaccestné vetvenie → vnorenie dvojcestných vetvení)

c. Prepínač - modifikácia viaccestného vetvenia

Pri viaccestnom vetvení -každá z vetiev je špecifikovaná pre celú množinu hodnôt podmienky.

Pri prepínači-je každá vetva určená pre konkrétnu hodnotu výrazu uvedeného v podmienke

Výraz

Činnosť 1

Činnosť 2

Činnosť n-1

Činnosť n

=hn

hn-1

=h2

=h1

Použitie vetvení znamená zaradenie rozhodovacieho procesu do vykonávania algoritmu a súvisí s vyhodnotením PODMIENKY.

CYKLY

Cykly(iterácie)-predstavujú časť algoritmu, kt. sa opakuje pokiaľ je splnená podmienka opakovania.

Cyklus sa skladá z: -podmienky opakovania

                               -tela cyklu

Počet opakovaní teda cyklu môže byť dopredu zadaný alebo je odvodený od splnenia podmienky -

a.cyklus s podmienkou na začiatku (príkaz jazyka C: while, for)

b.cyklus s podmienkou na konci (príkaz jazyka C: do-while)

c.cyklus s daným počtom opakovaní (aritmetický cyklus) (príkaz jazyka C: for)

a.,b. sú logické cykly;

V príklade riešenia kvadrantickej rovnice tvoria kroky 2-5 cyklus s podmienkou na začiatku.

A. Cyklus s podmienkou na začiatku

1.Vyhodnotenie podmienky P

2. Ak je podmienka P splnená vykonajú sa operácie dané štruktúrou S (telo cyklu) a nasleduje návrat na začiatok cyklu

3. Ak podmienka P nie je splnená cyklus končí.

[Pozn. cyklus sa nemusí vykonať ani raz]

P

S

nie

áno

B. Cyklus s podmienkou na konci:

1.cyklus začína svoju činnosť operáciami v sekvencii S

2.ak podmienka P je splnená návrat na bod 1 (začiatok tela cyklu)

3.ak podmienka P nie je splnená vykonávanie (logického) cyklu je ukončené  [Cyklus sa vykoná vždy raz oproti prípadu A.]

splnená

S

P

nie

Nesplnená

áno

Obr. 7 Cyklus

C.cyklus s daným počtom opakovaní

c1)aritmetický cyklus(for) - štruktúra cyklu

c2)logický (cyklus-a)while

1. Inicializácia cyklu

2. Test podmienky

3. Vykonanie tela cyklu

4. Aktualizácia

I≤N

I ← 1

I ← I+1

S

→ Telo cyklu

→ Aktualizácia

áno

nie

→ Inicializácia pre riadiacu pr. cyklu

I = 1,...,N

S

Štruktúra cyklu

Obr. 9 Cyklus s daným počtom opakovaní