× Aktuálně z oboru

Programátoři po celém světě dnes slaví Den programátorů [ clanek/2018091300-programatori-po-celem-svete-dnes-slavi-den-programatoru/ ]
Celá zprávička [ clanek/2018091300-programatori-po-celem-svete-dnes-slavi-den-programatoru/ ]

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

[ http://programujte.com/profil/17127-libor-benes/ ]Google [ ?rel=author ]       [ http://programujte.com/profil/14523-martin-simecek/ ]Google [ ?rel=author ]       26. 8. 2011       32 009×

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.

6. díle [ http://programujte.com/index.php?akce=clanek&cl=2010060400-vyvojove-diagramy-6-dil ] 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 [ http://programujte.com/?akce=clanek&cl=2010061400-vyvojove-diagramy-8-dil ] 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.


Článek stažen z webu Programujte.com [ http://programujte.com/clanek/2010030102-vyvojove-diagramy-cykly-s-danym-poctem-opakovani-9-dil/ ].