\input webmac
\def\WEB{{\tt WEB}}


\N1.  Prvocisla: Kratky ukazkovy priklad na demonstraci baliku \WEB\ .
Nasledujici program slouzi pouze jako ukazka nekterych moznosti
a sluzeb, ktere poskytuje programovaci nastroj \WEB. Jak jiz vime,
\WEB\ je specialni nastroj pro tvorbu dobre dokumentovanych programu.
Toto programovani nazyvame literarni programovani.

Tento ukazkovy priklad mel za vzor Knuthuv priklad, ktery
pomoci baliku \WEB\ literarne naprogramoval program na vypsani prvnich
1000 prvocisel. Zatimco Knuth naprogramoval opravdu
kvalitni program, ktery prevzal od Edsgera Dijkstra
z jeho knihy {\sl Notes on Structured Programming}, ja zde predkladam
pouze jednoduche priklady na toto tema, ktere kazdy jiste sam a mozna,
ze i lepe naprogramuje. Programy budu rozepisovat a strukturovat
vice nez pri programovani funkcnich, ale ne ukazkovych programu.

Muj ukazkovy priklad budou vlastne priklady dva: jeden na urceni, zda
dane cislo je prvocislo a druhy vypise vsechna prvocisla mensi nez \|p.
Budeme jim rikat podprogramy.

\Y\P\X2:Ukazkovy program na urcovani prvocisel\X\par
\fi

\M2. Jeden z podprogramu ma vstup a druhy ne. A cely program potrebuje na
zacatku prace jednu vstupni hodnotu, podle ktere pozna, ktery z podprogramu
ma pouzit pro vypocty. Musime si proto nadeklarovat konstanty a promenne.

\Y\P$\4\X2:Ukazkovy program na urcovani prvocisel\X\S$\6
\4\&{program}\1\  \37\\{prvocisl};\6
\4\&{const} \37$\|p=30$;\6
\4\&{var} \37\X4:Promenne programu\X;\6
\&{begin} \37\X3:Vetveni programu na dva podprogramy\X;\6
\&{end}.\par
\U1.\fi

\N3.  Vyber jednoho z podprogramu.
Jedna z prvnich veci, ktera se musi udelat, je rozhodnout, kterou vetvi
programu se budeme dale ubirat.
Jak jiz jsem se zminil, sklada se priklad ze dvou podprogramu a zalezi
na uzivateli, jaky program chce zrovna pouzivat.

\Y\P$\4\X3:Vetveni programu na dva podprogramy\X\S$\6
\X5:Vstupni hodnota pro urceni vyberu podprogramu\X;\6
\X6:Vyber podprogramu podle vstupni hodnoty\X\par
\U2.\fi

\M4. Nadefinujeme si pomocnou promennou, ktera nam poslouzi pro nacteni vstupu
a dale podle ni pozname, ktery z podprogramu se ma dale pouzit.

Pomocna promenna \\{vyber} bude typu word.
\Y\P$\4\X4:Promenne programu\X\S$\6
\4\\{vyber}: \37\\{word};\par
\As8, 10, 14\ETs18.
\U2.\fi

