Vývojové diagramy - 8. díl

V minulém díle jsme začali s cykly. V tom dnešním si ukážeme několik příkladů, kde využijeme jejich sílu.

V dnešním díle si projdeme několik příkladů, na nichž si vysvětlíme fungování cyklů a také si ukážeme, že rozmezí cyklu nemusí být dané napevno, ale může být ovlivněno vstupem uživatele, tj. že rozmezí nemusí být jen od 1 do 100. A vedle cyklů si předvedeme i operace, které se běžně používají v programování.

Průměr známek

Začneme příkladem na výpočet průměru zadaných známek. Zadání takového příkladu by mohlo být: vytvořte algoritmus pro výpočet průměru ze 30 zadaných známek. Průměr známek se vypočítá jako jejich součet lomeno jejich počet. Ve výsledném algoritmu tedy potřebujeme zadat 30 známek, které sečteme a následně vypočteme jejich průměr.

Úlohu bychom mohli řešit tak, že bychom nechali uživatele najednou zadat 30 známek, následně bychom je všechny sečetli a vypočítali průměr. To by bylo řešení bez cyklu, jehož nevýhodou je nesnadné rozšíření třeba na jiný (větší, ale i menší) počet známek, ale i případná kontrola zadaného vstupu atd. Posledně jsme si ukázali, že s cyklem je možné takové úlohy řešit efektivněji.

Uživatel má zadat 30 známek, které může vkládat postupně. Udělejme si cyklus od 1 do 30, kde dostaneme možnost nechat si nějaký kousek algoritmu – tělo cyklu – 30krát zopakovat. Co by v těle takového cyklu mělo být? Když se nám bude tělo cyklu 30× opakovat, tak stačí vyřešit úlohu, kde se zadává jedna známka, která se přičte do nějakého součtu.

Úloha se tedy redukuje na zadání jedné známky a součet – vše 30× zopakujeme. Zadání známky je normální vstup od uživatele. Samozřejmě bychom měli kontrolovat, jestli zadal platnou školní známku (1 až 5), ale to v tuto chvíli řešit nebudeme, protože si chceme pouze ukázat cyklus.

Zbývá nám tedy vyřešit součet. Výsledný součet bude v proměnné S, zadaná známka je v proměnné Z. Nesmíme zapomenout na to, že sčítání se také bude provádět postupně v cyklu, stejně jako zadávání, takže v proměnné S budeme mít průběžný součet, ke kterému musíme hodnotu známky přičítat.

Provedeme tedy součet, který si uložíme: X = S + A a následně vrátíme do proměnné S: S = X. Toto lze v programování zapsat zkráceně, a to: S = S + A. Matematicky by tento zápis nedával smysl (pouze pro nulové A). Nesmíme ovšem zapomenout, že rovnítko v příkazu znamená přiřazení, nikoliv porovnání (není to podmínka). Zápis by se dal slovně popsat: proveď součet proměnných S a A a výsledek ulož do proměnné S. Stejný zápis lze použít pro všechny operandy (viz násobení u příkladu Faktoriál) a nemusí se vždy jednat o operaci s dvěma proměnnými (viz příklad Prvočíslo).

Někdy se používá příměr se sklenicemi a vodou nebo mincemi v dlani. Máme dvě sklenice (X, Y), u kterých chceme provést „součet obsahu". To můžeme provést tak, že obsah obou sklenic přelijeme do třetí (Z): Z = X + Y. Nic nám ovšem nebrání v tom, abychom obsah jedné sklenice (X) přelili do druhé (Y), takže výsledný součet bude ve sklenici Y: Y = X + Y nebo Y = Y + X (zápisy jsou ekvivalentní).

Výsledný vývojový diagram můžete vidět na obrázku. Tělem cyklu je zadávání a„sčítání. Po skončení cyklu se provede výpočet průměru, který nakonec vypíšeme. A„samozřejmě nesmíme zapomenout inicializovat proměnnou pro součet S – provádíme sčítání, takže inicializace bude na 0.

Následující tabulka obsahuje jednotlivé kroky pro průchod vývojovým diagramem. Vzhledem k opakování v cyklu se zde některé kroky (2, 3, 4) cyklicky opakují. Pro všech 30 průchodů by tabulka byla velmi dlouhá, proto je její výpis zkrácen na několik průchodů. Podstatné je v ní uvedeno, tj. první průchody a hlavně poslední. Tabulka končí výpočtem průměru ze zadaných známek.

Součet číselné řady

Druhým dnešním příkladem bude součet (suma) číselné řady. Zadání je následující: vytvořte algoritmus pro součet číselné řady do zadaného čísla. Číselná řada začíná 1 a končí zadanou hodnotou. Například pro konečné číslo 8 se jedná o řadu 1, 2, 3, 4, 5, 6, 7, 8, jejímž součtem je 36 (= 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8).

Řešení pomocí cyklu s daným počtem opakování se přímo nabízí. Rozmezí cyklu bude od 1 do nějakého zadaného N, které načteme od uživatele. Index cyklu se tedy bude měnit od 1 do N, každým průchodem se zvedne o 1. V těle cyklu bude stačit posčítat postupně měnící se hodnoty indexu. Na tomto příkladu vidíme, že index je možné používat jako jakoukoliv jinou proměnnou.

Výsledný součet uložíme do proměnné S. Opět použijeme zápis S = S + I, který znamená, že součet hodnot S a i uložíme do proměnné S. Protože provádíme součet, tak počáteční hodnota (inicializace) bude stejně jako v předchozím příkladu 0. Počáteční hodnota nemusí být vždy nulová, o tom se přesvědčíme v dalším příkladu.

