Jazyk C (príklady) - Algoritmy

Základy informatiky - jazyk C

---

Riešené príklady

Algoritmy

Prvé programy

Podmienky

Cykly

Polia

Funkcie

Súbor

Vzorové príklady

Neriešené príklady

---

zdroj: Juraj Ďuďák, Zbierka úloh z algoritmizácie pre predmet Základy informatiky

ISBN: 978-80-8075-199-9

Obsah

V tejto kapitole budú ukázaná tvorba jednoduchých vývojových diagramov. Budú ukázané základné prvky algoritmizácie úloh, použitie rozhodovania, opakovania istého počtu operácií. K zvládnutiu tejto kapitoly sa predpokladá znalosť grafických značiek použitých pri tvorbe vývojových diagramov.

Grafické značky vývojových diagramov

Medzi základné stavebné bloky vývojových diagramov (VD) patria bloky, ktoré reprezentujú

• začiatok / koniec VD
• vykonávací blok
• rozhodovací blok
• spojka
• vstup / výstup dát
• orientované spojnice blokov

[Vývojové stavebné bloky]

Príklady

Absolútna hodnota

Zadanie: Vieme, že absolútna hodnota je definovaná ako vzdialenosť čísla od začiatku súradnicového systému (resp. od nuly). Nakreslite vývojový diagram, ktorý by znázorňoval výpočet absolútnej hodnoty.

Analýza problému: Pre absolútnu hodnotu reálnych čísel platí:

• abs(x) = x
• abs(-x) = x

Inak povedané, pre x>=0, je absolútna hodnota x rovná práve x, pre x<0 je absolútna hodnota x rovná -1*x. Teda, stačí nám zistiť, či je x menšie ako nula.

Kvadratická rovnica

Zadanie: Navrhnite algoritmus výpočtu koreňov kvadratickej rovnice ax2+bx+c=0. Vstupom do algoritmu budú koeficienty a, b, c, a výstupom budú korene kvadratickej rovnice x1,2.

Analýza problému: Riešenie tejto rovnice je známe, úlohou je tento problém znázorniť v podobe vývojového diagramu. Vieme, že kvadratická rovnica má dva korene (x1 a x2). Tieto korene môžu byť rôzne, alebo riešením je jeden dvojnásobný koreň. Toto zistíme pomocou výpočtu diskriminantu kvadratickej rovnice. Diskriminant je definovaný ako D=b2-4ac Rozoberme si jednotlivé prípady riešenia.

• D>0 : Rovnica má dva korene: x1=(-b+D1/2)/4ac, x2=(-b-D1/2)/4ac
• D=0 : Rovnica má jeden dvojnásobný koreň: x1,2=-b/4ac
• D<0 : Rovnica má riešenie na množine komplexných čísel:

Vieme, že i2=-1. (i je komplexná jednotka). Potom výpočet druhej odmocniny diskriminantu je (D)1/2=(i2 * (-D))1/2=i*(-D) ½ (poznámka: D<0). Teda korene kvadratickej rovnice budú x1=(-b+iD1/2)/4ac, x2=(-b-iD1/2)/4ac

Maximum z 3 hodnôt

Zadanie: V predajni skrípt majú 3 skriptá, o ktoré máme záujem. Cena skrípt je a, b, c Sk. Navrhnite algoritmus, ktorý nájde najdrahšie skriptá; teda skriptá s maximálnou cenou.

Analýza problému: V prípade, ak máme zistiť maximálnu (alebo minimálnu) hodnotu z troch čísel, musíme každé číslo porovnať s každým iným číslom. Teda, spolu budeme robiť 3 porovnania (a<->b, a<->c, b<->c). Nemá zmysel porovnávať ab a ba, lebo toto sú totožné porovnania. Ak teda máme zistiť najväčšie číslo z a, b, c, môžeme postupovať napríklad nasledovne: Najskôr porovnáme : a>b. Ak toto platí, potom porovnáme a>c. V prípade ak aj toto platí, tak maximum je a. Keby platilo že: a>b a c>a, potom vieme, že maximum je c. Takto by sme mohli pokračovať ďalej.

Opakované načítanie

Zadanie: Na faktúre je údaj o počte položiek a samotné položky (položka obsahuje o.i. aj cenu v Sk). Ak viete koľko je na faktúre položiek, navrhnite algoritmus, ktorý vypočíta celkovú sumu položiek faktúry. Prvý vstupný údaj bude číslo pocet, ktoré nám hovorí o počte nasledujúcich položiek. Následne sa načíta pocet položiek ( – celých čísel symbolizujúcim cenu položky). Navrhnite algoritmus, ktorý vypočíta výslednú sumu ceny všetkých položiek.

Analýza problému: V tomto prípade nikdy popredu nevieme, koľko budeme načítavať položiek. Tento údaj sa dozvieme až v momente, keď načítame prvý údaj. Úlohou bude teda navrhnúť algoritmus, ktorý by načítal požadovaný počet položiek (počet položiek môže byť od 0 až po ľubovoľne veľké konečné číslo).

Na riešenie tohto problému využijeme cyklus. Tento cyklus sa bude opakovať toľkokrát, koľko položiek máme načítať. Pri každom opakovaní cyklu načítame jednu položku (položku označme ako premennú a) a jej hodnotu pripočítame k výslednej sume. Ďalším algoritmickým problémom je zabezpečiť, aby sa tento cyklus vykonával presne pocet krát. Tu využijeme prvý vstupný údaj pocet. Pri každej iterácii (opakovaní) cyklu sa hodnota premennej pocet zníži o 1. Cyklus budeme opakovať dovtedy, pokiaľ bude premenná pocet rôzna od nuly. Na výpočet súčtu všetkých položiek využijeme premennú suma, ktorú na začiatku vynulujeme (priradíme jej hodnotu 0).