Vývojové diagramy - cykly s daným počtem opakování - 9. díl

V tomto díle zakočníme téma cyklů s daným počtem opakování, probereme vnořené cykly, ukážeme si několik příkladů, kde využijeme více jak jeden cyklus, a budeme zjišťovat všechna prvočísla v daném rozsahu.

V 6. díle jsme si ukázali, že podmínek je možné použít v programu více. Stejné je to samozřejmě i s cykly. Doposud jsme ve vývojovém diagramu použili pouze jeden, ale to jenom z toho důvodu, že jsme jich více nepotřebovali. Kolik cyklů ve vývojovém diagramu (programu) použijeme, záleží pouze na nás, resp. na problému, který řešíme. V dnešním díle si ukážeme několik příkladů, kde využijeme více jak jeden cyklus.

Než se vrhneme na příklady, tak se podíváme na kombinování cyklů. V principu jsou dvě možnosti: buď jsou cykly na sobě nezávislé, nebo je jeden součástí druhého. První možnost je vidět na obrázku vlevo. Cykly jsou na sobě nezávislé – až jeden skončí, tak začne druhý. Druhý je tedy spuštěn až po skončení prvního. Těla cyklů se vykonají nezávisle na sobě podle daného rozmezí – v případě výřezu vývojového diagramu jde o N a M opakování. V obou se mohou zpracovávat různá data (ale i stejná), protože cykly jsou na sobě nezávislé.

Druhou možností je vnořený cyklus. Jde o situaci, kdy jeden cyklus je v těle jiného. Tělo vnořeného cyklu se provede N × M-krát, jak je vidět na obrázku. Při vstupu do prvního cyklu je I=1. Následně se vykonává jeho tělo, kde je další cyklus. Při vstupu do něj je J=1 – tento cyklus se provede M-krát, tj. J se změní postupně od 1 do M, ale I zůstává rovno 1. Po skončení vnořeného (vnitřního) cyklu se vracíme do vnějšího cyklu, kde se I mění na 2. Následně se vykoná jeho tělo, kde máme vnořený cyklus, který se znovu provede, tj. J se bude opět měnit od 1 do M (I je stále 2) atd. Nakonec se tělo vnořeného cyklu provede N × M-krát. Průchod si můžeme demonstrovat výpisem (odsazení značí průchod vnořeným cyklem):

(kód před cyklem)
I=1 
	J=1  {zde se vykoná tělo vnitřního cyklu}
	J=2  {a znovu}
	...
	J=M  {celkem M-krát}
I=2
	J=1  {opět se vykonává tělo vnitřního cyklu}
	J=2
	...
	J=M  {zase celkem M-krát, neboli zatím 2 x M krát}
I=3
	J=1
	J=2
	...
	J=M
...
	...
I=N 
	J=1
	J=2
	...
	J=M  {nakonec se tělo vnitřního cyklu provede N x M krát}
(pokračování po skončení cyklu)
 

U vnořeného cyklu jsou tedy zpracovávaná data společná. Počet vnoření není nijak omezen. Typický případ pro vnořený cyklus z obrázku je procházení tabulky (matice), kde I označuje řádek a J sloupec. V těle vnořeného cyklu se postupně můžeme dostat k jednotlivým buňkám tabulky.

Zakreslení cyklu tak, jak ho používáme, má i jednu výhodu – jednoduše se na něm pozná chyba, kdy se vnější a vnořený kříží. Vnořený a vnější cyklus se nesmí křížit, protože to znamená chybu v návrhu nebo v jeho zakreslení. Chybně zakreslený vnořený cyklus je vidět na obrázku.

Vykreslení plného čtverce

V prvním dnešním příkladu si ukážeme použití vnořeného cyklu při „vykreslení" plného čtverce. Zadání úlohy by bylo následující: vytvořte algoritmus, který na obrazovku vypisováním znaků „o" nakreslí čtverec o zadané délce strany. Vstupem od uživatele tedy bude zadaná délka strany čtverce. Výstupem algoritmu bude „vykreslený" čtverec.

Vykreslený čtverec bude vypadat podobně, jako bychom ho „nakreslili" například v Notepadu. Dejme tomu pro zadanou délku strany 5, tj. 5 řádek, kde by na každém řádku bylo 5 znaků „o" vedle sebe. A jak by vlastně vypadal algoritmus nakreslení takového čtverce 5 × 5 v Notepadu? Začali bychom na prvním řádku a napsali bychom postupně pět těchto znaků. Následně bychom odřádkovali a napsali dalších pět znaků. Pak ještě tři takové řádky a měli bychom nakresleno.

Když vypisujeme znaky do řádku, tak odpočítáme daný počet. V programu takový přístup vede na cyklus s daným počtem opakování. Stejně tak odpočítáváme řádky, tj. opět se jedná o cyklus s daným počtem opakování. Výsledný algoritmus budou tedy tvořit dva (vnořené) cykly. Vnitřní cyklus bude vypisovat znaky do řádku a vnější cyklus se bude starat o přechod na nový řádek (stejně jako jsme to dělali v Notepadu). Výsledný vývojový diagram je vidět na obrázku.

