•••••••~
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
<lllIII
•••
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] <A[I]
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
-
Download

Tvorba algoritmu s použitím cyklu