\M5. Nebudeme nijak testovat vstupni hodnotu. Tzn. pri chybne vstupni hodnote
se beh programu zastavi. Budeme predpokladat ze uzivatel vi, co chce a,
nebude nijak zkouset dalsi vlastnosti programu.
\Y\P$\4\X5:Vstupni hodnota pro urceni vyberu podprogramu\X\S$\6
$\\{writeln}(\.{\'Program\ na\ demonstraci\ prvocisel\'})$;\5
$\\{writeln}(\.{\'Muzes\ si\ vybrat:\ zjisti\ zda\ zadane\ cislo\ je\
prvocislo...1\'})$;\5
$\\{writeln}(\.{\'\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ vypis\ prvocisel\ mensich\
nez\ \'},\39\|p,\39\.{\'.........2\'})$;\5
$\\{write}(\.{\'Tva\ volba:\ \'})$;\5
$\\{readln}(\\{vyber})$\par
\U3.\fi

\M6. Pomoci uzivatelem zadane vstupni hodnoty program pozna, kde bude dale
pokracovat ve vypoctu.

\Y\P$\4\X6:Vyber podprogramu podle vstupni hodnoty\X\S$\6
\&{case} $\\{vyber}$ \1\&{of}\6
\41: \37\X7:Zjisti zda zadane cislo je prvocislo\X2: \37\X13:Vypis prvocisel
mensich nez\X\2\6
\&{end}\par
\U3.\fi

\N7.  Urci zda zadane cislo je ci neni prvocislo.
Tento podprogram muzeme rozdelit na dve samostatne casti. V jedne zjistime
cislo, ktere budeme dale zkoumat, a v druhe budeme provadet vlastni vypocet.

\Y\P$\4\X7:Zjisti zda zadane cislo je prvocislo\X\S$\6
\&{begin} \37\X9:Vstupni hodnota zkoumaneho cisla\X;\6
\X11:Testovani zkoumaneho cisla\X;\6
\X12:Vypis vysledku testu\X;\6
\&{end};\par
\U6.\fi

\M8. V teto casti chceme nacist do pomocne promenne hodnotu testovaneho
cisla, s kterou budeme dale pracovat.

Po cislu budeme pozadovat, aby bylo cele a kladne. Zvolime ho typu integer.

\Y\P$\4\X4:Promenne programu\X\mathrel{+}\S$\6
\4\|n: \37\\{integer};\par
\fi

\M9. Vstupni hodnotu cisla nebudeme nijak testovat, predpokladame, ze je cele
a kladne.

\Y\P$\4\X9:Vstupni hodnota zkoumaneho cisla\X\S$\6
$\\{writeln}(\.{\'Program\ urci\ zda\ zadane\ cislo\ je\ prvocislo\'})$;\5
$\\{write}(\.{\'Zadej\ cele\ cislo\ vetsi\ nez\ 1:\ \'})$;\5
$\\{readln}(\|n)$\par
\U7.\fi

\M10. Pri urcovani zda dane cislo je/neni prvocislo pouzijeme tuto
myslenku: budeme postupovat od 2 k odmocnine z \|n a po otestovani cisla 2
testujeme pouze licha cisla.

Musime si dodefinovat dalsi pomocne promenne. Dve ciselne a jednu logickou.

\Y\P$\4\X4:Promenne programu\X\mathrel{+}\S$\6
\4$\\{delitel},\39\\{odmocnina}$: \37\\{integer};\6
\4\\{jeprvocislo}: \37\\{boolean};\par
\fi

\M11. Pro vypocet budeme pouzivat ciselne pomocne promenne \\{delitel} a
\\{odmocnina} a logickou hodnotu \\{jeprvocislo}. \\{delitel} bude nabyvat
lichych
hodnot az do \\{odmocnina}. Budeme jim delit zadane cislo \|n a pomoci zbytku
po celociselnem deleni pozname, jestli je \|n nasobkem \\{delitel} a nebo
neni. Pokud se \\{delitel} rovna \\{odmocnina} a zbytek po celociselnem deleni
je
roven 0, pak zadane cislo je prvocislo, tzn. \\{jeprvocislo} je \\{true}.

\Y\P$\4\X11:Testovani zkoumaneho cisla\X\S$\6
\&{if} $((\|n=2)\V(\|n=3))$ \1\&{then}\5
$\\{jeprvocislo}\K\\{true}$\6
\4\&{else} \&{if} $\\{odd}(\|n)$ \1\&{then}\6
\&{begin} \37$\\{odmocnina}\K\\{round}(\\{sqrt}(\|n))$;\5
$\\{delitel}\K3$;\6
\&{while} $(\|n\mathbin{\&{mod}}\\{delitel}\I0)\W(\\{delitel}<\\{odmocnina})$ %
\1\&{do}\5
$\\{delitel}\K\\{delitel}+2$;\2\6
$\\{jeprvocislo}\K\|n\mathbin{\&{mod}}\\{delitel}\I0$;\6
\&{end}\6
\4\&{else} $\\{jeprvocislo}\K\\{false}$\2\2\par
\U7.\fi

\M12. Nyni jiz staci jen vypsat vysledek.

\Y\P$\4\X12:Vypis vysledku testu\X\S$\6
\\{writeln};\6
\&{if} $\\{jeprvocislo}$ \1\&{then}\5
$\\{writeln}(\.{\'Zadane\ cislo\ n\ =\ \'},\39\|n,\39\.{\'\ je\ prvocislo.\'})$%
\6
\4\&{else} $\\{writeln}(\.{\'Zadane\ cislo\ n\ =\ \'},\39\|n,\39\.{\'\ neni\
prvocislo.\'})$\2\par
\U7.\fi

\N13.  Vypis prvocisel mensich nez \|p.
Tento podprogram na rozdil od prvniho netestuje zda zadane cislo je nebo
neni prvocislo, ale vypisuje prvocisla, ktera jsou mensi nez zadane \|p.

Take se nyni nemusime zabyvat zadnymi vstupnimi udaji od uzivatele. Pouze
mu predame vysledek.

K vypoctu pouzijeme algoritmus, ktery se take nazyva Erastotenovo sito
. Pouzivame zde dve pomocne ciselne mnoziny. Jedna na
zacatku obsahuje vsechna cisla od 2 do \|p, oznacme ji \\{sito} a  druha je
prazdna,
oznacme ji \\{prvocisla}. Da se rict, ze z mnoziny \\{sito} nam do mnoziny
\\{prvocisla} propadavaji pres sito pouze prvocisla. A budeme presivat
tak dlouho, dokud mnozinu \\{sito} nevyprazdnime, pak v mnozine \\{prvocisla}
budou jen sama prvocisla mensi nez \|p.

\Y\P$\4\X13:Vypis prvocisel mensich nez\X\S$\6
\&{begin} \37\X15:Inicializace pomocnych mnozin\X;\6
\1\&{repeat} \37\X16:Hledani dalsiho prvocisla\X;\6
\X17:Eliminace nasobku prvocisla ze sita\X;\6
\4\&{until}\5
$\\{sito}=[\,]$;\2\6
\X19:Vypis sita\X;\6
\&{end}\par
\U6.\fi

\M14. Musime si nadefinovat dve pomocne mnoziny kladnych celych cisel a pomocne
ciselne promenne pro praci s cisly v mnozinach.

\Y\P$\4\X4:Promenne programu\X\mathrel{+}\S$\6
\4$\\{sito},\39\\{prvocisla}$: \37\&{set} \1\&{of}\5
$2\to\|p$;\2\6
\4$\\{dalsiprvocislo},\39\\{nasobekprvocisla}$: \37\\{word};\par
\fi

\M15. Dale si musime inicializovat obe pomocne ciselne mnoziny a jednu pomocnou
ciselnou promennou.

\Y\P$\4\X15:Inicializace pomocnych mnozin\X\S$\6
$\\{prvocisla}\K[\,]$;\5
$\\{sito}\K[2\to\|p]$;\5
$\\{dalsiprvocislo}\K2$\par
\U13.\fi

\M16. Z pomocne mnoziny \\{sito} budeme vybirat prvocisla a budeme je zapisovat
do
mnoziny \\{prvocisla}.

\Y\P$\4\X16:Hledani dalsiho prvocisla\X\S$\6
\&{while} $\R(\\{dalsiprvocislo}\in\\{sito})$ \1\&{do}\5
$\\{dalsiprvocislo}\K\\{succ}(\\{dalsiprvocislo})$;\2\6
$\\{prvocisla}\K\\{prvocisla}+[\\{dalsiprvocislo}]$\par
\U13.\fi

\M17. Pak uz jen staci z mnoziny \\{sito} odebrat vsechny nasobky posledniho
prvocisla.

\Y\P$\4\X17:Eliminace nasobku prvocisla ze sita\X\S$\6
$\\{nasobekprvocisla}\K\\{dalsiprvocislo}$;\6
\&{while} $\\{nasobekprvocisla}\L\|p$ \1\&{do}\6
\&{begin} \37$\\{sito}\K\\{sito}-[\\{nasobekprvocisla}]$;\5
$\\{nasobekprvocisla}\K\\{nasobekprvocisla}+\\{dalsiprvocislo}$;\6
\&{end}\2\par
\U13.\fi

\M18. Tento postup opakujeme dokud neodebereme z mnoziny \\{sito} posledni
cislo
a pak uz mame v mnozine \\{prvocisla} vysledek, ktery muzeme vypsat.

K tomu pouzijeme novou pomocnou promennou \|i, ktera bude postupne nabyvat
hodnot od 2 do \|p a pomoci ktere vypiseme prvocisla z mnoziny \\{prvocisla}.

\Y\P$\4\X4:Promenne programu\X\mathrel{+}\S$\6
\4\|i: \37\\{integer}\par
\fi

\M19. Nyni budeme testovat jestli cislo \|i je v mnozine \\{prvocisla}. Jestli
ano,
pak je vypiseme, jestli ne testujeme \|i o jednicku vyssi. Jako prvni prvocislo
vypiseme cislo 1, ktere sem samozrejme take patri, ale kvuli vypoctu jsme ho
do pomocne mnoziny \\{sito} nezahrnuli, jiste kazdy vi proc.

\Y\P$\4\X19:Vypis sita\X\S$\6
$\\{writeln}(\.{\'1\'})$;\6
\&{for} $\|i\K2\mathrel{\&{to}}\|p$ \1\&{do}\6
\&{if} $\|i\in\\{prvocisla}$ \1\&{then}\5
$\\{writeln}(\|i)$\2\2\par
\U13.\fi

\N20.  Index.
Zde je rejstrik vsech pouzitych pojmu.
\fi


\inx
\:\\{boolean}, 10.
\:\\{dalsiprvocislo}, 14, 15, 16, 17.
\:\\{delitel}, 10, 11.
\:{Dijkstra, Edsger}, 1.
\:{Erastotenovo sito}, 13.
\:\\{false}, 11.
\:\\{integer}, 8, 10, 18.
\:\\{jeprvocislo}, 10, 11, 12.
\:{Knuth, Donald E}, 1.
\:\\{nasobekprvocisla}, 14, 17.
\:\\{odd}, 11.
\:\\{odmocnina}, 10, 11.
\:\\{prvocisl}, \[2].
\:\\{prvocisla}, 13, 14, 15, 16, 18, 19.
\:\\{readln}, 5, 9.
\:\\{round}, 11.
\:\\{sito}, 13, 14, 15, 16, 17, 18, 19.
\:\\{sqrt}, 11.
\:\\{succ}, 16.
\:\\{true}, 11.
\:\\{vyber}, 4, 5, 6.
\:\\{word}, 4, 14.
\:\\{write}, 5, 9.
\:\\{writeln}, 5, 9, 12, 19.
\fin
\:\X17:Eliminace nasobku prvocisla ze sita\X
\U13.
\:\X16:Hledani dalsiho prvocisla\X
\U13.
\:\X15:Inicializace pomocnych mnozin\X
\U13.
\:\X4, 8, 10, 14, 18:Promenne programu\X
\U2.
\:\X11:Testovani zkoumaneho cisla\X
\U7.
\:\X2:Ukazkovy program na urcovani prvocisel\X
\U1.
\:\X3:Vetveni programu na dva podprogramy\X
\U2.
\:\X5:Vstupni hodnota pro urceni vyberu podprogramu\X
\U3.
\:\X9:Vstupni hodnota zkoumaneho cisla\X
\U7.
\:\X6:Vyber podprogramu podle vstupni hodnoty\X
\U3.
\:\X13:Vypis prvocisel mensich nez\X
\U6.
\:\X19:Vypis sita\X
\U13.
\:\X12:Vypis vysledku testu\X
\U7.
\:\X7:Zjisti zda zadane cislo je prvocislo\X
\U6.
\con