Následující tabulka obsahuje jednotlivé kroky pro průchod vývojovým diagramem. Vzhledem k opakování v cyklu se zde některé kroky (3, 4) cyklicky opakují. Pro všech 10 průchodů (uživatel do N v tabulce zadal 10) by tabulka byla velmi dlouhá, proto je její výpis zkrácen na několik průchodů. Podstatné je v ní uvedeno, tj. první průchody a hlavně poslední.

Faktoriál

Dalším dnešním příkladem bude výpočet faktoriálu. Zadání by mohlo znít: vytvořte algoritmus pro výpočet faktoriálu ze zadaného čísla. Faktoriál je definován jako: n! = 1 × 2 × 3 × 4 × ... × n. Na vstupu od uživatele tedy bude jedno číslo. Na výstupu bude výpis vypočteného faktoriálu.

V podstatě jde o stejný příklad jako v předchozím případě. Jediný rozdíl je v tom, že jednotlivé hodnoty číselné řady mezi sebou nesčítáme, ale násobíme. Místo sčítání tak v těle cyklu použijeme násobení a opět využijeme zkrácený zápis: F = F × I (vynásob F a I a výsledek ulož do proměnné F).

Druhý podstatný rozdíl je v inicializaci proměnné F. U součtu jsme nastavili výchozí nulu – před součtem musí být celková hodnota 0. U součinu by 0 v inicializaci měla za následek to, že výsledek by byl opět 0 pro jakékoliv číslo. Proto musíme zvolit hodnotu 1. Můžeme obecně volit jiné výchozí hodnoty, vždy záleží na konkrétním příkladu.

Následující tabulka obsahuje jednotlivé kroky pro průchod vývojovým diagramem. Vzhledem k opakování v cyklu se zde některé kroky (3, 4) cyklicky opakují. Pro všech 5 průchodů (uživatel do N v tabulce zadal 5) by tabulka byla dlouhá, proto je její výpis zkrácen na několik průchodů. Podstatné je v ní uvedeno, tj. první průchody a hlavně poslední.

Prvočíslo

Poslední dnešní příklad bude zjištění, jestli je zadané číslo prvočíslo. Zadání takového příkladu by mohlo být: sestavte algoritmus pro zjištění, jestli zadané číslo je prvočíslo. Prvočíslo je celé číslo, které je dělitelné pouze 1 a samo sebou. Vstupem algoritmu tedy bude zadané číslo a výstupem algoritmu bude vypsání, jestli zadané číslo je, nebo není prvočíslo.

Metod na zjišťování je více. My si vystačíme s tou nejjednodušší, a to takovou, že projdeme všechna čísla od 1 do zadaného N a vyzkoušíme, jestli některé z nich nedělí zadané N. Všechna čísla od 1 do N projdeme v cyklu. Abychom se po skončení cyklu mohli rozhodnout, jestli je dané číslo prvočíslo, nebo nikoliv, potřebujeme vědět, zda ho nějaké číslo dělí. Opět nebudeme vymýšlet nic složitého – počet čísel, která zadané číslo dělí, si spočítáme.

Abychom si ukázali, že cyklus nemusí být jen od 1 do N, tak si provedeme malou optimalizaci. Každé číslo je dělitelné 1 a samo sebou, takže je jasné, že v rozmezí od 1 do N bude zadané číslo N dělit číslo 1 a číslo N. Z tohoto důvodu je nemusíme vůbec zkoušet a rozmezí cyklu může být od 2 do N-1 (pro zvídavější: větší optimlizaci dosáhneme tím, že by cyklus byl od 2 do odmocniny z N, což není ani zdaleka poslední možnost). Pokud nebudeme do počtu dělitelů započítávat 1 a sebe sama, tak prvočíslo bude takové číslo, které bude mít v rozmezí 2 až N-1 celkem nula dělitelů.

Test dělitelnosti provádíme výpočtem, tzv. zbytku po dělení (operace modulo). Pro zápis operace zbytku po dělení se používá příkaz % nebo mod, např. výpočet zbytku po dělení 3: X = Y % 3 nebo X = Y mod 3. My budeme používat první zápis se znakem procent, který je používanější a úspornější v zápisu (například: 7 % 3 = 1).

Ve výsledném vývojovém diagramu nejprve inicializujeme celkový počet dělitelů (proměnnou P) na 0 a načteme testované číslo od uživatele. Dále v cyklu projedeme všechna čísla od 2 do čísla, které je o jedno menší než zadané uživatelem. Těmito čísly z cyklu (index) zkusíme vydělit zadané číslo – zjistíme, jaký je zbytek po dělení. Pokud je zbytek nulový, pak je zadané číslo od uživatele dělitelné indexem a jediné, co provedeme, je přičtení 1 do proměnné P, která obsahuje celkový počet dělitelů. Na konci cyklu vyhodnotíme proměnnou P. Pokud je nulová, tak nebylo nalezeno žádné číslo, které by zadané dělilo, a proto je výsledkem vypsaný text, že zadané číslo N je prvočíslo. V opačném případě, kdy hodnota P není nulová, existovalo alespoň jedno číslo, které zadané číslo dělilo, a proto se nemůže jednat o prvočíslo.

Následující tabulka obsahuje jednotlivé kroky pro průchod vývojovým diagramem. Vzhledem k opakování v cyklu se zde některé kroky (3, 4, 5) cyklicky opakují. Tabulka obsahuje všechny kroky pro zadané číslo 5. Výsledkem je zjištění, že číslo 5 je prvočíslo.

Příště si ukážeme složitější algoritmy s využitím cyklů.