Vykreslení rovnostranného trojúhelníku

Druhý dnešní příklad bude velice podobný. Jeho zadání zní následovně: vytvořte algoritmus, který na obrazovku vypisováním znaků „o" a mezera nakreslí rovnostranný trojúhelník o zadané délce strany. Od uživatele dostaneme zadán jeden rozměr – délku strany trojúhelníku. Algoritmus jako svůj výstup bude mít vykreslený trojúhelník.

Opět si zkusíme takový trojúhelník nakreslit v Notepadu. Řešení úlohy si rozdělíme, nejprve si takto vykreslíme plný trojúhelník. První řádek bude velice podobný jako při kreslení čtverce – vypíšeme všechny znaky „o". Druhý řádek plného trojúhelníku bude mít o jeden znak „o" méně. Třetí řádek bude mít o 2 znaky méně, čtvrtý řádek o 3 znaky atd. Výsledný trojúhelník v textovém zápisu sice vypadá spíše jako rovnoramenný, ale to nám nevadí, důležitý je princip.

V druhém vnořeném cyklu je vidět závislost na prvním cyklu. Počet vnořených opakování klesá s narůstajícím počtem vnějšího cyklu. Dostáváme tedy další možnost omezení, která je také poměrně častá – počet opakování jednoho cyklu ovlivňuje počet opakování druhého cyklu. Výsledný rozsah opakování je tedy dán rozdílem maximálního počtu, který zadal uživatel (N), a aktuální hodnotou vnějšího cyklu. Jednička se do rozmezí přičítá, protože začínáme od 1, takže tím ji kompenzujeme. Výsledný rozsah je tedy od 1 do N-X+1.

Nyní je potřeba vyřešit vykreslení pouze hran trojúhelníku. Když si trojúhelník v Notepadu upravíme podle zadání, tak vidíme, že znaky jsou pouze v prvním řádku, prvním sloupci a na diagonále. V podmínce to musíme zohlednit. Znaky na prvním řádku znamená, že se budou vypisovat v případě, že X je rovno 1 (X=1). Podobně je to i se sloupcem, tj. Y je rovno 1 (Y=1). Poslední částí podmínky je diagonála. Můžeme vysledovat, že na diagonále je součet pozice řádku a sloupce vždy stejný, a to o jednu větší, než je maximum (N), neboli podmínka bude X+Y=N+1.

Všechny části podmínky zohledňují část vykresleného trojúhelníka. Stačí, aby byla splněná jedna z podmínek (1. řádek nebo 1. sloupec atd.). Spojovací operátor mezi jednotlivými částmi podmínek bude tedy || (nebo). A vůbec nevadí, že pro některé pozice (např. pro pozici [1, 1]) budou splněny dvě najednou. Výsledný vývojový diagram je vidět na obrázku.

Všechna prvočísla do zadaného čísla

Od kreslení se opět vrhneme na matematiku. Minule jsme si vytvořili algorimus pro zjištění, jestli dané číslo je prvočíslo. Tento příklad si nyní rozšíříme o zjištění všech prvočísel v daném rozsahu. Zadání takového příkladu by znělo: vytvořte algoritmus pro zjištění všech prvočísel od 2 do zadaného čísla. Vstupem od uživatele tedy bude horní mez rozsahu. Výstupem budou vypsaná prvočísla v daném rozmezí.

Funkce bude stejná, jako kdybychom program dle vývojového diagramu z minulého dílu spustili pro čísla 2, 3, 4, 5, …, N. V podstatě celý vývojový diagram z minula bude tělem nově přidaného cyklu. Hledáme provčísla v rozsahu 2 až zadané N, takže rozmezí vnějšího cyklu bude od 2 do N.

Tělo vnitřního cyklu musí obsahovat nulování počítadla dělitelů (P), aby se počítání provádělo pro každé testované číslo zvlášť. Kdyby byla inicializace P před vnějším cyklem, tak by po prvním zjištěném čísle, které má více dělitelů (tj. od čísla 4), již žádné další číslo nebylo označeno jako prvočíslo. Proto se musí hodnota P nulovat před každým novým průchodem vnitřním cyklem.

Rozsah vnitřního cyklu je stejný jako minule, jen je ovlivněn vnějším cyklem. Horní mez rozsahu je dána aktuální hodnotou vnitřního cyklu. Pro hodnotu 2 se vnitřní cyklus vůbec neprovede (jeho rozmezí je od 2 do 1), pro hodnotu 3 se provede jednou (od 2 do 2), pro hodnotu 4 je rozmezí od 2 do 3 (neboli se provede výpočet zbytku po dělení číslem 2 a číslem 3) atd.

Výsledný vývojový diagram je vidět na obrázku. Složitost vývojových diagramů nám utěšeně roste a jak je vidět na tomto příkladu (a částečně na předchozím), tak často lze úlohu rozdělit na menší části, které se dají řešit samostatně. Více o této problematice se dozvíme v některém z dalších dílů, ale nejprve nás čekají další dva typy cyklů: s podmínkou na začátku a s podmínkou na konci.