•••••••~
A I 9 O r i trn i z a c e
Zjištení, kolik císel je kladných, kolik záporných - prijde-Ii nula, pak cyklus skoncí Jedná se o podobný príklad, jako je predchozí. Tentokrát však pocet testovaných císel dopredu neznáme, proto použijeme cyklus rízený podmínkou na zacátku cyklu. Ukoncovacím znakem bude nula, která nepatrí ani do kladných, ani do záporných císel. Jádro cyklu bude stejné jako v predchozím algoritmu. Zacátek Musí být jistota, že pocítadla kladných a záporných císel jsou vynulována.
Nactení prvního císla probehne ješte pred cyklem. Je-Ii císlo ruzné od nuly, vstoupí se do cyklu, ve kterém je otestováno.
x
<>
O
+ X>O
+
KLAD := KLAD + 1
ZAP:= ZAP +1
Konec
Tip: Stejným zpusobem byste mohli napríklad zjištovat, kolikrát se mezi nactenými císly objevila jednicka (nebo jakékoli jiné císlo). Pak byste pocítadla KLAD ci ZAP prejmenovali treba na JEDNICKA a podmínka v jádre cyklu by netestovala, zda je císlo kladné, ci záporné, ale zda je rovno napríklad jednicce.
72
I
l
Tvorba algoritmu s použitím ey"klu ~ ... Soucin pomocí souctu Úkolem je sestavit algoritmus, který bude umet vynásobit dve celá císla mezi sebou. Nesmí však být použita operace násobení, protože umíte jen secítat. Princip rešení: •
Vzpomente si na doby, kdy vám na základní škole vysvetlovali operaci násobení a ríkali:
5 *2
je jako
5
+ 5,
tedy petku sectete dvakrát
8 *3
je jako
8
+ 8 + 8,
tedy osmicku sectete trikrát atd.
•
Protože už umíte zobecnovat, mužete odvodit, že:
A *B •
je jako
A +A + A +
+ A,
Úloha je jako stvorená pro cyklus
tedy A sectete S-krát. se známým poctem opakování.
Použité promenné: A, S ... dve císla, která mezi sebou máte vynásobit (budou zadána zvencí) C .. promenná, do které budete ukládat mezivýsledky souctu, nakonec v ní bude uložen výsledek (obdoba promenné SUMA, kterou jste používali v predchozích príkladech) 0
I ... rídicí promenná cyklu Zacátek
Promenná C musí být na zacátku prázdná.
Nactou se císla, která mají být mezi sebou vynásobena. Cyklus probehne S-krát.
C:= C+A
Pri každém pruchodu cyklem se k tomu, co je v C, pricte další A.
Konec cyklu
Po výstupu z cyklu je v C výsledek.
Konec
77
Algoritmizace Delení pomocí odecítání v dalším príkladu má být sestaven
algoritmus, který bude umet vydelit dve celá nezáporná císla mezi sebou. Nesmí však být použita operace delení, protože umíte jen secítat a odecítat.
Princip rešení bude vysvetlen na jednom (nepedagogickém)
príkladu ze života:
•
Predstavte si, že v restauraci sedí pet kamarádu, kterí si zašli na pivo. Dobre se bavili a objednávali jednu rundu za druhou, až najednou prišla" záverecná" a bylo nutno platit. Tácek byl plný cárek, ale když prišel vrchní, ani jeden si nepamatoval, kolik piv vlastne mel. Všichni si však pamatovali, že vypili stejný pocet piv, protože se objednávalo po rundách.
•
Vrchní znalecky obhlédl stul, spocítal pivare a pak si vzal do ruky tácek: •
škrtl prvních pet cárek na tácku a na cisté úctence si udelal jednu cárku;
• protože na tácku zbylo ješte víc než pet cárek, zase jich pet škrtl a na úctenku si udelal další cárku; • •
tento postup opakoval tak dlouho, dokud bylo na tácku víc než pet cárek (pokud pivari nelhali a pili všichni stejne, nakonec by mel zbýt úplne poškrtaný tácek).
Nakonec vrchní secetl cárky na úctence a zjistil, kolik každý z hostu u stolu vypil.
Použité promenné: A
delenec zadaný zvencí (pocet cárek na tácku)
B
delitel zadaný zvencí (pocet hostu u stolu)
C
promenná, do které se budou ukládat mezivýsledky odectu, nakonec v ní bude uložen podíl (úctenka)
Algoritmus rešte pomocí cyklu rízeného podmínkou na zacátku.
Zacátek
c:=o
Promenná C musí být na zacátku prázdná ("cistá úctenka").
Delitel musí být ruzný od nuly, jinak by promenná A v cyklu vubec neklesala, jednalo by se o nekonecný cyklus.
Rídicí podmínka cyklu: Bude se odebírat tak dlouho, dokud bude z ceho.
Zobraz: C, A
V promenné C je výsledek celocíselného delení, v promenné A bude zbytek. Konec
78
~
Tvorba algoritmu s použitím cyklu ...••.... Nejvetší spolecný delitel Najdete nejvetšího spolecného delitele dvou kladných celých císel. Princip rešení: 1.
Pokud jsou císla stejná, jsou zároven svým nejvetším spolecným delitelem.
2.
Je-Ii vetší A, pak od neho odectete B, címž dostanete nové A.
3.
Je-Ii vetší B, pak od neho odectete A, címž dostanete nové B.
4.
Postup opakujete tak dlouho, dokud si císla nebudou rovna.
Napríklad: Nejvetší spolecný delitel císel A = 27 a B = 12 Postup: 1. krok:
A :=A -B = 27 -12 = 15
2.krok:A:=A-B=15-12=
3
A bylo vetší, proto A je ted 15, B je porád 12 A bylo vetší, proto A je ted 3, B je porád 12
3. krok:
B := B - A = 12 - 3 = 6
B bylo vetší, proto B je ted 6, A je porád 3
4. krok:
B := B - A = 6 - 3 = 3
B je ted 3 a A je také 3
Ted už platí, že
A = B = 3, takže jste našli nejvetšího spolecného delitele. Zacátek
Rídicí podmínka cyklu "Nejsou si rovny", proto se pokracuje.
B je vetší, proto bude zmenšeno
A je vetší, proto bude zmenšeno
oA.
oB. +
B:= B - A
A:=A-
B
Konec
Poznámka: Nastane-Ii prípad, že budete odecítat tak dlouho, až dojdete k jednicce, zrejmé, že císla jsou nesoudelná (nemají jiného spolecného delitele než jednicku).
pak je
79
L
Algoritmizace Soucet císlic v císle Zacátek
Zjistete soucet císlic v zadaném celém císle Princip rešení: Použijete funkci celocíselného delení, pomocí které mužete zjistit poslední císlici císla - viz uvedený algoritmus vpravo .•••••••••••••••••••• Použité promenné: A ... zadané císlo
>
Zadané císlo
POM ... pomocná bunka, do které se ukládá podíl celocíselného delení
podelte celocíselne deseti, tím dostanete císlo 10x menší; poslední cifra z puvodního císla je ztracena.
POM := A div(10) CIS := A - 10*POM
Vynásobíte-Ii nove získané císlo nazpet deseti, nedostanete puvodní císlo - liší se od neho tím, že má na konci nulu. Odectete-Ii toto císlo od puvodního, dostanete poslední císlici puvodního císla.
Konec
Zacátek
Musí být jistota, že SUMA
SUMA:=
O
je prázdná. Muže být podeleno 10? Nejvyšší císlice Celocíselné delení 10 Zjištení poslední císlice v císle
POM:= A div (10) CIS := A - POM*1 O
SUMA := SUMA + A
Prictení poslední císlice k sume Novým A bude staré A s uríznutou poslední císlicí (je schováno v POM). Konec
80
Tvorba algoritmu s použitím cyklu ...••.... Test, kolikrát se vyskytuje urcitá císlice v daném císle Zvencí nactete nekolikamístné
císlo a císlici. Zjistete, kolikrát se v daném císle vyskytuje urcená císlice.
Princip rešení: •
Algoritmus bude pracovat na velice podobném principu jako predchozí algoritmus - pomocí celocíselného delení deseti budete postupne separovat císlici, která bude v tu chvíli poslední, a to tak dlouho, dokud z císla neco zbude (tedy dokud nebude nula).
•
Jakmile císlici od císla oddelíte, otestujete ji na shodu se zadanou císlicí.
•
Použijete opet cyklus rízený podmínkou.
Použité promenné: A ... vícemístné císlo zadané zvencí X
0.0
císlice (zadaná zvencí), která má být hledána v císle
POM
pomocná bunka, do které bude ukládán podíl celocíselného delení
POC
pocítadlo výskytu císlice v císle
-~----------------------------------
Zacátek
Vynuluje pocítadlo výskytu císlice v císle.
Bude celocíselne delit deseti tak dlouho, dokud bude co.
POM := A div (10) CIS:= A - POM*10
+
A:= POM
Konec
Poznámka: V tomto algoritmu jste upravílí rídicí podmínku trochu jinak než v predchozím - cyklus probehne jedenkrát navíc a poslední císlici ješte necháte otestovat v cyklu. Kdybyste použílí stejnou rídicí podmínku jako v predchozím algoritmu, museli byste ješte zbylou císlici po výstupu z cyklu otestovat a v prípade shody zvýšit pocítadlo o jednicku. 81
Tvorba algoritmu s použitím cyklu ...•••.... Zajíci a bažanti Myslivci porádali hon na zajíce a bažanty. Na konci chteli zjistit, kolik ceho ulovili. Byli však už tak unaveni, že nerozeznali zajíce od bažanta. Místního ucitele napadlo, že by mohli spocítat všechny kusy, které ulovili, a celkový pocet nohou. Z toho by se to prý melo spocítat. Princip rešení a použité promenné najdete na další stránce. Zacátek
Ošetrení nesmyslných hodnot - žádné zvíre nemuže mít víc než ctyri nohy.
Ošetrení nesmyslných hodnot - každé zvíre musí mít aspon dve nohy.
Zobraz: "Žádné zvíre nemá víc než ctyri nohy"
Pro zacátek predpokládejme, že budou samí bažanti. Bude spocítáno, kolik by to bylo kusu.
Bylo spocteno víc kusu, než je jich doopravdy. Musí se vymenit dva bažanti za jednoho zajíce.
TEST:=NOHY DIV(2) TEST:= TEST' 2
Pocet nohou musí být sudý. Zobraz: "Každé zvíre musí mít aspon dve nohy"
ZAJ :=0 BAZ :=NOHY/2 KUSY := ZAJ + BAZ Zobraz: "Zvírata bez jedné nohy neberu"
KUSY>
KS
+ Zobraz: ZAJ:= ZAJ +1 BAl:= BAZ-2 KUSY := ZAJ + BAl
ZAJ, BAZ
Konec
Dva bažanti byli vymeneni za zajíce a znovu budou testovány kusy.
85
I
Algoritmizace Princip rešení a použité promenné k príkladu Zajíci a bažanti (vývojový diagram je na str. 85). Rešení: Jedná se o klasickou úlohu, kterou lze rešit pomocí soustavy dvou rovnic o dvou neznámých. V tomto príkladu však bude použito jiné rešení. •
Nejprve se ošetrí nesmyslne zadané hodnoty:
•
•
Každé ulovené zvíre musí mít nejvýše ctyri nohy (zajíc ctyri, bažant jen dve). Je-Ii nohou více, pak asi myslivci špatne pocítali.
•
Každé ulovené zvíre musí mít nejméne dve nohy (bažant dve, zajíc dokonce ctyri). Je-Ii nohou méne, pak asi myslivci špatne pocítali.
•
Nohou musí být sudý pocet (viz algoritmus na zjištení sudého ci lichého císla). Pokud ne, tak se také bude jednat o chybné zadán í.
Vlastní rešení: •
Nejprve budete predpokládat, že myslivci ulovili samé bažanty a žádného zajíce - všechny nohy, které jsou, se priradí bažantum, tj. pocet nohou se vydelí dvema a vyjde pocet bažantu.
•
Porovnáte spocítaný pocet kusu (v tomto kroku je shodný s poctem bažantu, protože se predpokládá, že zajíci nebyli uloveni) s poctem skutecných kusu.
•
Pokud spocítaný pocet kusu je vetší než pocet kusu skutecných, vymení se dva bažanti za jednoho zajíce (pocet nohou zustane stejný, pocet kusu se o jeden sníží).
•
Testování kusu a výmeny dvou bažantu za jednoho zajíce se budou opakovat tak dlouho, dokud výsledkem nebude stejný pocet kusu, jako byl zadán.
Úlohu budete rešit pomocí cyklu rízeného podmínkou - v cyklu pokracujete, dokud bude spocítaný pocet kusu vetší než pocet skutecných kusu. Použité promenné: KS ... skutecný pocet kusu zvere (zadaný zvencí) NOHY
celkový pocet nohou (zadaný zvencí)
KUSY
spocítaný pocet kusu (v každém pruchodu cyklem se mení, na záver dosáhne hodnoty KS)
ZAJ
pocet zajícu (v každém pruchodu cyklem se mení, na záver bude roven jejich skutecnému poctu)
BAZ
pocet bažantu (v každém pruchodu cyklem se mení, na záver bude roven jejich skutecnému poctu)
Itl) -
a krátké. Vetšinu algoritmu zabírá ošetrení nežádoucích
stavu, které by vznikly, kdybyste Poznámka: Na výše uvedeném vývojovém diagramu opet vidíte, že vlastní rešeníje jednoduché do zpracování pustí/í nesmyslne zadané hodnoty.
CíSELNÉ SOUSTAVY A PREVODY MEZI NIMI Prevod z desítkové soustavy do dvojkové - nové cifry se vypisují od nejnižších. Zadání: Prevedte císlo z desítkové soustavy do dvojkové, nové cifry se budou postupne vypisovat od nejnižšího rádu. Princip rešení: •
Zadané císlo podelíte celocíselne dvema, výsledek si zapamatujete si zapíšete' - bude to nejnižší rád nového císla ve dvojkové soustave.
a zbytek po celocíselném
•
Výsledek celocíselného delení (císlo, které jste si zapamatovali) opet podelíte celocíselne dvema a zbytek po celocíselném delení si opet zapíšete - bude to další cifra (vyšší rád) nového císla ve dvojkové soustave.
•
Postup opakujete tak dlouho, až výsledek celocíselného ve dvojkové soustave.
delení bude 1. To bude nejvyšší rád nového císla
Na následující stránce je uveden príklad - prevod desítkového císla 26 do dvojkové soustavy.
86-----I
•
delení
Tvorba algoritmu s použitím cyklu ...••• ·.. Prevod desítkového císla 26 do dvojkové soustavy
Celocíselný podíl císla 13 13 6 o jedno výš
26
1O1 O
Nejnižší cifra nového císla
Zbytky po celocíselném delení císla vlevo,
Nejvyšší cifra nového císla
takže 26 = (11010)2
Úlohu budete rešit pomocí cyklu rízeného podmínkou na zacátku soustave budete vypisovat pri každém pruchodu cyklem.
cyklu, císlice nového císla ve dvojkové
Použité promenné: X
císlo v desítkové soustave zadané zvencí
Y
zbytek po celocíselném delení dvema, jedna cifra nového císla ve dvojkové soustave
POM ... pomocná bunka, do které se ukládá výsledek celocíselného delení dvema
Zacátek
I(
I Císlo v desítkové
soustave
I
Rídicí podmínka cyklu. Bude se delit tak dlouho, dokud bude co.
Podelí se celocíselne dvema a zjistí se zbytek po celocíselném delení.
POM:= X div(2) Y:= x- POM *2
Cifra ve dvojkové soustave
Výsledek celocíselného delení bude prohlášen za X, aby bylo možno postup opakovat.
Zobraz: X
Poslední (nejvyšší) cifra
Konec
Algoritmus mužete upravit také tak, že zmeníte rídicí podmínku cyklu na X > O. Potom cyklus probehne ješte jednou, podíl celocíselného delení bude nula a nejvyšší rád se zobrazí v promenné Y.
Tip:
~~
Poznámka: Výše uvedený algoritmus sice funguje, jenomže vypisování císlic v císle "odzadu dopredu" nepusobí príliš elegantne. Tento nedostatek odstranuje následující algoritmus.
............ ~ l I!lJ
[
:
r
Algoritmizace Prevod z desítkové soustavy do dvojkové - nové cifry se vypisují od nejvyšších Prevedte císlo z desítkové soustavy do dvojkové, nakonec císlo ve dvojkové soustave zobrazte. Princip rešení: •
Výpocet císlic nového císla ve dvojkové soustave probehne úplne stejne jako v predchozím prípade.
•
Protože však získáváte nižší rády dríve než vyšší, musíte si je nekam ukládat. K tomuto úcelu použijete strukturovanou promennou pole. Toto pole bude mít nekolik jednoduchých prvku, napr.: A[1] je první prvek pole, A[2] je druhý prvek pole, A[I] bude I-tý prvek pole, atd. Do každého prvku tohoto pole si mužete uložit nejaké císlo - v tomto prípade to bude císlice nového císla ve dvojkové soustave.
•
Na záver všechny prvky pole vypíšete, zacnete posledním a skoncíte prvním. Použijete k tomu cyklus s pevným poctem opakování, protože už víte, kolik prvku pole má (to si zjistíte, když budete pri výpoctu císlic pocítat pruchody cyklem).
Použité promenné: X
císlo v desítkové soustave zadané zvencí
V
zbytek po celocíselném delení dvema, jedna cifra nového císla ve dvojkové soustave
POM
H'
pomocná bunka, do které se ukládá výsledek celocíselného delení dvema
A[I]. .. I-tý prvek pole A, do kterého se budou ukládat spocítané císlice I ... pocítadlo císlic (pri každém pruchodu cyklem se získá jedna císlice a do pocítadla se pridá jednicka), v druhém cyklu bude pocítadlo použito jako rídicí promenná cyklu Poznámka:
I
Zacátek
Promennou
byste mohli vynechat a zbytky celocíselného delení nacítat zrovna
Y
do prvku pole A[I] - bylo by to úspornejší. Tato verze byla ponechána kvuli lepší srozumitelnosti a návaznosti myšlenkových pochodu na predchozí algoritmus. V první cásti algoritmu (pri výpoctu jednotlivých císlic) je použita modifikace predchozího algoritmu doporucená v Tipu.
Delit se bude tak dlouho, dokud bude co. Uložení poctu císlic do horní meze rídicí promenné cyklu
+ POM:= X div(2) Y:= x- POM *2
Zvednutí pocítadla císlic
r----
Presun císlice do prvku pole
Cyklus
I=N,1
Konec cyklu
Cyklus pujde pozpátku, od N do jednicky. I bude klesat, N zustává. Konec
88
r
Algoritmi
ace
RADY - ARITMETICKÉ, GEOMETRICKÉ, DALŠí Dalšími typickými úlohami, které se reší pomocí cyklu, jsou aritmetické a geometrické rady. Jsou to napríklad výpocty urcitého prvku aritmetické ci geometrické rady, poprípade soucty rad. Reší se pomocí tzv. rekurentních výpoctu, kde se na základe znalosti prvního prvku a pravidla pro výpocet prvku následujícího spocítá druhý prvek. V zobecnení platí, že z každého prvku je možné pomocí téhož pravidla získat prvek následující. Tyto úlohy - zejména s geometrickými radami - však skrývají jedno úskalí. Pokud rada není konvergentní, pak po urcitém poctu cyklu muže hodnota souctu rady nebo i prvku nabývat tak velkých hodnot, že presáhne povolený rozsah hodnot príslušného datového typu a dojde k tzv. "pretecení" (odborný výraz pro chybu programu zavinenou tím, že se do promenné, která je dimenzovaná na urcitý rozsah hodnot, snažíte zapsat vetší hodnotu - analogie se sklenicí vody, do které se snažíte nalít víc vody, než kolik je schopna pojmout).
Aritmetická rada - výpocet hodnoty prvku rady, prvky se zobrazují prubežne Spocítejte hodnoty prvních N prvku aritmetické rady. Znáte hodnotu prvního prvku A a hodnotu rozdílu mezi dvema po sobe jdoucími prvky O. Každý prvek se hned po výpoctu zobrazí.
Zacátek
Princip rešení: •
První prvek mužete zobrazit hned po jeho zadání.
•
Dále použijete cyklus s pevným poctem opakování, v jehož tele napred k predchozímu prvku prictete O, címž získáte prvek následující, a pak nový prvek zobrazíte.
•
Protože budete prvky hned zobrazovat a netrváte na jejich uchovávání, mužete pro všechny použít jedinou promennou A, kterou po zobrazení v následujícím pruchodu cyklem prepíšete novou hodnotou.
První prvek se nemusí pocítat, prímo se zobrazí.
Použité promenné: A ... hodnota prvního prvku zadaná zvencí, slouží pro všechny ostatní prvky rady
pozdeji
O
rozdíl mezi libovolným prvkem a prvkem následujícím
N
pocet prvku, které se mají spocítat (horní mez rídicí promenné cyklu)
I ... rídicí promenná cyklu
potrebné, prepsat. je možné je
Další prvek je získán Staré A užD. nebude zprictením predchozího
r-------
Cyklus
I :=2,N
A:= A+ O
Dolní mez rídicí promenné I je 2, protože první prvek byl už zobrazen.
A V prímo každém zobrazuje. pruchodu cyklem se promenná
~ Konec cyklu
Konec
90----
I
•
__
Tvorba algoritmu s použitím cyklu ~ .... Aritmetická rada - výpocet hodnoty prvku rady, všechny prvky se zobrazí nakonec Spocítejte hodnoty prvních N prvku aritmetické rady. Znáte hodnotu prvního prvku A[1] a hodnotu rozdílu mezi dvema po sobe jdoucími prvky D (prírustek). Princip rešení: •
První prvek mužete zobrazit hned po jeho zadání.
•
Dále použijete cyklus s pevným poctem opakování, v jehož tele napred k predchozímu prvku prictete D, címž získáte prvek následující. Pak nový prvek zobrazíte.
•
Tentokrát však máte požadavek všechny prvky uchovat a zobrazit je až nakonec. Proto použijete pole - strukturovanou promennou, jehož jednotlivými prvky budou odpovídající prvky rady.
Použité promenné: A[1] ... hodnota prvního prvku zadaná zvencí (první prvek pole A) A[I]. .. hodnota obecného I-tého prvku (I-tý prvek pole A) D
rozdíl mezi libovolnými dvema po sobe následujícími prvky
N
pocet prvku, které mají být spocteny (horní mez rídicí promenné cyklu)
I
rídicí promenná cyklu Zacátek
Dolní mez rídicí promenné I je 2, protože první prvek je už znám a není nutné jej pocítat.
r------I I I I I I I
Pro výpocet dalšího prvku se použije nový prvek pole; predchozí tedy zustane uchován.
I I
I
I I I I I I I I I I I I I I
•
A[I] := A[I-1] + D
Další cyklus, ve kterém se prvky jeden po druhém zobrazí, tentokrát "od jednicky".
Konec cyklu2
Konec
91
I
Algoritmizace Aritmetická rada - soucet Vytvorte algoritmus pro zjištení souctu aritmetické rady, zadáte-Ii hodnotu prvního prvku rady A[1], hodnotu rozdílu dvou po sobe jdoucích prvku D a pocet prvku, které máte secíst. Princip rešení: •
Princip rešení bude velice podobný jako u predchozích dvou príkladu. Rozdíl bude pouze v tom, že nebudete muset vypisovat hodnoty, které vznikají pri jednotlivých pruchodech cyklem, nýbrž vás bude zajímat až konecná hodnota souctu.
•
Pro výpocet souctu lze použít obe varianty, jak pomocí jediné promenné, která se bude postupne (predminulý algoritmus - Aritmetická rada - výpocet hodnoty prvku rady, prvky se zobrazují str. 90), tak i pomocí pole, do kterého si budete jednotlivé prvky aritmetické rady ukládat algoritmus Aritmetická rada - výpocet hodnoty prvku rady, všechny prvky se zobrazí str. 91). Ve vývojovém diagramu Aritmetická rada - soucet je použita varianta s polem.
prepisovat prubežne, (predchozí nakonec,
Použité promenné: A[1] ... hodnota prvního prvku zadaná zvencí (první prvek pole A) A[I). .. hodnota obecného I-tého prvku (I-tý prvek pole A) D
rozdíl mezi dvema libovolnými po sobe jdoucími prvky
N
pocet prvku, jejichž soucet se má spocítat (horní mez rídicí promenné cyklu)
I
rídicí promenná cyklu
SUMA ... soucet aritmetické rady, v jednotlivých pruchodech cyklu se do promenné ukládají mezisoucty Zacátek
Promenná SUMA se tentokrát nebude nulovat, ale priradí se jí prímo hodnota prvního prvku rady. Dolní mez rídicí promenné I je 2, protože první prvek byl už vložen do promenné SUMA.
SUMA:=
r-------
Cyklus
A[1]
1:= 2,N
Pro výpocet da.lšího prvku bude použit nový prvek pole; predchozí tedy zustane uchován. K tomu, co už v promenné SUMA je, se pricte nove spocítaný prvek. r r r
L
_
Konec cyklu
Konec
92
Tvorba algoritmu s použitím cyklu .•••.... Geometrická rada - výpocet hodnoty prvku rady, prvky se zobrazují prubežne Spocítejte hodnoty prvních N prvku geometrické rady. Znáte hodnotu prvního prvku A a hodnotu podílu mezi dvema po sobe jdoucími prvky Q. Hodnoty prvku se budou zobrazovat prubežne. Princip rešení: Protože se jedná o geometrickou radu, je dobré si predem zjistit velikost koeficientu Q, nebot:
•
1Q1< 1, rada je konvergentní;
•
je-Ii
•
je-Ii 1 Q1> 1, rada je divergentní.
•
V matematice se dopady konvergence ci divergence rady užívají hlavne až pri souctu geometrických Pri algoritmizaci si však musíte uvedomit, že bude-Ii napríklad:
A[1] = 1 a Q = 10, pakA[2]
rad.
= 10,A[3] = 100 ... a dáleA[S] = 100 000,
což je daleko za hranicí možností císel datového typu Integer (nejvyšší císlo je 32 767). Existují sice další datové typy, které umožnují uchovávat mnohem vetší císla, ale pri bezmyšlenkovitém použití velkého poctu kroku cyklu nebudou stacit ani ty a dojde k pretecení pameti! •
Po nezbytném ošetrení nežádoucích stavu, které by mohly nastat, je další algoritmus velice podobný algoritmu Aritmetická rada - výpocet prvku rady, prvky se zobrazují prubežne (str. 90), jen v tele cyklu získáte nový prvek vynásobením predchozího prvku koeficientem Q.
Použité promenné: Zacátek
A ... hodnota prvního prvku zadaná zvencí (pozdeji slouží pro ostatní prvky) Q
0'0
podíl dvou po sobe jdoucích prvku
Ošetrení, zda je rada konvergentní, ci divergentní
N .. pocet prvku, které se mají spocítat (horní mez rídicí promenné cyklu) o
1,,0
rídicí promenná cyklu
+ abs(Q)
>i
Dolní mez rídicí promenné I je 2, protože první prvek byl už zobrazen.
r-------
Cyklus
1:= 2,N Zobraz:
Další prvek bude získán z predchozího vynásobením Q. Staré A už nebude zapotrebí, proto muže být prepsáno.
"Pozor, rada je divergentní. Prvky mohou po nekolika krocích nabývat vysokých hodnot a muže dojít k pretecení pameti." A:= A* Q
V každém pruchodu cyklem se promenná A prímo zobrazuje.
Konec cyklu
Konec
93
1
••
Algoritmizace Geometrická rada - výpocet hodnoty prvku rady, všechny prvky se zobrazí nakonec Spocítejte hodnoty prvních N prvku geometrické rady. Znáte hodnotu prvního prvku A[1] a hodnotu podílu mezi dvema po sobe jdoucími prvky Q. Hodnoty všech prvku zobrazte až nakonec. Princip rešení: •
Napred ošetríte (stejným zpusobem jako v predchozím algoritmu Geometrická prvku rady, prvky se zobrazují prubežne, str. 93 )možnost pretecení pameti.
rada - výpocet
hodnoty
•
Další algoritmus bude velmi podobný algoritmu Aritmetická rada - výpocet hodnoty prvku rady, všechny prvky se zobrazí nakonec (str. 91), jenom v tele cyklu získáte nový prvek vynásobením predchozího prvku koeficientem Q.
Použité promenné: A[1] A[I]
hodnota prvního prvku zadaná zvencí (první prvek pole A) hodnota obecného I-tého prvku (I-tý prvek pole A)
Q
podíl dvou po sobe následujících prvku
N
pocet prvku, jejichž hodnoty mají být spocteny (horní mez rídicí promenné cyklu)
10.0
Zacátek
rídicí promenná cyklu Ošetrení, zda je rada konvergentní, ci divergentní
+ abs(Q) > O
Dolní mez rídicí promenné I je 2, protože první prvek je už znám a nemusí být pocítán.
Zobraz:
Pro výpocet dalšího prvku bude použit nový prvek pole; predchozí prvek tedy zustane uchován.
I
~
A[I] := A[I-1] * Q
Konec cyklu1
Další cyklus, ve kterém budou prvky jeden po druhém zobrazeny, tentokrát "od jednicky".
r--I II I I
I I I
I I I I I I I I I I I I L
_
Konec cyklu2
Konec
94 --------------------.---------------
"Pozor, jedná se o divergentní radu. Prvky po nekolika krocích mohou nabývat vysokých hodnot a muže dojít k pretecní pameti."
Tvorba algoritmu s použitím cyklu Geometrická
1lllII •••••.
rada - Suma
Spocítejte soucet prvních N prvku geometrické rady. Znáte hodnotu prvního prvku A[1] a hodnotu podílu mezi dvema po sobe jdoucími prvky Q. Soucet zobrazte. Princip rešení: •
Nejprve ošetríte stejným zpusobem jako v predchozím algoritmu (Geometrická rada - výpocet prvku rady, všechny prvky se zobrazí nakonec, str. 94) možnost pretecení pameti.
•
Další algoritmus bude velmi podobný algoritmu Aritmetická rada - soucet získáte nový prvek vynásobením predchozího prvku koeficientem Q.
hodnoty
(str. 92), jenom v tele cyklu
Použité promenné: A[1] A[I]
hodnota prvního prvku zadaná zvencí (první prvek pole A) hodnota obecného I-tého prvku (I-tý prvek pole A)
Q ... podíl dvou po sobe následujících prvku SUMA ... soucet geometrické rady, v jednotlivých pruchodech cyklu se do promenné ukládají mezisoucty N I
pocet prvku, které mají být spocteny (horní mez rídicí promenné cyklu) rídicí promenná cyklu Zacátek
Ošetrení divergentní rady
Promenná SUMA se tentokrát nebude nulovat, ale priradí se jí prímo hodnota prvního prvku rady. Dolní mez rídicí promenné I je 2, protože první prvek už byl vložen do promenné SUMA.
SUMA:=
A[1]
r------1
I I
Pro výpocet dalšího prvku bude použit nový prvek pole; predchozí prvek tedy zustane uchován.
I I I
I I
---, 1
1
1
I I
K tomu, co už v promenné SUMA je, bude pricten nove spocítaný prvek.
.
Zobraz: "Rada je divergentní, muže dojít k pretecení pameti."
I I I I
I 1 1 1
L
_
Konec cyklu
---------95 Konec
I
t
••••••• ~
A I9O r
it m iz a c e
Složité úrokování Praktickým príkladem na použití rady je složité úrokování. Vytvorte algoritmus pro složité úrokování, pomocí kterého zjistíte výši usporené cástky, když zadáte rocní úrokovou míru, výši pravidelné mesícní úložky a pocet let, po která budete sporit. Princip rešení: Mohli byste sice také dosadit do vzorce, ze kterého s použitím zadaných údaju spocítáte budoucí hodnotu, vy však vytvoríte rekurentní algoritmus. •
Rocní úroková míra - pocet procent, o který by se zúrocila cástka penez, jež by ležela na úctu po celý rok.
•
Úložky však nebudou vkládány 1x rocne, ale mesícne (vždycky na zacátku mesíce), takže: lednová úložka bude ležet na úctu 12 mesícu; únorová úložka bude ležet na úctu 11 mesícu; prosincová úložka bude ležet na úctu 1 mesíc.
•
Proto pak následne: lednové úložce bude príslušet celý rocní úrok, tj. 12/12 rocního úroku; únorové úložce bude príslušet 11/12 rocního úroku; prosincové úložce bude príslušet jen 1/12 rocního úroku.
•
Behem roku se úrocí pouze vložené peníze, neúrocí se úroky z mesícních úroku. Nemužete proto pripocítat každý mesíc úrok k rocní usporené cástce a príští mesíc jej úrocit spolu s ostatními penezi.
•
Výše uvedenou cást algoritmu budete rešit cyklem s pevným poctem opakování (a to 12) - pri každém pruchodu prictete k rocní sume novou mesícní úložku a spocítáte 1/12 rocního úroku z této cástky.
•
Úroky se "pripisují" 1x rocne, takže: •
znáte cástku, která ležela na úctu déle než rok;
•
znáte cástku, kterou jste našetrili za práve uplynulý rok;
•
spocítáte rocní úrok ze všech penez, které ležely na úctu déle než rok;
•
znáte už úrok z mesícních úložek, protože jste jej prubežne pocítali.
Vše sectete a získáte celkovou sumu za uplynulé období vcetne pripsaných úroku, další rok tedy budete mít úroky i z techto úroku. •
Nesmíte zapomenout vynulovat promennou, do které nacítáte rocní vklady, abyste ji meli pripravenou na další rok. Ze stejného duvodu musíte vynulovat rocní úrok.
•
První cást algoritmu (cyklus zabývající se mesícními úložkami a jejich úrokem) a další cást algoritmu, která se zabývá aktualizací celkové cástky a pripsáním úroku, "obalíte" dalším (vnejším) cyklem s pevným poctem opakování (pocet let).
Protože se soucasné rocní úrokové míry pohybují zpravidla v nekolika málo procentech (nebude hypoteticky uvažováno v hyperinflacních rozmerech, kdy by neprimerene rostly i úrokové míry vkladu), nebudete si muset lámat hlavu s tím, že by nasporená cástka rostla nad všechny meze (a došlo k pretecení pameti). Použité promenné: ULOZ ... pravidelná mesícní úložka PA N
rocní úroková míra (procentní cástku prevedete na desetinné císlo, napr. 2% = 0,02) pocet roku, po které bude sporeno
SUMAR
promenná slouží k ukládání mezivýsledku rocní usporené cástky pri každém pruchodu vnitrním cyklem
SUMAC
celková suma - do této promenné se po uplynutí roku pricítají rocní usporené cástky a úroky za uplynulá období
UROKR '" rocní úrok - promenná slouží k výpoctu úroku z pravidelných mesícních úložek behem jednoho roku UROKC ... celkový úrok - promenná sloužící k výpoctu úroku z cástky, která leží na úctu déle než rok vývojový diagram algoritmu je na následující stránce.
96 -----------------------------------------
Tvorba algoritmu s použitím cyklu ..•••... vývojový diagram algoritmu: Složité úrokování
-------------------------------------
Zacátek
/
SUMAR:= O SUMAC :=0 UROKR:= O
r------------------~ I I I I I I I I I I Cyklus2 r--------------I J:= 1, 12 I I I I I I I I I I I I I I I I I III I SUMAR := SUMAR + ULOZ I I I UROKR:= UROKR + SUMAR * PAl12 I I I I I I I I I I
Všechny promenné, ke kterým se bude neco pricítat, musí být vynulovány.
Vnejší cyklus - pocet let I
Vnitrní cyklus - mesícní úložky behem roku
Pripoctení
další úložky
Pripoctení
úroku
II I
I
Konec cyklu2
UROKC := SUMAC * PA
SUMAC := SUMAC + SUMAR + UROKC + UROKR
I I I
Nová celková cástka, do které je pripocítána nasporená cástka za uplynulý rok a jsou pripsány všechny úroky
Vynulování rocní sumy a rocního úroku, pokracuje se dál
I I I
~-------------------
Úrok z cástky, která je na úctu déle než rok
Konec cyklu1
Konec
97
I
•
Algoritmizace Stavební sporení Vypracujte algoritmus pro výpocet cástky, kterou nasporíte za celý jeden cyklus stavebního sporení. Podmínky stavebního sporení a vysvetlení pojmu, které budete dále potrebovat: •
Klient (stradatel) vkládá pravidelne jednou mesícne dohodnutou cástku (porád stejnou).
•
Sporí takto pravidelne po celý cyklus, který trvá nekolik let od ledna do prosince (dríve to bylo 5 let, nyní je to 6 let, za cas to bude zase jiná doba, proto bude ponechána doba obecná - bude zadávána zvencí). Délka cyklu musí být dodržena.
•
Peníze, které klient ukládá, jsou úroceny obvyklým zpusobem (viz predchozí príklad Složité úrokování na str. 96-97). Bude predpokládáno, že úroková míra behem celého cyklu zustane stejná.
Až potud by se jednalo o obvyklou úlohu složitého úrokování, ovšem je dále ješte vylepšena: •
Nasporí-Ii klient behem roku urcitou maximální cástku (dríve to bylo 18 000 Kc, nyní to je 20 000 Kc, za cas to bude treba jinak, proto ji necháte obecnou a bude zadávána zvencí), potom mu prísluší za tento rok maximální prémie (dríve to bylo 4 500 Kc, nyní to je 3 000 Kc, ponecháte ji proto zase obecnou a bude opet zadávána zvencí): •
nasporí-Ii za rok méne než maximální cástku, pak se maximální prémie úmerne zkrátí;
•
nasporí-Ii více, maximální prémie se už nezvýší.
•
Do nasporené cástky se pocítají i všechny úroky a prémie, které byly v daném roce pripsány.
•
Nasporená cástka se vyhodnotí každý rok koncem prosince, prémie se však pripisuje až v kvetnu.
•
Jakmile se prémie pripíše ke vkladu, normálne se úrocí jako všechno ostatní.
(Poznámka: Úloha je mírne zjednodušena.) Použité promenné: ULOZ ... pravidelná mesícní úložka PR ... rocní procentní úroková sazba N ... pocet let, po která stradatel sporí MPR ... maximální prémie, která muže být stradateli pripsána, pokud nasporí za rok maximální cástku, z níž se odvozuje prémie: •
nasporí-Ii za rok cástku vyšší, pak už prémie dál neroste
•
nasporí-Ii za rok cástku nižší, pak se prémie zkrátí v pomeru nasporené cástky ku maximální cástce, ze které se odvozuje prémie
PREM ... prémie, která bude stradateli pripsána. Pocítá se jako pomerná cást z maximální prémie: •
nasporí-Ii za rok cástku vyšší nebo rovnou maximální rocní usporené cástce (MCR), pak dostane maximální prémii (MPR)
•
nasporí-Ii za rok cástku nižší, pak se prémie zkrátí v pomeru nasporené cástky ku maximální cástce, ze které se odvozuje prémie
MCR ... maximální rocní usporená cástka, ke které prísluší maximální prémie (pokud by stradatel nasporil víc, prémie se už dál nezvyšuje) Do rocní usporené cástky se zapocítávají i pripsané úroky a prémie za minulý rok. MPL ... pocet let, po která bude stradatel sporit SUMR ... suma úspor v prubehu jednoho roku (do této cástky se krome vkladu zapocítávají i úroky a prémie za minulý rok) SUMC ... celková suma za uplynulé období UROKC
rocní úrok z cástky, která leží na úctu déle než rok
UROKR
úrok z úložek, které pricházely na úcet behem posledního roku
Princip rešení: •
Nebýt prémie, která se pripisuje vždy jednou za rok v kvetnu, jednalo by se o obycejnou úlohu o složitém úrokování (viz predchozí príklad Složité úrokování na str. 96-97).
98 -----------------------------------
Tvorba algoritmu s použitím cyklu ...••..... •
Opet v tomto algoritmu pobeží soubežne a jeden s úložkou 1x rocne.
dva cykly složitého
úrokování
- jeden s úložkou 1x mesícne
•
Vezmete-Ii v úvahu jen interval jednoho roku, pak se v nem projeví pouze mesícní úložky - vetšinou pravidelné, pouze v 5. mesíci zvednuté o prémii. Tím mužete vytvorit cyklus s pevným poctem opakování (a to 12).
•
Cyklus, který je zmínen v predchozím bodu, bude soucástí dalšího cyklu - rovnež s pevný poctem opakování (pocet let). V tom se zjistí, kolik klient nasporil, vypocítá se prémie, na kterou bude mít príští rok v kvetnu nárok a pripocítají se úroky. Zacátek
SUMC:= SUMR:= PREM:=
r-------------
r---------
O
Všechny promenné, ke kterým se bude neco pricítat, musí být vynulovány.
O O
Cyklus1 J:= 1, MPL
+---i
Vnejší cyklus - pocet let I
Vnitrní cyklus - mesícní úložky behem roku
Cyklus2 1:= 1,12
+ SUMR := SUMR + PREM
SUMR := SUMR + ULOZ UROKR:= UROKR + SUMR'
Je-Ii kveten, pripocítá se prémie.
Pripocítá se další úložka. PN12
PripOCítá se úrok.
Výpocet prémie - usporí-Ii klient více, dostane nakonec stejne jen maximální prémii.
Konec cyklu2
+ Úrok z cástky, která je na úctu déle než rok
SUMR + UROKR > MCR
PREM := MPR • (SUMR + UROKR) / MCR
Pomerná cástka z maximální prémie Nová celková cástka, do které je pripocítána nasporená cástka za uplynulý rok a jsou pripsány všechny úroky.
UROKC := SUMC • PA SUMC = SUMC + SUMR + UROKC + UROKR
Vynuluje rocní sumu a rocní úrok.
SUMR :=0 UROKR:=
O
Konec
l
99
Algoritmizace Faktoriál Po predchozí pomerne složité úloze je toto jedna z jednodušších - rekurentní algoritmus
pro výpocet faktoriálu.
Vytvorte algoritmus pro výpocet faktoriálu z celého nezáporného císla. Princip rešení: •
Z matematiky víte, že:
N! = N*(N-1)*(N-2)* •
... *3*2*1 a také
0!=1, což je úloha jako stvorená pro rekurentní algoritmus.
Úlohu budete rešit pomocí cyklu s pevným poctem opakování. V níže uvedeném algoritmu bude rídicí promenná cyklu rust od hodnoty 2 po N, takže budete pocítat 1*2* .... *N.
Použité promenné: N ... císlo, jehož faktoriál se má pocítat FAKT ... faktoriál císla N, tedy NI Zacátek
První hodnota je prirazena faktoriálu ješte pred cyklem. + N =0
r----
I I I I
To, co už je, bude vynásobeno dalším císlem v poradí.
I I I I I
I
:---.. I I I I I
I I I I I
L
_
Konec cyklu
Konec
Upozornení: Budete-Ií podle algoritmu vytváret program, nezadávejte pri jeho ladení velká císla a zvolte si primerený datový typ. Již 81 = 40320, což je víc, než se vejde do promenné typu Integer - muže snadno dojít k pretecení pameti! 100 -----------------------------------
Tvorba algoritmu s použitím cyklu
•••
Algoritmus pro výpocet Ludolfova císla 1t Vytvorte algoritmus pro výpocet
n, a to pomocí rady.
Vzorec pro výpocet:
1 1 1 ... -1t =1--+--4 3 5 7 Princip rešení: •
Jedná se o konvergentní radu, která konverguje práve k 1tI4. Její prírustky budou s každým dalším clenem cím dál menší, ovšem cím více clenu rady použijete, tím bude výsledek presnejší.
•
Zvolíte si sami nejaké hodne malé císlo E (epsilon), které bude zadáno zvencí. Budete pricítat nové cleny rady tak dlouho, až bude dosud poslední clen rady menší než vámi zvolené E. Poté výpocet ukoncíte a výsledek prohlásíte za dostatecne presný. Pozor, není to skutecný rozdíl správné hodnoty od hodnoty, kterou jste spocítali!
•
Použijete cyklus
•
Na záver ješte výsledek vynásobíte ctyrmi, protože ve vzorci se pocítá 1tI4.
rízený podmínkou
na zacátku cyklu.
Použité promenné: EPS ... požadovaná "presnost" PICTVRT ... promenná, do které se prubežne ukládají mezivýsledky výpoctu 1tI4, nakonec zde bude skutecne tato hodnota I ... pomocná promenná pro výpocet jmenovatele nového clenu rady KROK ... promenná, pomocí které se nastaví znaménko nového clenu rady - bylo-Ii minule kladné, ted bude záporné a naopak. PI ... císlo
n, které
pocítáte
(
Zacátek
Nastavení pocátecních hodnot
1:= 1 PICTVRT:=1 KROK :=1
Rídicí podmínka cyklu - testování posledního prírustku rady
Každý nový clen má ve jmenovateli císlo o 2 vetší.
PI := 4 * PICTVRT
Když se minule pricítalo, ted se bude I--odecítat (a naopak).
1:= 1+2
KROK := - KROK PICTVRT:= PICTVRT + KROK
*1/1
Konec
101
I
-
Tvorba algoritmu s použitím cyklu ...••.., OPERACE S VEKTORY A MATICEMI Další typickou oblastí úloh, které jsou velice vhodné pro algoritmizaci s vektory a maticemi.
s využitím cyklu, jsou práve operace
Soucet vektoru Vypracujte algoritmus pro soucet dvou vektoru A, B. Jejich rozmery N, M a hodnoty všech položek A[I], B[I] budou zadávány zvencí. Výsledný vektor bude C. Zacátek
Nejprve se nacte rozmer prvního vektoru.
r-----
Cyklus1 1=1,N
Ponevadž není možné míchat strídavé nacítání P910žek z jednoho a z druhého vektoru, musí být nejprve nacteny všechny položky prvního vektoru. Bude použit cyklus s pevným poctem opakování.
Pak se nacte rozmer druhého vektoru. Protože je možné secítat pouze vektory, které mají stejný rozmer, otestuje se, zda je tato podmínka splnena.
Konec cyklu1
Podmínka je splnena. Pomocí dalšího cyklu s pevným poctem opakování se nacítají položky druhého vektoru. Každá položka se hned po nactení secte s odpovídající položkou prvního vektoru.
Cyklus2 1=1,M
C[I]:= A[I] +8[1]
Spocítané položky nového vektoru se hned zobrazují.
~
Konec cyklu2
Konec
•••• -----------------------------------
105
Algoritmizace Skalární soucin vektoru Vypracujte algoritmus pro skalární souCIn dvou vektoru A, B. Jejich rozmery N, M a hodnoty všech položek A[I], B[I] budou zadávány zvencí. Výsledný vektor bude C.
Zacátek
Nejprve se nacte rozmer prvního vektoru.
Ponevadž není možné míchat strídavé nacítání položek z jednoho a z druhého vektoru, musí být nejprve nacteny všechny položky prvního vektoru. Bude použit cyklus s pevným poctem opakování.
Cyklus1
r----I
1=1,N
I I I I I I I I
I I I II I I I
Pak se nacte rozmer druhého vektoru. Protože je možné násobit pouze vektory, které mají stejný rozmer, otestuje se, zda je tato podmínka splnena.
1
_
Podmínka je splnena. Pomocí dalšího cyklu s pevným poctem opakování se nacítají položky druhého vektoru. Každá položka se hned po nactení vynásobí s odpovídající položkou prvního vektoru.
Zobraz: "Vektory nejsou stejného rozmeru"
C[I]:= A[I] *B[I]
Konec cyklu2
Konec
106-----•I
Tvorba algoritmu s použitím cyklu ~ .. Matice - nactení prvku
IJ
m1
Nacítání prvku matice je základní úlohou, bez níž se neobejdete v žádném algoritmu, který souvisí práve s maticemi. a·· a1n a2n ajn ... ... ...ai2 amj a2j a1j ... am2 a12 amn a22 Základní údaje:
I
Je dána matice A o rozmerech m, n: aj1 a11
v rámci jednoho
rádku, mení se druhý,
tedy j-tý
index od
1 do n,
•
Postupujete-Ii zleva doprava index j udává císlo sloupce.
•
Postupujete-Ii odshora udává císlo rádku.
•
Chcete-Ii nacíst první rádek, mužete použít cyklus, ve kterém se bude menit druhý, j-tý index od
•
Každý další rádek mužete nacíst úplne stejne, takže pro ctení všech rádku mužete použít rovnež cyklus. Tentokrát bude rídicí promennou i - první index. Jeho meze budou od 1 po n.
•
Protože napred prectete jeden celý rádek a teprve pak pujdete na další, ctení každého rádku budete provádet ve vnitrním cyklu. Ten bude vnoren do vnejšího cyklu, který bude rídit prechod z jednoho rádku na druhý.
dolu v rámci jednoho sloupce, mení se první, tedy i-tý index od
1 do
m, index i
1 po n.
Zacátek
r-------
Cyklus1
Vnejší cyklus - zarídí prechod z jednoho rádku na druhý, aby se ve vnitrním cyklu mohly nacíst všechny prvky téhož rádku. Až se nactou, pak se zmení rádkový index I a vše se opakuje.
1=1,M
Vnitrní cyklus - zarídí nactení všech prvku téhož rádku. J je druhým indexem prvku, který udává císlo sloupce matice.
r---
I
I I I I I I I I I I I I I
I I I I
Konec cyklu2
I I I I
I I 1
--
Konec cyklu 1
Konec
~------------------------------------
109
Tvorba algoritmu s použitím cyklu ~ .. TRíDICí ALGORITMY Povestnou "trešnickou na dortu algoritmizace" jsou trídicí algoritmy. Jejich úkolem je vždy seradit podle velikosti radu císelných nebo alfanumerických údaju. Bez trídicích programu se neobejde žádná úloha hromadného zpracování dat, nebot vyhledávání informací v serazených datech je podstatne jednodušší a rychlejší než v datech neserazených (kde pripadá v úvahu pouze sekvencní prohledávání). Nactená data musí být vždy pred vlastním trídením uložena, a to bud v operacní pameti, nebo na disku, protože se ke každé položce budete nekolikrát vracet.
~~
a Upozornení: kterou vždy Nemužete v dalším kroku použítcyklu systém prepíšete jediné novým promenné, údajem! do které budete zvencí zadávat údaj
A) Z pohledu zadání vstupních dat existují dve varianty: •
setrídení predem známého poctu císel ci znaku - pocet je znám predtím, než se nacte první císlo ci znak;
•
setrídení neznámého poctu císel - nacítají se císla ci znaky a na jejich konci je "zarážka" (muže to být bud speciální znak, který se normálne v rade trídených znaku ci císel nemuže vyskytnout, nebo napríklad znacka konce souboru).
Tyto varianty mají vliv pouze na "prípravnou fázi" trídicího algoritmu - na zpusob nactení a uložení vstupních dat (zda se použije cyklus s pevným poctem opakování, ci cyklus rízený podmínkou). Na vlastní prubeh trídení však vliv nemají. B) Z pohledu vlastního zpusobu serazování dat existuje hodne ruzných metod, které se liší: •
složitostí algoritmu;
•
nároky na pamet (poctem pomocných promenných);
•
rychlostí (poctem porovnání).
V ucebnici bude objasneno nekolik nejznámejších
trídicích algoritmu.
Poznámka: Ve všech trídicích algoritmech se na zacátku vyskytuje nactení údaju, které je stejné pro všechny uvádené algoritmy. Tato cást jíž nebude rozvádena, nebot se už v této knize vyskytuje nekolikrát. Je oznacena znackou podprogramu Nacti vektor A[N] a rozumí se tím nactení n císel ci znaku do strukturované promenné pole A o n položkách.
Select Sort (trídení prímým výberem) Název metody Select Sort pochází z toho, že postupne vybíráte jeden prvek po druhém a srovnáváte jej s prvním prvkem nesetrídené posloupnosti. Je-Ii prvek, který je "na rade", menší než první, vymeníte je. První setkání s tímto algoritmem bylo už v kapitole Vetvení - podkapitola Porovnávání císel a jejich razení podle velikosti, príklad Serazení trí císel s použitím pomocné bunky, resp. Serazení ctyr císel s použitím pomocné bunky. Nyní je algoritmus zobecnen na obecný pocet císel ci znaku a je rešen pomocí cyklu. Poznámka: V této úloze bude použito trídení vzestupné, tj. od nejmenšího prvku k nejvetšímu. Pokud byste chteli trídit naopak, postup by byl analogickÝ, pouze byste namísto minima hledali maximum.
Princip rešení: •
Nactete všechny n položky do pole A - viz podprogram Nacti vektor A[N].
•
Položky setrídíte takto: •
Nejprve ze všech n položek najdete minimum a uložíte je do položky A[1]. K vyhledání minima použijete algoritmus z této kapitoly Minimum z rady císel, metoda prímého výberu - rešení pomocí vektoru (str. 107).
12
Algoritmiza
e
Pro jistotu si malicko osvežíme postup: • první prvek porovnáte s druhým - je-Ii druhý menší, prehodíte je; • pak první porovnáte s tretím, je-Ii tretí menší než první, prehodíte je; • obdobným zpusobem pokracujete dál; • nakonec porovnáte první s posledním, je-Ii poslední menší, prehodíte je.
•
•
V položce A[1] máte nyní minimum ze všech prvku, proto si jí nebudete nadále všímat a ze zbývajících n-1 položek (od druhé po n-tou) vyhledáte opet minimum a uložíte je do položky A[2].
•
Položky A[2] si nebudete nadále všímat a ze zbývajících n-2 položek (od tretí po n-tou) vyhledáte opet minimum a uložíte je do položky A[3].
•
Tento postup se opakuje tak dlouho, dokud bude co porovnávat.
vývojový diagram se bude skládat ze dvou vnorených cyklu: •
Vnitrní cyklus bude obsahovat zobecnený algoritmus Minimum z rady císel, metoda prímého výberu - rešení pomocí vektoru (str. 107). U rídicí promenné cyklu už není definována dolní mez "natvrdo", ale je zadána obecne.
•
Vnejší cyklus zarizuje nastavení dolní meze rídicí
Zacátek
promenné vnitrního cyklu. Je-Ii nalezeno minimum, vyradí se a dál se bude hledat minimum ze zbylých císel.
Nacti vektor A[N]
Nastavení dolní meze rídicí promenné vnitrního cyklu. Vždy, když se ve vnitrním cyklu najde minimum, zkrátí se nesetrídená posloupnost o Jednicku.
(±) Výhody metody Select Sort: •
•
e • •
•
Tato metoda je velmi jednoduchá, snadno zapamatovatelná a také naprogramovatelná. Je to první zpusob, který cloveka vetšinou intuitivne napadne, i když nemá hlubší znalosti o trídicích algoritmech. Nevýhody
r------------I I I I I I I I
Vnitrní cyklus obstará vyhledání minima z dosud nesetrídených prvku.
r---------
Postupne se srovnává každý prvek nesetrídené posloupnosti s prvním prvkem nesetrídené posloupnosti.
metody Select Sort: +
Dochází k velkému poctu porovnávání (každý s každým).
A[J]
Pocet porovnávání se nesníží ani v prípade, že je posloupnost hned na zacátku cástecne nebo i úplne setrídená.
POM :=A[I] A[I] :=A[J] A[J] :=POM
I II
S vysokým poctem porovnávání se úmerne zvyšuje cas potrebný k setrídení.
I I I I I
l..
I I I I I
L
_
_
Konec cyklu2
Konec cyklu1
Zobraz vektor A[N]
122
•j
-
Tvorba algoritmu s použitím cyklu'" .... Bubble Sort (trídení probubláváním) - zjednodušený Název metody Bubble Sort (probublávání) pochází z analogie s kapalinou, ve které jsou ruzne velké bublinky vzduchu. Nejdríve "vybublá" nahoru ta nejvetší, pak ty menší. Algoritmus pracuje na principu postupného porovnávání dvou sousedních prvku. Je-Ii prvek vetší než následující, prvky se prohodí. První setkání s tímto algoritmem bylo už v kapitole Vetvení - podkapitola Porovnávání a razení císel, maximum a minimum, príklad Serazení trí císel podle velikosti s respektováním výsledku predchozího kroku (str. 37). Nyní už umíte používat cykly, proto mužete rešit príklad obecne pro n prvku. Poznámka: V této úloze budete opet pracovat s trídením vzestupným, tj. od nejmenšího prvku k nejvetšímu. Pokud byste chteli trídit naopak, postup by byl analogickÝ, pouze byste namísto minima hledali maximum. ~ Princip rešení: •
Nactete všechny n položky do pole A - viz podprogram Nacti vektor A[N].
•
Položky setrídíte takto: •
nejprve ze všech n položek najdete maximum a uložíte je do položky A[N]. K vyhledání maxima použijete algoritmus z této kapitoly Maximum z rady císel, metoda probublávání - rešení pomocí vektoru (str. 108). Pro jistotu si opet osvežíme postup: • první prvek porovnáte s druhým - je-Ii první vetší, prehodíte je; • pak druhý porovnáte s tretím, je-Ii druhý vetší než tretí, prehodíte je; •
obdobným zpusobem pokracujete dál;
• nakonec porovnáte predposlední s posledním, je-Ii predposlední vetší, prehodíte je.
•
•
Položky A[N] si nebudete nadále všímat a ze zbývajících n-1 položek (od první po n-1) vyhledáte opet maximum a uložíte je do položky A[N-1].
•
Položky A[N-1] si nebudete nadále všímat a ze zbývajících n-2 položek (od první po n-2) vyhledáte opet maximum a uložíte je do položky A[N-2].
•
Tento postup se opakuje tak dlouho, dokud bude co porovnávat.
vývojový diagram se bude skládat ze dvou vnorených cyklu: •
Vnitrní cyklus bude obsahovat zobecnený algoritmus Maximum z rady císel, metoda probublávání, - rešení pomocí vektoru (str. 108). U rídicí promenné cyklu však už nebude definována horní mez "natvrdo", ale je zadána obecne.
•
Vnejší cyklus zarizuje nastavení horní meze rídicí promenné vnitrního cyklu. Je-Ii nalezeno maximum, zaradí se na konec a dál se bude hledat nové maximum ze zbylých císel. Poznámka: Výše uvedená metoda se v této podobe príliš nepoužívá, protože neskýtá žádnou zvláštní výhodu oproti predchozí. Její význam pro vás je zejména v pochopení algoritmu, který mužeme dále zefektivnit.
® Výhody
metody Bubble Sort - zjednodušené:
•
Tato metoda je rovnež velmi jednoduchá, snadno zapamatovatelná
e
Je základem pro klasickou metodu Bubble Sort a pro metodu Sh?ke Sort (trídení pretrásáním).
•
V této podobe opet dochází k velkému poctu porovnávání (každý s každým).
•
Pocet porovnávání setrídená.
•
S vysokým poctem porovnávání se úmerne zvyšuje cas potrebný k setrídení.
•
i naprogramovatelná.
Nevýhody metody Bubble Sort - zjednodušené:
se nesníží ani v prípade, že je posloupnost
hned na zacátku cástecne nebo i úplne
123
I
•
Algoritmizace vývojový diagram algoritmu: Bubble Sort (trídení probubláváním) - zjednodušený
Zacátek
Nacti vektor A[N]
Nastavení horní meze rídicí promenné vnitrního cyklu. Vždy, když se ve vnitrním cyklu našlo maximum, zkrátí se nesetrídená posloupnost o jednicku. Pozor! Rídicí promenná cyklu je klesající, pri každém pruchodu cyklem bude o jednicku menší.
r------------I I I
Vnitrní cyklus obstará vyhledání maxima z dosud nesetrídených prvku.
1
r--------I I
I
Postupne se srovnává každý prvek nesetrídené posloupnosti s prvkem o jedno vyšším, který také ješte patrí do nesetrídené posloupnosti.
POM :=A[J] A[J] := A[J+1] A[J+1] :=POM
1
I I
I Výmena prvku I
1
I I I 1 1 1 1
I
I I I I I I 1 1 1 1
L
_
Konec cyklu1
Zobraz vektor A[N]
Konec
Bubble Sort (trídení probubláváním) - klasický Základem je predchozí algoritmus, bude však vylepšen o test, který zjistí, zda už je rada prvku setrídena, ci ne. Pokud ano, nepokracuje se v procházení rady prvku a trídení se ukoncí dríve. Vylepšení umožní významne snížit pocet vzájemných porovnávání (a tím zkrátit dobu trídení) v prípade, že rada prvku je už na zacátku cástecne (nebo dokonce úplne) setrídena. Princip rešení: •
Jako základ použijete predchozí algoritmus, tedy Bubble Sort (trídení probubláváním) (uvedený na str. 123).
•
Použijete novou promennou ZM, která bude sloužit jako indikátor, zda došlo behem celého jednoho porovnávacího pruchodu rady císel aspon k jednomu prohození prvku:
124 -----------------------------------
- zjednodušený
Tvorba algoritmu s použitím cyklu ...••· •
pred vstupem do vnitrního cyklu nastavíte promennou ZM na hodnotu O;
•
do vnitrního cyklu, v míste, kde dochází k prohození hodnot prvku v prípade, že je prvek vetší než následující, pridáte indikátor zmeny - promennou ZM nastavíte na hodnotu 1;
•
až dokoncíte celý pruchod radou císel, po opuštení vnitrního cyklu, otestujete, zda jste museli na poradí neco menit (zda ZM = 1), nebo zda už byla rada setrídená (zda ZM = O).
•
Pokud jste museli neco na poradí menit, pak pokracujete v rámci vnejšího cyklu. Když ne, je setrídeno.
<±>
Výhody - klasické
metody Bubble oproti predchozí:
•
Máte-Ii
na
zacátku
nebo dokonce úplne posloupnost, algoritmus a muže skoncit dríve. •
e •
•
Sort
cástecne setrídenou to
metody
Bubble
Nacti vektor A[N]
zjistí
Velice rychle "vybublá" nahoru velký prvek. Je-Ii na zacátku rady (která je cástecne setrídená) velký prvek, dostane se na její konec behem jednoho pruchodu radou císel. Nevýhody - klasické:
Zacátek
Sort
Je-Ii naopak na konci cástecne setrídené rady císel malé císlo, velice pomalu se "potápí" na zacátek rady. Pri každém pruchodu radou prvku klesne jen o jedno místo, a proto je zapotrebí plný pocet pruchodu (každého s každým) a nic se neušetrí.
Cyklus1
r-------------I I I I I I I I I I
1:= N, 2
Vynuluje se indikátor zmeny poradí.
ZM:=O
I I I I I
I I I I
I I I I I I I
Cyklus2 J:= 1, 1-1
r--------I I I I I I I I I I I
Menilo se poradí, indikátor zmeny se nastaví na jednicku.
+
I I
Je-Ii posloupnost úplne nesetrídená, dochází k velkému poctu porovnávání (každý s každým).
I I I
POM :=A[J] A[J] :=A[J+1] A[J+1] :=POM ZM := 1
I I
I I I I I I I I
I
I I I I
I I I I I I I
L
Pokud se nic nemuselo menit, rada císel už byla setrídená.
_
Menilo se poradí prvku, proto je nutné radu projít znovu. Zobraz vektor A[N]
Konec
1~
I
•
AlgoritmizaCé
r';~~~."""~
_
Shake Sort (trídení pretrásáním) Tento trídicí algoritmus odstranuje nevýhodu s pomalým "potápením" malých prvku z konce rady na její zacátek. Poznámka: Název Shake (pretrásání) pochází z prirovnání k barmanovi, který pracuje se šejkrem. Má v nem nejaké tekutiny a bublinky. Zatrese šejkrem a bublinky probublávají zdola nahoru, pak šejkr obrátí a bublinky zase spechají na druhou stranu. Princip rešení: Algoritmus Shake Sort vychází z predchozího - Bubble Sort (trídení probubláváním) má však dve významná vylepšení: •
První vylepšení
vychází z podstaty
- klasický
(str. 124),
pretrásání:
•
jednou budete procházet radu zepredu dozadu (zleva doprava) a necháte "vybublat" nejvetší prvek zdola nahoru (zleva doprava);
•
podruhé budete procházet odzadu dopredu (zprava doleva) a necháte "potopit" nejmenší prvek seshora dolu (zprava doleva);
•
rada se tedy bude rovnat od zacátku a od konce, nejdéle zustane nesetrídená uprostred;
•
pri každém pruchodu radou budete hlídat dolní a horní mez nesetrídeného zbytku prvku uprostred rady (promenné O a H) - tyto meze se budou po každém pruchodu posunovat smerem doprostred rady.
•
algoritmus skoncí, až bude všechno setrídeno, tedy až se meze prekryjí (O > H).
•
Oruhé vylepšení spocívá v hlídání místa v rade, kde došlo k poslední zmene poradL Nebudete už používat promennou ZM (indikátor zmeny), ale promennou PZM (poslední zmena), do níž se bude ukládat poradí (index) prvku, který jste prehazovali se sousedním. Pokud za tímto prvkem už nedošlo ke zmene, je tam už posloupnost setrídená.
•
V dalším pruchodu radou opacným smerem mužete tedy zacít procházet radu až od místa poslední zmeny: •
horní mez (promenná H) pri smeru dolu bude rovna místu poslední zmeny zmenšenému o hodnotu 1 (tedy PZM -1);
•
dolní mez (promenná O) pri smeru nahoru bude rovna místu poslední zmeny zvetšenému o hodnotu 1 (tedy PZM +1).
Použité promenné: O
dolní mez nesetrídené cásti rady
H
horní mez nesetrídené cásti rady
PZM ... místo poslední zmeny v rade
J ... rídicí
promenná obou cyklu, ve kterých se prochází nesetrídená cást rady
A[J] ... J-tý prvek v rade A [J+1] .. prvek, který stojí v rade vuci J-tému prvku o jedno místo vpravo, tj. smerem ke konci rady. Procházíte-Ii prvky od zacátku rady k jejímu konci, pak je to vuci J-tému prvku prvek následující. Procházíte-Ii radu smerem od konce k jejímu zacátku, pak je to vuci J-tému prvku prvek predchozí. 0
vývojový diagram algoritmu Shake Sort je na následující stránce.
126-----
I
•
-J.
Tvorba algoritmu s použitím cyklu'" .... vývojový diagram algoritmu: Shake Sort (trídení pretrásáním) Pruchod radou seshora dolu. Pozor, rídicí promenná cyklu je klesající.
Zacátek
Dolní mez je na zacátku rady. Horní mez musí umožnit srovnání s prvkem o jedno vyšším. PZMnicemu neprekáží.
r--I I
Nacti vektor A[N]
Cyklus2 J:= H, D
POM :=A[J] A[J] :=A[J+1] A[J+1] :=POM PZM :=J
Pruchod radou zdola nahoru
Cyklus1 J:= D, H
I II I I
I I I I
+
Konec cyklu2 POM :=A[J] A[J] := A[J+ 1] A[J+1] := POM PZM :=J D:= PZM +1
Posune dolní mez, od které zacne prohledávat.
Konec cyklu1
Posune horní mez, od které zacne prohledávat.
H:= PZM-1
Zobraz vektor A[N]
Konec
_ 127
I
-
