Úvod do programování

1. Úvod

1.1. Cíle kurzu

Cílem kurzu je poskytnout základní orientaci v problematice a připravit na další studium algoritmizace a programování, stejně jako studium v oblasti výuky algoritmizace a programování na středních a základních školách.

V kurzu Základy a algoritmizace a programování se seznámíte se základními principy řešení problémů na počítači.

Poznáte algoritmus jako formalizovaný postup řešení úlohy (zejména na počítači).

Budete uvedeni do historie algoritmizace, programování a počítačů vůbec.

Poznáte typické metodiky analýzy problému, návrhu příslušných algoritmů, datových struktur a jejich implementace.

Získáte přehled o modelovacích a programovacích nástrojích pro řešení jednotlivých tříd problémů a budou umět zvolit vhodný nástroj.

Zvládnete praktické algoritmické obraty a jejich programovou implementaci v jazyce Pascal.

1.2. Vstupní předpoklady kurzu

• nepředpokládají předchozí znalosti z této problematiky,
• očekává se však základní počítačová gramotnost (na úrovni úvodu práce s počítačem) a
• znalost středoškolské matematiky.

1.3. Obsah a forma učebního textu

1.4. Jak pracovat v kurzu "Úvod do programování"

1.4.1. Postup při práci v kurzu

1. Pročíst si "návod k použití" tohoto učebního textu, uvedený dále.
2. Podle instrukcí stáhnout a nainstalovat Turbo Pascal 5.5 a prozkoušet jeho funkčnost.
3. Sledovat pokyny vyučujícího, zejména která část textu se má právě nastudovat.
4. Průběžně přijímat, řešit a odevzdávat úlohy.
5. Sledovat diskuse k problematice na webu vyučujícího.
6. V případě potřeby ihned e-mailem (nebo jinak, i osobně) konzultovat - až po té, co se přesvědčíme, zda již podobný dotaz nebyl diskutován a zodpovězen na webu vyučujícího.

1.4.2. Způsob práce s textem

Celkový obsah učebního textu
Celá učebnice je rozdělena na tyto hlavní části (jsou číslovány a uvedeny velkým nadpisem)

1. Úvod - ten právě čtete, obsahuje obecné pokyny k práci;
2. Úvod do algoritmizace a programování - motivuje, uvádí do problematiky; zdůvodňuje, proč používáme právě takové nástroje, jejich historii, atd.;
3. Začínáme prakticky programovat - nejdříve popíše postup přípravné fáze - jak se nainstalují potřebné nástroje (prostředí Turbo Pascalu) a naváže prvními programátorskými pokusy v Pascalu; obsahuje mnoho ukázek funkčních programů;
4. Programy, co se umějí rozhodovat - zde se naučíme pracovat s větvením programu
5. Vícekrát se vyskytující části programu - co s tím? - zde se naučíme navrhovat celkovou strukturu programu tak, aby se v něm zbytečně neopakovaly stejné úseky kódu, kód byl logicky dobře a přehledně navržen;
6. Opakované provádění úseku výpočtu, cykly - zvládneme návrh programů, v nichž potřebujeme opakovaně provádět nějakou činnost: typicky při načítání vstupů, vyhledávání, atd.
7. Jak psát procedury a funkce - se znalostí sestavování jednoduchých cyklů se podíváme na tzv. podprogramy;
8. Jeden cyklus nestačí - složitější algoritmy (např. řazení posloupnosti) vyžadují vnoření dvou či více cyklů do sebe, zde se naučíme takové programy konstruovat;
9. "Výběrovky" - zde najdeme těžší úlohy;
10. Výuka programování na základní a střední škole - je nepovinnou částí; spíše jen stručným úvodem, proč, kdy a kde učit programování na ZŠ/SŠ;
11. Stručná referenční příručka vybraných prvků Turbo Pascalu - tato část je relativně samostatná, slouží pro rychlou a relativně přesnou orientaci v jednotlivých prvcích a konstrukcích Turbo Pascalu, mnohé detaily Pascalu jsou totiž v hlavní výkladové části materiálů z důvodu zřejmosti zjednodušeny;
12. Literatura, odkazy na Internet - netřeba komentáře...

Prvky učebního textu

Text je členěn na logické sekce, jimiž jsou moduly, mini-moduly, submoduly a kroky. Logické sekce jsou vždy uvedeny:

1. ikonou, přičemž moduly - ikonu nemají, mini-moduly s ikonou "dvouhroté vidličky", submoduly s ikonou "trojhroté vidličky" a kroky s ikonou "jdoucího panáčka";
2. víceúrovňovým číslováním (kromě kroků);
3. nadpisem tučným písmen (evt. vedlejším nadpisem uvedeným v závorce a menším písmem).

Kroky znamenají elementární "dávku" nové informace.

Dalším prvkem členění textu jsou již jen odstavce, které pouze opticky předělují souvislý text.

Každý prvek logické struktury textu může (má) mít definovány cíle. Ty jsou uvedeny tučným písmem, umístěny hned za nadpisem a uvozeny ikonou silné pruhované šipky.

Komentáře - jsou psány kurzívou s ikonou lupy:

Odkazy - slouží k rychlému přístupu na místa, kde nalezneme bližší popis, vysvětlení atd. Vypadají jako běžný internetový odkaz (link), ale jsou uvozeny ikonou ruky s ukazujícím prstem a mohou směřovat nejen do Internetu, ale též na jiné části tohoto textu.

• Toto je např. odkaz na začátek tohoto textu: #intro a
• toto je odkaz do Internetu - na osobní stránku autora tohoto textu: http://www.fi.muni.cz/~tomp.

Příklady uvedené v textu

• Jsou vždy číslované (jedno číslování v rámci celého textu),
• jsou podbarvené šedým pozadím,
• při levém okraji je počtem okrových "cihliček" znázorněna relativní obtížnost příkladu (1-5).
• Za slovním označením programu je v závorce odkaz přímo na jeho kompletní zdrojový text s příponou .PAS. Máme-li správně instalován Turbo Pascal (postup popíšeme dále) a dobře nastaveny asociace souborových přípon ve Windows (postup už bychom mohli znát předem:-)), stačí kliknout a soubor se otevře v prostředí Turbo Pascalu. Pokud bychom je hledali na CD-ROM přímo, jsou v podadresáři pas tohoto kurzu. Další eventální možností, jak získat zdrojový text příslušného příkladu, je vybrat jej označením pomocí myši přímo z okna prohlížeče a zkopírovat do schránky. To je také OK, ale jen do té doby, než text ze schránky vložíme do okna Turbo Pascalu: díky odlišnému kódování české diakritiky a jinému ukončování řádků nedostaneme zcela čitelný text... Doporučuji proto použít zdrojové texty přímo z CD-ROM.

1.	Toto je ukázkový příklad s obtížností 1 (Ahoj.pas)
	program Ahoj; {toto je hlavička programu} begin {toto je začátek těla programu}    writeln('Ahoj!'); {tento příkaz vypíše zprávu Ahoj!} end. {toto je konec programu}

Úlohy k procvičení (nehodnocené)

Úloha č. 1. Toto je ukázková úloha k procvičení.

1.5. Hodnocení kurzu

1.5.1. Motivace

1.5.2. Schéma hodnocení

1. průběžně řešené, odevzdávané a hodnocené úkoly: 25 úkolů po max. 10 bodech = celkem 250 bodů
2. závěrečná zkouška - návrh a realizace programu u počítače: max. 150 bodů

1.5.3. Způsob odevzdávání průběžně řešených úloh

1. Každých 14 dní budou zadávány čtyři úlohy: počínaje prvním soustředěním a dále pak elektronicky vždy v pondělí.
2. Vyřešené úlohy jsou přijímány opět elektronicky do 24.00 hod neděle před dalším "zadávacím" pondělkem. Na řešení je tedy téměř čistých 14 dní času.

2. Úvod do algoritmizace a programování

2.1. Řešení úlohy na počítači ··· Výběr vhodného prostředku

2.1.1. Ne vše musíme programovat

Řešení mnoha úloh prostě dnes většinou nevyžaduje znalost programování jako takového, většinou je potřebný spíše přehled o možnostech hotových uživatelských nástrojů a kompetence v jejich používání. Přesto analýza algoritmů zůstává základním prostředkem pro pochopení skutečné podstaty řešených problémů a je jedinou cestou, jak najít nejvhodnější postup řešení těchto problémů - optimální algoritmus k jejich řešení.

2.1.2. Používáme hotový nástroj

Jaké hotové nástroje existují?
Uživatelské programy jsou tradičně členěny do skupin podle charakteru úloh jimi řešených. Obvykle se rozlišují

• textové editory,
• tabulkové procesory,
• databázové systémy,
• grafické a prezentační systémy,
• komunikační nástroje,
• speciální nástroje.

Některé z nich jsou dokonce dostupné zdarma na Internetu (602pro PC, Star Office), některé jsou přibaleny jako "dárek" např. k základní desce počítače (Corel WordPerfect Suite) nebo je jejich cena zahrnuta v ceně nějakého "většího" systému, jako je Lotus Notes/Domino.

Speciální nástroje obvykle nabízejí řešení speciálnějšího okruhu úloh než jsou obecné kancelářské a administrativní úkony, počítáme sem např.

• programy ekonomických agend (účetnictví, fakturace, skladové hospodářství),
• programy pro statistické výpočty,
• programy pro počítačovou sazbu (DTP),
• počítačem podporované navrhování (CAD),
• počítačem podporovanou výrobu (CAM) a jiné.

Kdy tvoříme vlastní nástroje?
Jak vidět, nabídka je velmi široká. Je-li to možné, snažíme se maximálně využívat těchto hotových nástrojů. K tvorbě vlastního software přikročíme až tehdy, máme-li k řešení úlohu(y), kde:

1. hotové nástroje problém vůbec neřeší
2. použití hotových nástrojů by bylo zbytečně nákladné (úlohy mají dočasný charakter a nákup nástroje je nákladný),
3. hotový nástroj vyžaduje výkonnější počítač, než máme (to je kupodivu dosti časté:-)),
4. obsluha hotového nástroje je zbytečně složitá, přičemž z něj využijeme jen malou část funkcí,
5. hotový nástroj nelze dostatečně (nastavením, doprogramováním) přizpůsobit (provést tzv. zákaznické přizpůsobení neboli customization daného nástroje nebo systému),
6. si chceme vyzkoušet, jestli dokážeme vytvořit vlastní řešení.

2.1.3. A když musíme programovat...

2.2. Algoritmus ··· Algoritmické řešení úlohy

2.2.1. Co je algoritmus?

Přesně definovat nelze...
Algoritmus je pojem, jehož význam definujeme intuitivně, tedy "nepřímo", pomocí popisu jeho vlastností a chování. Nelze jej definovat přesně na základě nějakých jednodušších pojmů. V intuitivním slova smyslu je algoritmus postup, jak řešit libovolnou úlohu z určité třídy úloh.

Podstatné je tedy to, že algoritmus je stejný pro každou úlohu z dané třídy, algoritmus tedy vykazuje jistou obecnost (také se v této souvislosti říká hromadnost).

Historie
Pojem algoritmu se v žádném případě nezrodil až v počítačovém věku, jeho historie sahá minimálně ke starým Babylóňanům (cca 1800 let př.n.l.). Samotné označení algoritmus je o něco mladší, "jen" středověkého stáří - pochází totiž ze jména arabského matematika Muhammada ibn Músá al-Chvárízmího žijícího po roce 800 n.l. ve Střední Asii.

Staří Řekové formulovali řadu matematických algoritmů například z teorie čísel (např. Euklidův algoritmus na hledání největšího společného dělitele čísel nebo Eratostenovo síto na hledání prvočísel mezi prvními n přirozenými čísly). Tyto popisy algoritmů byly tehdy určeny pro "manuální" zpracování - podle nich postupoval člověk, který chtěl vyřešit jistou úlohu. Dnes není problém takové algoritmy "přepsat" do počítačem srozumitelné podoby - do formy programu a předložit je počítači ke zpracování. Koneckonců, některé z nich nás čekají i v tomto kurzu...

Podstatného uplatnění tedy dosahuje algoritmus jako formalizovaný popis řešení jisté třídy úloh až nyní, v době, kdy můžeme na realizaci (vykonání, provedení) algoritmu využít počítače, fungující automaticky a nahrazující pracnou, pomalou a zcela "netvůrčí" manuální práci při vykonávání algoritmu.

V současnosti jsme tudíž díky počítačům zbaveni nudného a jednotvárného vykonávání algoritmů, ale o to více jsme intelektuálně namáháni při analýze problémů a tvorbě algoritmů a programů tyto problémy řešící.

2.2.2. Úloha a její algoritmické řešení

Specifikace úlohy
Abychom vůbec mohli nějakou úlohu řešit, musíme přesně specifikovat, co chceme řešit. To zahrnuje specifikaci tzv.

• vstupních dat (údajů) představujících "zadání" konkrétní úlohy z dané třídy úloh a
• výstupních dat (údajů), která představují výstup řešení pro danou konkrétní úlohu.

Popis algoritmu
Specifikace úlohy říká pouze to, co chceme řešit a jaké požadujeme výsledky. Kdyby byl počítač natolik "geniální", že by sám podle takové specifikace dokázal najít algoritmus, nepotřebovali bychom nic dalšího - počítač by vše realizoval za nás. Tohoto "Svatému Grálu" algoritmizace nikdy zcela nedosáhneme, některé moderní prostředky analýzy a návrhu algoritmů se mu však již částečně blíží, obvykle však pouze pro velmi specifické typy úloh.

Obecně takovou automatizaci návrhu algoritmů obvykle nemůžeme použít. Musíme tedy sami najít a popsat přesný postup, jak se od přípustných vstupních dat dostat k požadovaným výstupním datům, a tento postup přepsat do takové podoby, aby jí počítač "rozuměl" a dokázal algoritmus vykonat. To je další podstatný úkol algoritmizace.

2.2.3. Algoritmus a jeho vlastnosti

1. Hromadnost - algoritmus je uplatnitelný na celou přípustnou třídu úloh, nikoli na jednu konkrétní "osamocenou" úlohu;
2. Determinovanost - v každém kroku algoritmu musí být jednoznačně určeno jeho další pokračování, tj. co se má přesně provést;
3. Rezultativnost (konečnost provádění) - algoritmus musí pro každý přípustný vstup skončit v konečném čase (po konečném počtu kroků);
4. Správnost (korektnost) - pro přípustná vstupní data algoritmus skončí v konečném čase a dá správný (očekávaný) výsledek.

Hromadnost
Hromadnost neboli též obecnost spočívá ve schopnosti být nasazen na celou třídu úloh, nikoli na jeden či několik málo zcela speciálních vstupů. V této souvislosti se traduje příhoda nejmenovaného kolegy, který na zahraničním přednáškovém pobytu zadal úkol napsat program, který spočte faktoriál libovolného přirozeného čísla. Jaké bylo jeho překvapení, když zjistil, že jeden ze studentů jako řešení předložil program, který počítal faktoriál čísla 6. Užaslému vyučujícímu sdělil, že přece program má počítat faktoriál libovolného čísla, takže on si za to libovolné číslo vybral šestku (sic!) Vysvětlit studentovi chybnost jeho úvahy bylo tehdy údajně nemožné...

Tedy formulaci "pro libovolné číslo" je třeba přinejmenším v kontextu algoritmizace rozumět ve smyslu "pro každé" (samozřejmě s jistými omezeními).

Determinovanost
Determinovanost spočívá v tom, že v každém výpočetním kroku je jednoznačně určeno, co se má dále provést. Ten, kdo algoritmus vykonává, rozhoduje o dalším postupu pouze na základě podmínek v algoritmu určených (a tím po dobu běhu neměnných) a podle momentálního výpočetního stavu. Nic dalšího - žádné "éterické síly" nesmí mít na průběh výpočtu vliv. Tj., při každém dalším vykonání stejného algoritmu nad stejnými vstupními daty musíme bezpodmíněčně dosáhnout stejného výsledku.

Rezultativnost
Rezultativnost znamená konečnost provádění algoritmu. Ať jsou vstupní data jakákoli (ale přípustná), musí vykonání algoritmu po konečném počtu kroků (a tím i v konečném čase) skončit. Jestli skončí se správným výsledkem, je jiná věc: tu řeší správnost algoritmu.

Správnost (korektnost)
Korektní algoritmus je takový rezultativní algoritmus, který nejenže vždy skončí, ale dá správný výsledek, tj. takový výsledek, který splňuje výstupní podmínku.

2.3. Jak algoritmus zapisovat?

Seznámíme se s prostředky slovního vyjádření algoritmu

a s prostředky přehledného grafického znázornění algoritmu

2.3.1. Slovní (textový) zápis algoritmu

Je to spíše historie...
V dobách, kdy algoritmizace nebyla chápána jako samostatná disciplína, ale jen jako určitý "přívažek" například k matematice nebo inženýrským vědám, bylo obvyklé, že se algoritmy zapisovaly slovně, formou textu v přirozeném jazyce. Buďto byla forma zcela volná a bylo víceméně na inteligenci a vnímavosti toho, kdo měl nelehký úkol algoritmus provést, jak přesně algoritmický postup dokáže realizovat, tj. jak moc se bude realizace lišit od autorových představ... V lepším případě se sice použito přirozeného jazyka, ale jen určitých vybraných obratů, o jejichž významu nemohl být nikdo na pochybách.

Většinou takový zápis vypadal tak, že každý řádek buďto znamenal určitý

• povel (načti, přičti, vypiš, zapiš, přiřaď...) nebo
• podmínku a evt. přechod na jiný řádek (něco jako "když platí, že a < 1, jdi na řádek 5, jinak jdi na řádek 3").

• opakování určitého řádku či řádků, dokud platí jistá podmínka (např. "dokud je m > 0, dělej řádky 7-9").

Příklad slovního popisu algoritmu
Zadání: pro nezáporná přirozená čísla a a b spočtěte jejich součin (a*b) pouze s použitím sčítání a odčítání (bez přímého použití operace násobení).

Řešení:

1. načti hodnoty a, b;
2. do proměnné vysledek dej hodnotu 0;
3. je-li b = 0, jdi na řádek 7
4. do vysledek přičti hodnotu a;
5. od b odečti jedničku;
6. jdi na řádek 3;
7. vypiš vysledek

Mírně vylepšený předchozí příklad
Jak jsme dříve zmínili, jedním z možných vylepšení jazyka pro zápis algoritmů bylo obohacení o konstrukci dovolující opakování určité části algoritmu. Výše zmíněné násobení a*b by s tím vypadalo takto:

Řešení s použitím obratu (konstrukce) "dokud":

1. načti hodnoty a, b;
2. do proměnné vysledek dej hodnotu 0;
3. dokud b > 0, dělej řádky 4 až 5;
4. do vysledek přičti hodnotu a;
5. od b odečti jedničku;
6. vypiš vysledek

Takový zápis je při složitějších algoritmech již značně nepřehledný, protože z takového zápisu vůbec není na první pohled zřejmá struktura takového algoritmu, tj. např. které části algoritmu se opakují, kde se vykonávání algoritmu větví podle platnosti určité podmínky atd. Algoritmus je zapsán jako posloupnost řádků ("výkonných" příkazů) a skoků mezi řádky.

Přesto to byl jistý úspěch; od takového poloformalizovaného zápisu již nebylo daleko jednak ke grafickému ("obrázkovému") znázornění algoritmu a také k jeho zápisu v programovacím jazyce.

2.3.2. Grafický zápis algoritmu

• načtení vstupních údajů (obdélníkový blok);
• nějaký výpočet nad údaji (např. aritmetické operace) (obdélníkový blok);
• větvení výpočtu podle určité podmínky (kosočtverečný blok);
• cyklické provádění určitého úseku algoritmu (kosočtverečný blok);
• výstup údajů (např. výpis na obrazovku nebo tisk) apod (obdélníkový blok);
• čára (evt. se šipkami) znamená přechod mezi jednotlivými algoritmickými prvky.

2.4. Co s algoritmem, aby ho počítač dokázal provést?

2.4.1. Zápis algoritmu do podoby kódu ··· Implementace algoritmu

Programovací jazyk je jistý přesně definovaný jazyk, vycházející často z některého z přirozených jazyků (obvykle angličtiny). Podstatné je, že v každém programovacím jazyce (nebo alespoň v těch lepších :-)), je naprosto přesně a jasně dáno, které obraty jsou vůbec přípustné a jaký význam mají. Významem se myslí to, jakou činnost počítač podle daného obratu při vykonávání algoritmu provede.

2.4.2. Programovací jazyky

"Klasika"

• Strojové jazyky jsou staré jako počítače samy. Zápis ve strojovém jazyce je tvořen instrukčními kódy (čísly) a přímo odpovídá podobě kódu, který počítač vykonává. První počítače ničemu jinému než svému strojovému jazyku "nerozuměly". Později se pro mírné ulehčení práce programátorů začal jako mezistupeň mezi strojovým jazykem a vyššími programovacími jazyky používat jazyk symbolických adres, někdy též nepřesně označován jako assembler.
• FORTRAN: Programovací jazyk FORTRAN (Formula Translation) se řadí mezi skutečné první programovací jazyky. Byl vyvinut v roce 1957. Používá se dodnes převážně pro numerické výpočty. Existuje pro něj řada vysoce optimalizovaných knihoven pro vědeckotechnické výpočty.
• COBOL: Jazyk COBOL (COmmon Businnes Oriented Language) byl vytvořen v roce 1960 pro aplikace v oblasti hromadného zpracování dat, kde se stále používá.
• BASIC: Beginner's All-Purpose Symbolic Instruction Code, rok 1964. Na osmibitových mikropočítačích (Spectrum, Sord, ATARI, Didaktik, Commodore) byl BASIC vestavěným programovacím jazykem a tím nahrazoval i operační systém. Hlavní oblastí použití Basicu jsou jednoduché programy s převažujícími numerickými výpočty.
• ALGOL 60: Na návrhu programovacího jazyka Algol 60 (Algorithmic Language) se podíleli především matematici. V souvislosti s tímto jazykem se objevila řada nových významných pojmů (např. bloková strukura programu, aj.). Dnes se jazyk téměř nepoužívá, ale významně ovlivnil další vývoj programovacích jazyků.
• PL/1: následník FORTRANU (rok 1975).
• PASCAL: pokračovatel Algolu, navržen profesorem Niklausem Wirthem (ETH Zürich) v roce 1971 pro potřeby výuky programování. Konečný tvar normy jazyka byl vydán v 80. létech pod označením ISO 7105.
• MODULA 2 (N. Wirth): vychází z Pascalu, který je rozšířen o prostředky tzv. "modulárního" programování.
• C: byl vyvinut původně jako obslužný prostředek pro používání operačního systému UNIX.

Programovací jazyky dneška
Z výše uvedených jazyků se dodneška používá FORTRAN, COBOL, BASIC, PASCAL a zejména C. Málokterý z těchto stále živých jazyků však zůstal ve stejné podobě jako před lety. Většina z nich dostala alespoň "nový kabát" v podobě pohodlného prostředí pro vývoj a testování programů, mnohé dostaly též různé nástavby měnící podobu samotného jazyka (C->C++, Pascal->Delphi) a podobně.

Na scénu nastoupily i jazyky zcela nové, které však zpravidla vycházejí z osvědčených vzorů (např. z jazyka C). Příkladem takového "nového" jazyka je Java (http://java.sun.com), vyvinutá společností Sun Corp.

Trendem současnosti jsou zejména jazyky, v nichž lze psát co nejdokonaleji přenositelný kód. Programujeme jen jednou a výsledný program jsme schopni spustit na různých počítačích s různým technickým vybavením (hardware) a různými operačními systémy.

Výuka algortmizace a programování je ovšem natolik specifickým úkolem, že programovací jazyky, které pro běžné "profesionální" programování vyhovují, jsou pro výuku obvykle značně, někdy až nepřekonatelně složité. Proto raději pro výuku volíme jazyk jednoduchý, přehledný, bez zákeřností, a z něhož později snadno přejdeme na požadovaný "profesionální" jazyk. Tím bude pro nás jazyk Pascal.

2.4.3. Jazyk Pascal

Proč zrovna Pascal
Pascal byl od počátku koncipován jako metodicky vhodný pro výuku algoritmizace a programování. To se ukázalo jako prozíravé a díky "rozumným" realizacím překladačů Pascalu od firmy Borland došlo k jeho masivnímu rozšíření na školách.

Pascal měl v tomto smyslu několik následníků, také připravovaných jako nástroje pro výuku programování (např. Modula, Eiffel, SmallTalk), žádný z nich však nedospěl ani zdaleka k takovému rozšíření. Pascal je dodnes díky své jednoduchosti, metodické čistotě, rychlosti dostupných překladačů a obecné známosti vzorem pro ostatní programovací jazyky.

Zrození a historie Pascalu

• 1971 - 1973 prof. Niklaus Wirth, ETH Zürich (Švýcarsko) definuje jazyk vhodný pro výuku algoritmizace a programování i pro profesionální použití
• 1980 je zveřejněna ISO norma jazyka Pascal
• 80. a 90. léta hlavní proud komerčního vývoje realizuje firma Borland Inc. (dnes Inprise) http://www.inprise.com, resp. http://www.inprise.cz - zrození tzv. Turbo Pascalu, Turbo (Borland) Pascal 7.0 (pro MS-DOS), objevuje se Turbo Pascal for Windows
• dnes profesionálně se používá Borland (Inprise) Delphi 5.0 (pro Windows 9x / NT) - následník Turbo Pascalu; "historický" Turbo Pascal 5.5 je vystaven na Internetu k bezplatnému stažení a použití...

Proč Pascal stále používáme?
Pascal má přes svou letitost stále co nabídnout:

1. snadno se učí;
2. oproti jiným jazykům nedovoluje udělat řadu těžko odhalitelných, zákeřných chyb;
3. dají (či dokonce musejí) se v něm psát "hezké" programy - povoluje jen obraty, které vedou k vytváření dobře strukturovaných a čitelných programů;
4. má relativně bohaté datové typy;
5. existuje na řadě platforem (DOS, Windows, UNIX/Linux...);
6. má perspektivu v podobě následníka: jazyka a prostředí Borland Delphi;
7. snadno se z něj přechází na jiné jazyky, naopak to jde rozhodně hůře...

3. Začínáme prakticky programovat

Nainstalujeme programovací prostředí Turbo Pascal 5.5

Seznámíme se se základními pojmy praktického programování a naučíme se sestavovat jednoduché programy pracující s čísly.

3.1. Instalace Turbo Pascalu 5.5

3.1.1. Stažení

• adresa Muzea: http://community.borland.com/museum/
• adresa Turbo Pascalu 5.5: http://community.borland.com/article/images/20803/tp55.zip

3.1.2. Instalace

1. Vytvoříme instalační adresář, řekněme c:\tp55. Zkopírujeme sem stažený soubor tp55.zip.
2. Soubor tp55.zip rozbalíme pomocí programu unzip (zdarma na internetu), WinZip (shareware na internetu, http://www.winzip.com) či ZipCentral (zdarma na internetu, http://members.nbci.com/zipcentral/). Rozbalovat musíme se zachováním adresářů (Disk1 a Disk2). Poté zkopírujeme obsah Disk2 do Disk1, aby bylo vše v jednom.
3. V adresáři c:\tp55\Disk1 spustíme program INSTALL.EXE
4. Dále se řídíme pokyny na obrazovce, v podstatě jde jen o výběr cílového adresáře pro instalaci. Vybereme např. opět c:\tp55. Instalace by měla proběhnout OK, po restartu stroje se projeví nastavení PATH, takže je možné z příkazové řádky spouštět Turbo Pascal 5.5 (dále jen TP) přímo příkazem TURBO. Pokud nechceme PATH měnit, nevadí. TURBO.EXE můžeme spouštět z jeho adresáře.
5. Funkčnost prostředí TP vyzkoušíme prostřednictvím příkladů přiložených jako demo, viz dále.

3.1.3. Úvod do použití TP

Spuštění TP
Program spouštíme tím nejjednodušším možným způsobem: spuštěním TURBO.EXE z instalačního adresáře.

Objeví se modrá obrazovka hlavní pracovní plochy TP. (Na obrázku vidíme Turbo Pascal 5.5. spuštěný v okně Windows 2000).

"Odklepneme" úvodní okno s textem "Turbo Pascal...". Nahoře vidíme lištu s nabídkou (menu):

• otevření (Load, zkráceně přímo přes F3),
• uložení (Save, zkráceně přímo přes F2),
• změna adresáře (Change dir)
• ukončení programu (Quit, zkráceně přímo přes Alt-X)

Ukázka práce v prostředí TP
Práci zahájíme vyzkoušením demonstračních příkladů dodávaných s TP, konkrétně zkusíme příklad CRTDEMO:

• Přes Load (tedy přes nabídku File a Load nebo přímo stiskem F3) otevřeme soubor CRTDEMO.PAS. Přípona .PAS označuje obecně tzv. zdrojové soubory v Pascalu.
• Přes nabídku Run/Run nebo přímo stiskem Ctrl-F9 program CRTDEMO spustíme. Program se bez dalšího upozorňování "v tichosti" sám přeloží (zkompiluje) a spustí.
• Dále se řídíme jeho pokyny, v podstatě můžeme vyzkoušet klávesy Ins, Del, Alt-W a Alt-R a sledovat činnost programu. Ten především ukazuje práci TP s obrazovkou.
• Ukázku ukončíme stiskem ESC.

3.1.4. Tvorba vlastních programů v prostředí TP

Celkový postup
Při tvorbě vlastních programů v prostředí TP budeme postupovat obdobně, samozřejmě s tím, že program musíme sami napsat:

1. Napíšeme tzv. zdrojový kód (zdrojový text) programu a uložíme jej.
2. Kód přeložíme do spustitelné podoby.
3. Program spustíme.
4. Klávesovou kombinací Alt-F5 můžeme kdykoli nahlédnout na výstup našeho programu (výstup totiž není normálně vidět - je překryt oknem integrovaného prostředí Turbo Pascalu). Opětovným stiskem Alt-F5 se vrátíme zpět do prostředí TP.

Psaní zdrojového textu (kódu) programu
K psaní zdrojového kódu bychom obecně mohli použít libovolný editor čistého textu, tedy např. Notepad, známou to součást Windows. Takto napsaný zdrojový kód bychom následně přeložili do spustitelné podoby tzv. řádkový překladačem (command-line compiler) a spustili jako běžný .EXE soubor. Takový postup je sice možný, ale přicházíme o řadu výhod, které nám přináší tzv. integrované vývojové prostředí (IDE, integrated development environment), které máme k dispozici dnes téměř pro všechny programovací jazyky. Konečně, v čem jiném než v integrovaném prostředí právě v Turbo Pascalu pracujeme?

Při psaní zdrojového kódu v integrovaném prostředí postupuje vlastně velmi podobně jako při pořizování textu v libovolném jiném textovém editoru. Samozřejmě, jelikož momentálně používáme IDE v dosovém prostředí, je ovládání trochu jiné, než v textovém editoru pod Windows, ale ne takové, aby se na něj nedalo rychle zvyknout.

Jaké jsou tedy hlavní činnosti při psaní zdrojového kódu?

• otevření souboru (File/Open nebo F3), případně vytvoření nového (New), s případným výběrem jiného adresáře - (File/Change dir)
• psaní textu
• průběžné ukládání (File/Save nebo F2)
• ukončení práce (File/Quit nebo Alt-X)

Vlastní psaní textu nám ulehčují kromě zcela běžných editačních funkcí jako jsou pohyb kurzoru po obrazovce, přechod na nový řídek s pomocí Enter, také speciální kombinace fungující v integrovaném prostředí Turbo Pascalu. Mezi důležité patří

• smazání celého řádku (Ctrl-Y),
• smazání do konce aktuálního řádku (Ctrl-T),
• rychlé přesuny na začátek a konec programu (Ctrl-PageUp a Ctrl-PageDown).

Je-li zdrojový text na světě, nezbývá, než jej přeložit. A o co při překladu jde?

Překlad (kompilace) programu
Překlad zdrojového kódu je proces, při němž tzv. překladač (compiler):

1. načítá postupně zdrojový kód,
2. ověřuje, zda je (syntakticky) správně napsán (zda byla dodržena gramatická pravidla daného pg. jazyka),
3. analyzuje jednotlivé programové konstrukce a
4. převádí jej do tzv. spustitelné podoby (executable code).

Při překladu jsme totiž upozorněni jen na chyby, které brání řádnému překladu - chyby, které brání řádnému fungování, překladem neodhalíme. Je to asi tak, jako nás pokročilý textový editor (např. MS Word) decentně upozorní na překlepy a eventuálně i jiné gramatické chyby, ale neposoudí za nás, zda píšeme zjevné nepravdy nebo zda sice píšeme pravdu, ale stylisticky naprosto nemožně.

• Překlad programu vyvoláme z nabídky Compile/Make nebo přímo stiskem F9.

Spuštění programu
Po řádně provedeném překladu můžeme program zkusit spustit. K tomu slouží výše zmíněná nabídka Run

• spuštění přeloženého programu: Run/Run nebo rychleji Ctrl-F9
• Nebyl-li program přeložen, nebo provedli jsme-li změny po posledním překladu, program se automaticky před spuštěním přeloží.
• Jelikož spuštěný program může být chybný a dokonce může dovést počítač (zvláště na systémech DOS a Windows 3.1) ke zhroucení, nezapomeňme program přes spuštěním uložit pomocí výše zmíněného File/Save nebo F2.

3.2. Nejjednodušší programy

Naučíme se psát, překládat a spouštět klasický ukázkový program "Ahoj".

Poznáme strukturu programu v Pascalu.

3.2.1. Nejjednodušší program v Pascalu ··· "Ahoj!" nebo "Hello, World!"?

Nebudeme rozhodně tradici porušovat a zkusíme si následující zdrojový kód přepsat (resp. načíst pomocí File/Load nebo F3 do prostředí TP.

2.	Ahoj! (Ahoj.pas)
	program Ahoj; {toto je hlavička programu} begin {toto je začátek těla programu}    writeln('Ahoj!'); {tento příkaz vypíše zprávu Ahoj!} end. {toto je konec programu}

• program Ahoj; je hlavička programu (header)
• begin je začátek těla programu (jeho výkonné neboli příkazové části)
• writeln('Ahoj!'); je příkaz vypsání zprávy "Ahoj!" na obrazovku
• end. je konec těla programu (a tím i celého programu)

3.2.2. Programy s proměnnými

Pochopíme, k čemu slouží tzv. proměnné.

Naučíme se pracovat s jednoduchou číselnou informací: načíst, jednoduše vypsat

Vstupní a výstupní údaje: Kam s nimi?
Jak jsme již naznačili: aby program vůbec něco užitečného činil, musí

Mezivýsledky výpočtů a načtené hodnoty: Kam s nimi?
Každý jen trochu složitější postup počítačového řešení problému také vyžaduje možnost ukládat mezivýsledků, ke kterým se vrátíme později a uloženou hodnotu použijeme. Například počítáme-li daň z příjmů, musíme zvlášť spočíst daňové základy pro jednotlivé typy příjmů a někde si je zapamatovat - na daňovém přiznání na to máme kolonky, v počítači paměť. Teprve na závěr je sečíst a provést výpočet příslušné daně z příjmu.

Ukládat potřebujeme i složitější data
Mezivýsledky matematických výpočtů nejsou jedinými objekty, které potřebujeme ukládat do paměti. Bez možnosti ukládat údaje by samozřejmě nefungovalo ani žádné hromadné zpracování dat - databáze. Například při sestavování Zlatých stránek - telefonního seznamu - je třeba o každém telefonním účastníkovi, který nevylučuje zveřejnění telefonního kontaktu, evidovat jméno (člověka nebo organizace), adresu a telefonní číslo.

Způsoby ukládání a práce s údaji při hromadném zpracování dat - v databázích - se však svými technikami poněkud liší od práce s daty v běžných (univerzálních) programovacích jazycích, se kterými budeme pracovat my.

Budeme tedy od nynějška údajům říkat poněkud konkrétněji (a "počítačověji") data a naznačíme si, jak s nimi pracovat.

Proměnná: místo uložení údaje (hodnoty)
Na průběžné ukládání dat používáme v běžných programovacích jazycích proměnné.

Proměnná je vlastně vyhrazené místo v paměti, do nějž lze uložit určitou hodnotu (údaj) - a později (ale v rámci jednoho běhu programu) tento údaj z tohoto paměťového místa nezměněný přečíst.

Následující program ukazuje, jak se pracuje s jednou proměnnou, která se jmenuje t a nese číselnou hodnotu nějaké blíže neupřesněné teploty.

3.	Teplota (Teplota.pas)
	program Teplota; var t: real; begin      write('Jaka teplota byla vcera rano (ve stupnich Celsia)?: ');      readln(t);      writeln('Vcera bylo ',t,' °C'); end.

3.2.3. Každá proměnná se musí nějak jmenovat ··· Identifikátor (jméno) proměnné

K čemu identifikátor je?
Identifikátor (koneckonců už z názvu je to jasné...) jednoznačně určuje (=identifikuje), o kterou proměnnou se právě, jedná. Identifikátory se nepoužívají pouze k označování proměnných,ale i jiných objektů, procedur, konstant atd., zkrátka čehokoli, co my nebo autoři samotného překladače Pascalu vytvořili a určili k použití sobě či jiným.

Jak identifikátor musí vypadat?

• Identifikátor je konečná posloupnost písmen a číslic začínající písmenem.
• Prakticky překladač rozlišuje identifikátory jen po určitý počet znaků.
• Identifikátor nesmí obsahovat mezeru
• Identifikátor volíme tak, aby z něj bylo ihned zřejmé, jakou hodnotu proměnná ponese.
• V Pascalu se nerozlišují identifikátory lišící se pouze "velikostí" písmen: pocetOsob je tatáž proměnná jako pocetosob nebo POCETosoB. Ve většině jiných jazyků však malé písmeno znamená něco jiného než velké, proto se snažíme dodržovat naprosto stejný způsob zápisu jednoho identifikátoru v rámci celého programu. Ulehčí nám to mj. případný přepis do jiného jazyka.

"Rozumnými" identifikátory jsou tedy např. teplota, celkemKc, pocetOsob, vyska, cenaZaJednotku, atd.

Výše uvedené identifikátory se vyznačovaly dodržováním těchto zásad:

1. začínaly vždy malým písmenem;
2. pokud byly složeny z více slov, počáteční písmeno druhého a dalších slov bylo velké (např. pocetOsob);

Pravidlo 1. se týká pouze identifikátorů proměnných, pravidlo 2. je obvyklé pro všechny identifikátory.

Místo velkých písmen uprostřed složeného identifikátoru se též užívá znak podtržítko _, např. teplota_vody místo teplotaVody.

3.2.4. Typ proměnné

Z metodického hlediska toto není příliš dobré - autor programu není nucen si přesně rozmyslet, co vlastně proměnná bude a smí uchovávat. Program pak nemusí rozpoznat, zdali podivná změna typu proměnné je OK, nebo došlo k nechtěné chybě.

V jazyce Pascal, se kterým začneme pracovat my, je to jasné. Až na naprosto výjimečné a velmi málo používané obraty je všude datový typ proměnné přesně a napevno definován.

Používanými typy proměnných jsou mimo jiné číselné proměnné a to buď celočíselné (mohou uchovávat jen celá čísla) nebo reálné (mohou uchovávat i čísla necelá). Více o typech proměnných řekneme dále.

3.2.5. Deklarace proměnné

4.

Příklady deklarací proměnných (Deklarace.pas)

program Deklarace; {toto je hlavička programu}     {následuje deklarace dvou proměnných s přípustnými reálnými hodnotami} var teplotaVody, teplotaVzduchu: real;     {následuje deklarace dvou proměnných s celočíselnými hodnotami}     {všimněte si, že neopakujeme "var" }          pocetLidi, pocetBazenu: integer; begin {toto je začátek těla programu}                         {program nemá nic v těle - nedělá tedy vůbec nic!} end. {toto je konec programu}

var teplotaVody, teplotaVzduchu: real;

3.2.6. Proměnné nejsou jen jednoduché...

Jednoduché proměnné
U jednoduchých problémů počítajících s čísly - např. výpočet dopravného na určitou vzdálenost, výpočet objemů či povrchů těles, měnové převody atd. - vystačíme s proměnnými, které nesou vždy po jedné (jednoduché) číselné hodnotě. Tato hodnota se samozřejmě může za běhu programu měnit.

Složené (strukturované) proměnné
Teprve u složitějších, strukturovanějších, problémů, nestačí uvažovat pouze jednoduché proměnné, ale často je nezbytné současně manipulovat s více proměnnými (třeba je všechy zvýšit o jedničku, vynásobit nějakým číslem nebo je uspořádat podle velikosti). Počet těchto "více proměnných pohromadě" často není dopředu znám - může se měnit podle momentálního přání uživatele, obsluhujícího program. Zatím však zůstaňme u jednoduchých (nesložených) proměnných - kdo zvládne práci s nimi, snadno naučené postupy rozšíří na proměnné složené - obsahující jednoduchých proměnných více. A naopak - kdo bude mít potíže již zde, neměl by se až do dokonalého zvládnutí pouštět dále.

3.3. Jednoduché výpočty s čísly

Naučíme se provádět s čísly jednoduché výpočty

Zvládneme sestavování jednoduchých výrazů k výpočtům podle určitého matematického vzorce.

5.

Bazén (Bazen.pas)

program Bazen; var d, s, h: real; {délka, šířka i hloubka bazénu jsou reálná čísla d,s,h}     cenaM3: real; {cena vody za m3 i celková cena za napuštění bazénu jsou reálná čísla}     cena: real; begin      write('Delka bazenu (v metrech): '); {uživatel zadá potřebné vstupy}      readln(d);      write('Sirka bazenu (v metrech): ');      readln(s);      write('Hloubka bazenu (v metrech): ');      readln(h);      write('Cena kubiku vody (v Kc/m3): ');      readln(cenaM3);      cena := cenaM3 * h * d * s; {program vypočte cenu vody na napuštění bazénu}                                                 {a tuto cenu vypíše...}      writeln('Cena vody na napusteni jednoho bazenu je ', cena:8:2, ' Kc'); end.

1. příkaz write vypíše dotaz na uživatelský vstup: Delka bazenu (v metrech):;
2. příkaz readln počká, až uživatel prostřednictvím klávesnice zadá délku bazénu (samozřejmě bez jednotek - metrů - a místo desetinné čárky používáme desetinnou tečku);
3. zadaná hodnota se načte do proměnné d;
4. ... obdobně pro šířku a hloubku bazénu ...;
5. tzv. přiřazovací příkaz cena := cenaM3 * h * d * s; zjistí objem bazénu v m3 a vynásobí jej cenou za m3, tím spočte celkovou cenu a tuto přiřadí do proměnné cena.

Následující program je obdobou předchozího, jen půdorys bazénu není obdélníkový, ale kruhový. Na spočtení objemu bazénu budeme tedy potřebovat známý vzorec pro výpočet objemu válce.

• funkci sqr (druhá mocnina) a
• vestavěnou konstantu pi (Ludolfovo číslo).

6.	Bazén (KruhovyBazen.pas)
	program KruhovyBazen; var d, h: real;     cenaM3: real;     cena: real; begin      write('Prumer bazenu (v metrech): ');      readln(d);      write('Hloubka bazenu (v metrech): ');      readln(h);      write('Cena kubiku vody (v Kc/m3): ');      readln(cenaM3);      cena := cenaM3 * h * pi * sqr(d/2);      writeln('Cena vody na napusteni jednoho bazenu je ', cena:8:2, ' Kc'); end.

1. několikeré použití proměnných typu real: např. d, s, cenaM3 apod.;
2. poznali jsme příkaz write (vypsání na obrazovku) a
3. příkaz readln (načtení vstupu do proměnné);
4. přiřazovací příkaz :=, který hodnotu výrazu na jeho pravé straně (za znaménkem "dvojtečka rovná se") přiřadí do proměnné na jeho levé straně (před znaménkem "dvojtečka rovná se").

3.4. Jaké číslo vlastně potřebujeme?

Pochopíme rozdíl mezi celočíselnou a neceločíselnou informací (proměnnou).

Naučíme se mezi nimi převádět.

Celá nebo reálná čísla?
Při práci s číselnými hodnotami nastávají v zásadě dva odlišné případy:

• buďto potřebujeme pracovat s čísly celými (včetně záporných nebo bez nich) a nebo problém vyžaduje
• použití čísel s desetinnou částí (např. při práci s nezaokrouhlenými peněžními částkami).

3.4.1. Celá čísla jsou často užitečná

Pochopíme, že celočíselné typy nejenže bývají úspornější na paměť i výpočetní čas, ale umožňují oproti reálným číslům i něco navíc.

Poznáme speciální celočíselné operátory (div, mod).

Kdy celé číslo?
Tj. ponese-li proměnná třeba pořadové číslo měsíce v roce (tedy celá čísla v rozsahu 1-12), vytvoříme raději proměnnou s datovým typem celočíselným. Předejdeme tím řadě možných problémů např. s nechtěným a nesprávným zaokrouhlováním. Totéž by mmch platilo i pro dny v měsíci (1-31) a letopočet. U sekund už by to bylo sporné, často totiž chceme uchovat i desetiny či setiny, prostě zlomky sekund.

Volba celých čísel přináší možnost použití speciálních operací definovaných jen pro celočíselné typy. Patří k nim především operace

1. celočíselného dělení: div a
2. zbytku po celočíselném dělení: mod.

7.

Demo na celočíselné operace (DemoCelociselnychOp.pas)

program DemoCelociselnychOp; var a,b:integer; begin        {toto bude jen statická ukázka}    writeln(' 7 div 3 = ', 7 div 3, ', 7 mod 3 = ', 7 mod 3);    writeln(' -7 div 3 = ',-7 div 3, ', -7 mod 3 = ', -7 mod 3);    writeln(' 7 div -3 = ', 7 div -3, ', 7 mod -3 = ', 7 mod -3);    writeln(' -7 div -3 = ',-7 div -3, ', -7 mod -3 = ', -7 mod -3);    {a tady může uživatel zadat, co chce spočítat}    write('Zadej delence: ');    readln(a);    write('Zadej delitele: ');    readln(b);    writeln('Celociselny podil ',a,' div ',b,' = ', a div b);    writeln('Zbytek po celociselnem deleni ',a,' mod ',b,' = ', a mod b); end.

Následující programy ukážou situace, kde je použití celočíselných proměnných takřka nezbytné, protože dovoluje využít celočíselné operace - dělení a zbytek po dělení.

8.	Čtverce z obdélníka (CtverceZObdelnika.pas)
	program CtverceZObdelnika; var a, b, x: integer; begin      write('Zadejte rozmery obdelnikove latky: ');      readln(a, b);      write('Zadejte stranu vystrihovanych ctvercu: ');      readln(x);      writeln('Z latky o rozmerech ',a,' x ',b,' lze nastrihat ',               (a div x)*(b div x),' ctvercu o strane ',x); end.

Další program je mírnou modifikací téhož: situace se odehrává ve skladu krychlových beden.

9.	Totéž ve 3D - sklad beden (SkladBeden.pas)
	program SkladBeden; var a, b, c, x: integer; begin      write('Zadejte rozmery skladu (v metrech): ');      readln(a, b, c);      write('Zadejte hranu krychlove bedny (v metrech): ');      readln(x);      write('Do skladu o rozmerech ',a,' x ',b,' x ',c, ' lze ulozit ');      writeln((a div x)*(b div x)*(c div x),' beden o hrane ', x ,' metru.'); end.

Kdy se celá čísla nehodí?
Naopak, pokud pracujeme s peněžními částkami, bylo by asi zbytečné ukládat "korunovou" část (celé koruny) do jedné celočíselné proměnné a haléře do druhé celočíselné proměnné a mít tak místo jedné hned dvě proměnné. Raději potom zůstaneme o typu s možnou desetinnou částí. Následující typický "příklad z Bělouna", tedy z populární příručky pro přípravu k přijímacím zkouškám na SŠ, ukazuje, kde se zcela jistě bez reálných čísel neobejdeme. Program počítá, za jak dlouho nateče nádrž, je-li napouštěna oběma přítoky současně.

10.

Nádrž se dvěma přítoky (NadrzSPritoky.pas)

program NadrzSPritoky; var a, b, c: real; begin      write('Prvnim pritokem se nadrz naplni za (hodin): ');      readln(a);      write('Druhym pritokem se nadrz naplni za (hodin): ');      readln(b);      {jaká část nádrže nateče přítokem a? - přece 1/a, podobně pro b       oběma přítoky současně tedy za hodinu nateče 1/a + 1/b nádrže       celá nádrž tedy nateče za 1/(1/a+1/b) hodin}             c := 1/(1/a+1/b);      writeln('Obema pritoky se nadrz naplni za ', c:8:2, ' hodin.'); end.

Když celé číslo, tak jakého typu?
Rozhodneme-li se, že daná proměnná bude uchovávat výlučně celá čísla, musíme být ještě poněkud konkrétnější. Celočíselná proměnná má stejně jako každá jiná své místo v paměti a velikost tohoto místa předurčuje, v jakém rozsahu celých čísel se může obsah proměnné pohybovat.

Následující program ukazuje příklady deklarací celočíselných proměnných různých přípustných typů. Program jednoduše zadeklaruje pět proměnných i až m, různých celočíselných typů. Jinak neprovede vůbec nic. Všimněte si, že deklarace jsou psány "zhuštěně", kíčové slovo var je uvedeno jen před prvním deklarací, pak už následují jen dvojice navzájem oddělené středníky: proměnná: typ; (např. k: integer;.

11.	(Integers.pas)
	program Integers; var i: byte;     j: shortint;     k: integer;     l: word;     m: longint; begin end.

Čísla se znaménkem nebo bez?
Zejména je třeba odlišit, zdali proměnná může nést i hodnoty záporné. Jde-li nám o proměnnou, která uchová pořadové číslo závodníka na startu nějaké soutěže, nemají záporné hodnoty (ani nula) smysl. Naproti tomu, pokud nám u konkrétního závodníka půjde o relativní pořadí vůči jinému soutěžícímu, záporná čísla jsou nezastupitelná; náš závodník je před ním nebo za ním a jeho relativní pořadí má tudíž pokaždé opačné znaménko.

Rozsahy číselných hodnot
které lze uložit do určité proměnné, jsou dány typem této proměnné. Obecně souvisejí samozřejmě s paměťovými nároky a možnostmi. Čím větší rozsah možných hodnot po proměnné požadujeme, tím více paměti bude proměnná zabírat. A to bez ohledu, je-li momentálně její rozsah využit (je tam nyní obrovské číslo) nebo nikoli (je tam číslo malé, třeba nula).

Programovací jazyky historicky starší nabízejí obvykle typy proměnných dovolujících menší rozsah (dříve byla větší omezení na paměť). Pascal je v tomto také díky své minulosti "skromný". Základním typem celočíselné proměnné je zde integer s rozsahem -32768..32767.

Jsou záporná čísla zcela "rovnocenná"?
Vnitřní kódování celých čísel v paměti počítače je konstruováno tak, aby rozsah celočíselných hodnot byl v optimálním případě stejně velký směrem do kladných čísel jako do záporných. Výjimkou z dokonalé symetrie kladného a záporného rozsahu je "přebývající" nejnižší záporná hodnota - ta už nemá svůj opačný (=kladný) protějšek. Následující tabulka ukazuje, jak to vypadá u nejběžnějšího celočíselného typu se znaménkem - typu integer.

-32768 = 10000000 00000000
-32767 = 10000000 00000001
      ...
    -1 = 11111111 11111111
     0 = 00000000 00000000
     1 = 00000000 00000001
     2 = 00000000 00000010
      ...
 32766 = 01111111 11111110
 32767 = 01111111 11111111

Jak se počítání s hodnotami typu integer chová, ilustruje následující program.

12.	Přetečení rozsahu hodnot typu integer (IntegerOverflow.pas)
	program IntegerOverflow; var i: integer; begin    i := 32767; {přiřadíme maximální možnost hodnotu}    writeln(i); {vypíše se v pořádku}        i := i + 1; {zvýšíme ještě o jedničku}    writeln(i); {a už to není OK...} end.

Dvojkový doplňkový kód
Tato asymetrie (záporných hodnot je o jednu více než kladných) je způsobena použitím tzv. dvojkového doplňkového kódu pro zobrazení záporných čísel a vyskytuje se dnes téměř na všech počítačích (minimálně počítačích postavených na procesorech Intel 80x86 a kompatibilních - tedy na všech běžných PC).

Proč nepoužívat zbytečně čísla se znaménkem?
Je-li povaha úlohy takové, že pro proměnnou nikdy nevyžaduje záporné hodnoty, je metodicky lépe zvolit typ bez znaménka (bez možných záporných hodnot) - tím se nám při stejných paměťových nárocích zvětší přípustný rozsah do kladných hodnot. Následující tabulka ukazuje, jak to vypadá u nejběžnějšího celočíselného typu bez znaménka - typu word. Tento typ poskytuje na stejném počtu bitů (tedy při stejně velkém "záboru" paměti jako integer), rozsah až do kladné hodnoty 65535.

     0 = 00000000 00000000
     1 = 00000000 00000001
     2 = 00000000 00000010
      ...
 32766 = 01111111 11111110
 32767 = 01111111 11111111
      ...
 65535 = 11111111 11111111

Jaké další celočíselné typy v Pascalu máme?
Následující tabulka přesně uvádí, co nabízí Turbo Pascal 5.5, pokud jde o celočíselné datové typy.

Typ        Rozsah          Se znaménkem?  Obsadí bitů
-----------------------------------------------------
Shortint   -128..127                 ano            8
Integer    -32768..32767             ano           16
Longint    -2147483648..2147483647   ano           32
Byte       0..255                    ne             8
Word       0..65535                  ne            16

Přílišná úspornost nic nepřináší
Paměťové a výkonnostní možnosti dnešních počítačů jsou natolik dobré, že nemá smysl volit vždy "nejmenší" a "nejúspornější" typ číselné proměnné s rizikem, že se časem může objevit hodnota, která rozsahu překročí.

Úloha č. 2. Zvolte vhodný číselný typ pro reprezentaci dne v týdnu (Po-Ne).

Úloha č. 3. Zvolte vhodný číselný typ pro reprezentaci délky časového úseku udané v milisekundách (úsek přitom může trvat až 1 rok).

Úloha č. 4. Uspořádejte číselné proměnné podle jejich vzrůstajících paměťových nároků (tj. podle toho, kolik jedna proměnná příslušného typu zabere v paměti). Pokud mají dvě proměnné různého typu paměťové nároky stejné, uveďte na první místo tu, jež má větší rozsah do kladných hodnot.

integer, word, byte, long

Úloha č. 5. Upravte níže uvedený program tak, aby přijímal a správně zpracovával i částky větší než tisíc korun.

3.4.2. Čísla "necelá"

Poznáme, že kromě čísel celých - bez desetinné části - lze na počítači pracovat i s čísly desetinnými.

Naučíme se tyto typy čísel vhodně používat.

Zápis čísla s desetinnou částí
Čísla s desetinnou částí se v běžných programovacích jazycích realizují pomocí tzv. pohyblivé řádové čárky (floating point). Pohyblivá řádová čárka odpovídá zápisu čísel v tzv. vědecké nebo přesněji semilogaritmické notaci. Číslo je v ní uloženo jako mantisa (se znaménkem) a exponent (opět se znaménkem).

0
-1.5
9.87600000000000E+0003 - odpovídá hodnotě 9876
9.87600000000000E+03 - odpovídá také hodnotě 9876

Co udává velikost prostoru pro mantisu?
Pro mantisu a exponent je vyhrazen prostor, jehož velikost znamená u mantisy

• přesnost zaznamenaného čísla (odpovídá počtu platných míst).

Volba přesnosti čísel
Následující prográmek jasně ukazuje, že "základní" přesnost pro čísla s desetinnou částí nemusí vždy stačit a že dokonce i v poměrně jednoduchém případě se projeví nepřesnosti - a to ani nemusíme nic počítat, stačí jen číslo přiřadit - a chyba je na světě.

13.	Srovnání přesnosti dvou pascalských neceločíselných typů (real a extended). (Reals.pas)
	program Reals; uses crt; var r: real;     e: extended; begin    clrscr;    r := sqrt(2);    e := sqrt(2);    writeln('Odmocnina z 2 v promenne typu real = ',r);    writeln('Odmocnina z 2 v promenne typu extended = ',e);    writeln('Znovu umocnime (real) = ',sqr(r));    writeln('Znovu umocnime (extended)= ',sqr(e)); end.

Na výpisu je to jednoznačně vidět:

Pokud nám výše uvedený program dělal problémy již při překladu - chyba Error 116: Must be in 8087 mode to compile this, musíme upravit volby překladače tak, aby překladač produkoval kód pro matematický koprocesor. Výpočty v reálných číselných typech "větších" než real se totiž, zejména z důvodu rychlosti, bez koprocesoru neobejdou. Naštěstí dnes každý běžně používaný počítač koprocesorem disponuje (počínaje stroji s procesorem 486DX). Nastavení voleb překladacče naznačuje obrázek (podstatné je, aby se u volby Numeric processing objevilo 8087/80287):

Rozsah mantisy
Optimální je, můžeme-li si přesně zvolit, jakou přesnost (např. tedy kolik desetinných míst) může nejvýše proměnná mít. Takto detailní nastavení bohužel Pascal neumožňuje, ale systémy určené pro pokročilou práci s čísly - třeba tabulkové procesory, databáze nebo matematické programy - toto dovolují. Přesto i univerzální pg. jazyky - Pascal nevyjímaje - umožňují požadovanou přesnost alespoň "zhruba" zvolit - v Pascalu máme pro čísla s desetinnou částí (krom jiných) dvě podstatné možnosti - "základní" (typ real) a "zvýšenou" (typ extended) přesnost. Na přechozím kódu jsme viděli, že i takové "krátké" číslo, jakým je odmocnina ze dvou nelze s absolutní přesností v proměnné typu real (proměnná r) uchovat. V proměnné typu extended (proměnná e) samozřejmě také ne, ale chyby při výpočtech jsou zjevně menší.

Rozsah exponentu
Naopak rozsah exponentu předurčuje možný rozsah velikosti celého čísla - tedy jak maximální možnou uložitelnou hodnotu, tak hodnotu nejbližší nule. Následující prográmek jako jeden z mála v předložené podobě nefunguje, a to úmyslně: překladač totiž zahlásí na přiřazení a2:=1.23456789e39; chybu "Error 76: Constant out of range", tedy to, co jsme chtěli přiřadit do proměnné a2 typu real, se tam jednoduše "nevejde".

14.	Srovnání rozsahu dvou běžných pascalských neceločíselných typů (real a extended). (Reals2.pas)
	program Reals2; var r: real;     e: extended; begin    r:=1.23456789e39;    e:=1.23456789e39;    writeln(r);    writeln(e); end.

Po snížení hodnoty v přiřazení na a2:=1.23456789e38; lze program přeložit a my můžeme program přeložit a spustit.

Reálné číselné typy v Pascalu
Následující tabulka je převzata přímo z nápovědy Borland Pascalu 7.0 a představuje možný rozsah a přesnost jednotlivých neceločíselných typů u tohoto překladače. Prakticky se nejčastěji používá real a při potřebě vyšší přesnosti extended.

typ      ¦ rozsah              ¦ číslic ¦ bajtů
-----------------------------------------------
real     ¦ 2.9e-39..1.7e38     ¦ 11-12  ¦  6
single   ¦ 1.5e-45..3.4e38     ¦  7-8   ¦  4
double   ¦ 5.0e-324..1.7e308   ¦ 15-16  ¦  8
extended ¦ 3.4e-4932..1.1e4932 ¦ 19-20  ¦ 10
comp     ¦ -9.2e18..9.2e18     ¦ 19-20  ¦  8

"Podivný" typ comp
Typ comp je de facto vnitřně celočíselný, s proměnnými tohoto typu lze však manipulovat jako s neceločíselnými, tj. přiřazovat do nich hodnoty v semilogaritmickém tvaru. Jeho rozsah - viz tabulka výše - je však menší než u real. Více ukáže příklad.

15.	Typ comp (Reals3.pas)
	program Reals3; var c: comp; begin    c:=1e18;    writeln(c); end.

Proč "pohyblivá řádová čárka"? Co přináší za výhody a problémy?
"Pohyblivost" řádové čárky je skryta v tom, že bez ohledu na absolutní velikost čísla nás z hlediska přesnosti zajímá vždy právě počet platných cifer, který vlastně udává relativní přesnost. Mantisa tedy vždy zachycuje určitý počet (dáno velikostí mantisy) těchto platných číslic bez ohledu na velikost čísla. Případné platné cifry, které se do mantisy nevešly, jsou automatickým zaokrouhlením nevratně odstraněny. Kvůli tomu se potom může stát, že po provedení určité operace, která zvýší počet platných (např. desetinných) míst dostaneme nepřesný výsledek. To může vést k absurdním a matematicky nesmyslným důsledkům, že operace a její inverze (obrácení) nevedou zpět k výchozímu číslu - to jsme viděli u odmocniny a mocniny!

Samozřejmě, problém je skryt v konečné velikosti paměťového prostoru pro mantisu a exponent. Proto se při operacích občas musí zaokrouhlovat a tím se přesnost ztrácí.

3.5. Jak tedy používat číselné proměnné v Pascalu?

3.5.1. Metodika práce s čísly

1. zvolit mezi celočíselnou proměnnou a proměnnou s pohyblivou řádovou čárkou
2. vhodně vybrat rozsah (u celočíselné proměnné) či přesnost+rozsah (u proměnné s pohyblivou řádovou čárkou)
3. proměnnou deklarovat (v úvodní - deklarační - části programu)
4. proměnnou používat (v příkazové - výkonné - části programu)

3.5.2. Úlohy na práci s čísly

16.

Trojúhelníková nádrž (TrojuhelnikovaNadrz.pas)

program TrojuhelnikovaNadrz; var a, b, c: real;     h: real;     V, s: real; begin      write('Delka prvni strany nadrze (v metrech): ');      readln(a);      write('Delka druhe strany nadrze (v metrech): ');      readln(b);      write('Delka treti strany nadrze (v metrech): ');      readln(c);      write('Hloubka nadrze (v metrech): ');      readln(h);      s := (a + b + c)/2;      V := h * sqrt(s * (s-a) * (s-b) * (s-c));      writeln('Do nadrze se vejde ', V, ' m3 vody.'); end.

Nyní již několik úloh na procvičení. Je potřeba si zejména připomenout, jak se počítají úroky v složeném úročení...

Úloha č. 6. Napište program na výpočet objemu koule s poloměrem r. Vyjděte z výše uvedeného programu.

Úloha č. 7. Napište program, který vypočte úroky z pevného vkladu za jedno měsíční úrokové období (je dána roční úroková sazba - je potřeba z ní spočíst úroky za měsíc - a procento zdanění přibylých úroků).

Úloha č. 8. Upravte výše uvedený program tak, aby spočítal úroky i za více období. Předpokládejte složené úročení se stabilní úrokovou sazbou po celou dobu.

Úloha č. 9. Napište program, kterému uživatel zadá celé číslo v rozsahu 0-80 a program vypíše na jeden řádek zadaný počet hvězdiček.

3.6. Lepší výstup (výpis) číselné informace

Naučíme se formátovat výstup číselné informace do vhodné podoby (počty míst a desetinných míst).

Zvládneme zaokrouhlování.

Neformátovaný výpis - nepřehledný, nehezký...
Následující příklad ukazuje, jak "nehezké" mohou být výpisy zvláště u reálných čísel (např. typů real a extended). Každé necelé číslo je totiž vypisováno v semilogaritmickém tvaru a ten rozhodně nebývá dobře čitelný. Posuďte sami:

17.

Mzda s přesčasy (MzdaSPrescasy.pas)

program MzdaSPrescasy; uses crt; var hodinNormal, hodinPrescas: real;     hodMzdaNormal: real;     mzdaCelkem: real; begin      clrscr;      write('Odpracovano v bezne prac. dobe (v hod): ');      readln(hodinNormal);      write('Odpracovano prescasu (v hod): ');      readln(hodinPrescas);      write('Hodinova mzda v bezne prac. dobe (v Kc): ');      readln(hodMzdaNormal);      {spočteme celkovou mzdu, přesčasová se počítá * 1.5}      mzdaCelkem := hodMzdaNormal * (hodinNormal + hodinPrescas * 1.5);      writeln('Celkova mzda bude ', mzdaCelkem, ' Kc'); end.

A tohle program po zadání potřebných vstupních údajů vypsal:

Program sice správně spočetl celkovou mzdu, ale vypsal ji tak, že dotyčný zaměstnanec by asi na pokladně nic nedostal, protože takový zápis by pokladní nedešifrovala... S tím výpisem čísel je třeba něco udělat!

3.6.1. Formátování výpisu čísel

Pokud do výpisu write(cislo) přidáme například write(cislo:6:2), bude číslo vypsáno na celkem šest míst (pozic, znaků), z nichž dvě místa budou desetinná, tj. za desetinnou tečkou.

Formátování nám umožní vypsat více čísel hezky "jak bývá zvykem" zarovnaných. Program:

18.	Formátování výstupu (format.pas)
	program Format; begin     writeln(1.0:6:2);     writeln(100.5:6:2);     writeln(-2.5:6:2); end.

  1.00
100.50
 -2.50

Formátování výstupu reálných a celých čísel
Ve formátovací specifikaci cislo:CelkovyPocetZnaku:PocetDesetinnychMist tedy hodnota za první dvojtečkou udává, kolik bude míst výstup čísla dohromady míst včetně případného znaménka a hodnota za druhou dvojtečkou říká, kolik míst z tohoto počtu bude desetinných. Tuto druhou hodnotu je možné vypustit, pak udáváme pouze celkový počet míst. To však pro výpis reálných čísel raději nedělejme a tuto možnost si nechejme výhradně pro čísla celá.

V následujícím programu, který rozpočítá údaje z tzv. jednoduchého daňového dokladu, je vidět, jak co použít: pro výpis procentní sazby daně (22% nebo 5%) použijeme nula desetinných míst, pro peněžní částky použijeme celkem osm míst, z toho dvě desetinná (pro haléře).

19.

Jednoduchý daňový doklad (JednoduchyDanovyDoklad.pas)

program JednoduchyDanovyDoklad; var celkem, sazba: real;     zaklad, dph: real; begin      write('Celkova castka na dokladu (v Kc vc. DPH):');      readln(celkem);      write('Danova sazba na dokladu (v % DPH):');      readln(sazba);      {z udané celkové částky a sazby DPH spočteme základ DPH...}      zaklad := celkem/(1+sazba/100);      {...a částku DPH}      dph := celkem - zaklad;      writeln('Zaklad DPH ',sazba:3:0, ' % je ', zaklad:8:2, ' Kc');      writeln(' DPH ',sazba:3:0, ' % je ', dph:8:2, ' Kc'); end.

3.6.2. Zaokrouhlování

20.

Mzda s přesčasy zaokrouhlená (MzdaSPrescasyZaokrouhlena.pas)

program MzdaSPrescasyZaokrouhlena; var hodinNormal, hodinPrescas: real;     hodMzdaNormal: real;     mzdaCelkem: real;     mzdaZaoukrohlena: integer; begin      write('Odpracovano v bezne prac. dobe (v hod): ');      readln(hodinNormal);      write('Odpracovano prescasu (v hod): ');      readln(hodinPrescas);      write('Hdinova mzda v bezne prac. dobe (v Kc): ');      readln(hodMzdaNormal);      mzdaCelkem := hodMzdaNormal * (hodinNormal + hodinPrescas * 1.5);            {spočtenou mzdu zaokrouhlíme na celé koruny}      mzdaZaoukrohlena := round(mzdaCelkem);      writeln('Celkova mzda bude ',mzdaZaoukrohlena, ' Kc'); end.

Například většina ústavních činitelů by měla ve výše uvedeném příkladu problémy: jejich plat totiž přesahuje rozsah hodnot použitého typu integer (32767)! Pro ně bychom museli použít "větší" celočíselný typ, např. longint, který by zatím měl vyhovět všem...

Formátováním a zaokrouhlováním skončíme úvodní "programátorskou" kapitolu a se slovy klasika: "Do teď to bylo snadné!" se vydáme dál.

4. Programy, co se umějí rozhodovat

Naučíme se psát jednoduché programy, které se umějí vybrat variantu dalšího postupu podle platnosti určité podmínky. Pochopíme, co je to větvení programu.

Naučíme se přehledně zapisovat program s větvením.

4.1. Prověření vstupu ··· Sestavení jednoduché podmínky větvení

Naučíme se psát programy, které různě zareagují na různý uživatelský vstup.

4.1.1. Sestavujeme to nejjednodušší větvení

Kdybychom měli takové větvení programu znázornit vývojovým digramem, vypadal by nějak takto:

Následující program ukazuje, jak dosáhneme toho, že různý uživatelský vstup způsobí různé chování programu. Nové oproti předchozím příkladům programů je právě ono větvení představované příkazem if then. Za if napíšeme podmínku, která, je-li splněna (na obrázku označeno jako větev +), způsobí, že se provádí příkaz za then. Jinak (na obrázku označeno jako větev -) se neprovede nic. Dochází tedy k podmíněnému provádění příkazu a uvedená konstrukce je tedy tzv. podmíněným příkazem.

21.	Zopakování uživatelovy odpovědi (dvě podmínky) (OtazkaOdpoved.pas)
	program OtazkaOdpoved; var odpoved: integer; begin      write('Je Snezka nejvyssi hora CR? (0 znamena ne, 0<> znamena ano): ');      readln(odpoved);      if odpoved = 0 then writeln('odpovedel/a jste ne');      if odpoved <> 0 then writeln('odpovedel/a jste ano') end.

1. Uživatel naplní proměnnou odpoved se příkazem readln(odpoved).
2. Hodnota proměnné odpoved je následně otestována první podmínkou if.
3. Pokud uživatel odpoví číslem 0, program provede příkaz uvedený za then, tedy writeln('odpoved je ne').
4. Pokud se odpoved nerovná 0, příkaz za then se neprovede.
5. Hodnota proměnné odpoved je následně otestována druhou podmínkou if.
6. Pokud uživatel odpoví číslem různým od 0 (např. 1), program provede příkaz uvedený za then, tedy writeln('odpoved je ano').
7. Pokud se odpoved rovná 0, příkaz za then se neprovede.

22.	Zopakování uživatelovy odpovědi (jedna podmínka) (OtazkaOdpoved2.pas)
	program OtazkaOdpoved; var odpoved: integer; begin      write('Je Snezka nejvyssi hora CR? (0 znamena ne, 0<> znamena ano): ');      readln(odpoved);      if odpoved = 0 then writeln('odpovedel/a jste ne')                     else writeln('odpovedel/a jste ano') end.

1. Uživatel naplní proměnnou odpoved se příkazem readln(odpoved).
2. Hodnota proměnné odpoved je následně otestována podmínkou za if.
3. Pokud uživatel odpoví číslem 0, program provede příkaz uvedený za then, tedy writeln('odpoved je ne').
4. Pokud uživatel odpoví číslem různým od 0 (např. 1), program provede příkaz uvedený za else, tedy writeln('odpoved je ano').
5. Zde už dochází k tzv. úplnému větvení programu podle výsledku určitého testu - podle platnosti určité podmínky program pokaždé provede různou akci.

Využití větvení pro uspořádání dvou čísel
Příkazu větvení využijeme pro uspořádání dvou zadaných čísel podle velikosti: je-li zadané a menší nebo rovno b, jsou čísla ve vzestupném pořadí a, b. Jinak (neboli když a > b) jsou v pořadí b, a. Program ukazuje vše:

23.	Uspořádat dvě čísla! (UsporadatDveCisla.pas)
	program UsporadatDveCisla; var a, b: integer; begin      write('Zadejte na radek dve cela cisla: ');      readln(a, b);      if a <= b then writeln(a, ' <= ', b)                else writeln(b, ' <= ', a) end.

Z programu by mělo být vše jasné, ale pro pořádek ještě protentokrát uveďme, jak by vypadal příslušný vývojový diagram:

Jelikož podmíněný příkaz (větvení) již může programy trochu zkomplikovat, je čas říci si základní zásady čitelného zápisu programu.

4.1.2. Abychom se v programu vyznali

Naučíme se čitelně a přehledně zapisovat text programou

Celková úprava programu
Přehledný a esteticky přijatelný zápis kódu programu je téměř stejně podstatný jako jeho správnost. Proto úpravě kódu věnujeme adekvátní pozornost.

Dodržováním pravidel psaní čitelných programů si mimo jiné ušetříme pracné "luštění" kódu programu v době, kdy už nám jeho struktura dávno z hlavy vypadla a my budeme sami přemýšlet "co jsme tímto vlastně mysleli". Stejně tak jistě uvítáme, budou-li čitelné programy psát ti, jejichž programová díla jsme nuceni číst.

24.	Ukázka "hezky upraveného" kódu programu (Odsazeni.pas)
	program NazevProgramu; var i: integer; begin    readln(i);    writeln(i); end.

• prázdné řádky mezi hlavními částmi programu - za hlavičkou program, za deklarací var i: integer; (tyto prázdné řádky nejsou nutné, mnoho programátorů je nedělá...)
• vždy tři mezery před začátkem kódu na řádcích mezi begin a end. Právě těmto mezerám před začátkem kódu na řádku se teď budeme věnovat podrobněji.

Odsazování
Psaní mezer před - tedy posunutí příkazů mezi readln a writeln se nazývá odsazení (indent). Počet odsazovacích mezer byl v naší ukázce tři, což nemusí platit v každém programu. Mnozí píší místo třech mezer čtyři, pět nebo osm. Dodržujme však následující pravidla:

• Místo psaní mezer lze použít stisk klávesy tabelátor (Tab).
• Stanovíme si velikost odsazení (počet mezer) jednou a v celém programu jej dodržujeme stejný.
• Méně než tři mezery je příliš málo, více jak osm se nepoužívá.

Příklady
Na závěr úvodní sekce o větvení/podmíněných příkazech uveďme ještě dva jednoduché příklady s použitím podmíněného příkazu if.

První z nich spočítá absolutní hodnotu zadaného čísla. Jak známo, absolutní hodnota je pro kladné číslo (a také nulu) rovna přímo tomuto číslu, pro záporné číslo je rovna číslu opačnému. Stačí tedy otestovat, je-li zadané číslo >= 0 a podle platnosti této podmínky se zachovat:

25.

Absolutní hodnota (AbsHodnota.pas)

program AbsHodnota; var cislo, abshodn: integer; { Budeme počítat absolutní hodnotu jen z celých čísel.} begin      write('Zadejte cele cislo: '); { zeptáme se uživatele na vstup }      readln(cislo); { uživatel zadá celé číslo (nečíselný vstup způsobí chybu!) }                                 { je-li číslo kladné - tj. větší nebo rovno 0,                                   je abs. h. rovna přímo tomuto číslu,                                   jinak je rovna číslu opačnému }         if cislo > 0 then abshodn := cislo                   else abshodn := -cislo;      writeln('abs(',cislo,') = ',abshodn) { vypíšeme výsledek } end.

Zadání druhého příkladu je opět jednoduché: napsat program, který si "vymyslí" nějaké náhodné číslo mezi 1 a 100, zeptá se uživatele na jeho "tip" a uživatelův odhad srovná s "myšleným" číslem.

26.

Myslím si číslo, hádej! (MyslimCislo.pas)

program MyslimCislo; var cislo, odhad: integer; begin      {inicializuj generátor náhodných čísel}      randomize;      {generuj náhodné číslo mezi 1..100}      cislo := random (100) + 1;      write('Myslim si cislo (1..100). Hadejte, jake: ');      readln(odhad);      {byl odhad menší, roven nebo větší než vygenerované číslo?}      if odhad < cislo then writeln('Myslim si vetsi cislo.');      if odhad = cislo then writeln('Myslim prave toto cislo.');      if odhad > cislo then writeln('Myslim si mensi cislo.'); end.

1. Před prvním použitím v rámci programu je obvyklé jej tzv. inicializovat, neboli "zaset" do něj první hodnotu, ze které budou následně generovaná pseudonáhodná čísla vycházet. Pokud inicializaci zanedbáme, bude generátor produkovat při každém spuštění programu stejnou posloupnost (tentokrát už nepříliš náhodných :-)) hodnot. V Pascalu slouží k inicializaci - "znáhodnění" generátoru procedura randomize.
2. Potřebujeme-li získat další (pseudo)náhodné číslo, použijeme funkci random s parametrem udávajícím rozsah generovaných čísel - např. random(100) generuje čísla z intervalu [0..99].

Jinak je snad princip algoritmu použitého v programu zřejmý:

1. Vygeneruje se náhodné číslo [1..100].
2. Uživatel zadá svůj odhad tohoto čísla.
3. Program srovná tento odhad s vygenerovaným číslem a vypíše, jak se uživatel "trefil".

4.2. Sestavení složitější podmínky ··· Relační operátory

Naučíme se používat v podmínkách i složitější výrazy.

Poznáme a naučíme se sestavit podmínky s různými porovnávacími (relačními) operátory.

V následující úloze budeme řešit tento problém:

• Skladník má sklad obdélníkového půdorysu o rozměrech a krát b metrů a výšce c.
• Má do něj umístít stejně velké bedny tvaru kvádru o rozměrech: šířka x, délka y a výška z (udáváno též v metrech).
• Problém je, že bedny musí být všechny stejně orientované, tzn. všechny položené "na délku" nebo "na šířku".
• Bedny se také nesmí klopit, tj. výška jedné bedny v každém přípustném uložení zůstává z.

27.

Bedny ve skladu (SkladBeden2.pas)

program SkladBeden2; var a, b, c, x, y, z: integer;     beden: integer; begin      write('Zadejte delku a sirku skladu (v metrech): ');      readln(a, b);      write('Zadejte vysku skladu (v metrech): ');      readln(c);      write('Zadejte delku a sirku bedny (v metrech): ');      readln(x, y);      write('Zadejte vysku bedny (v metrech): ');      readln(z);      {vejde se tam těch beden více "nadél" nebo "našíř"?}      if (a div x)*(b div y) > (a div y)*(b div x)               {spočteme větší ze dvou počtů beden}         then beden := (a div x)*(b div y)*(c div z)         else beden := (a div y)*(b div x)*(c div z);      writeln('Do skladu o rozmerech ',a,' x ',b,' x ',c, ' lze ulozit ', beden,' beden.'); end.

Algoritmus je jednoduchý, centrálním bodem je porovnání, která ze dvou variant je úspornější, tj. kdy se tam vejde více beden.

Nejjednodušším řešením je spočítat, kolik beden se tam vejde v obou umístěních a porovnat tyto počty. Vzhledem k tomu, že výška je stále stejná, stačí spočíst, kolik beden se tam v obou variantách vejde půdorysně (=do jedné vrstvy) - výška beden ani skladu (díky tomu, že je neměnná) totiž nemá na úspornost vliv.

Počet počet beden v jedné vrstvě je

1. (a div x)*(b div y) nebo
2. (a div y)*(b div x) podle jejich orientace.

Čili větší složitost oproti předchozím příkladu spočívala jen ve složitějších výrazech porovnávaných v podmínce za if. Následující příklad je podobné složitosti.

Srovnání dvou vypočtených hodnot
Úkolem je srovnat úspornost pořízení a provozu dvou vozidel za určité období, během něhož najedeme s vozidlem daný počet kilometrů. U obou vozidel známe:

• pořizovací cenu;
• spotřebu paliva v l/100 km (předpokládáme, že obě vozidla používají stejné palivo);
• cenu litru paliva;
• víme, kolik chceme s vozidlem ujet kilometrů (s oběma stejně);

28.

Srovnání aut (SrovnaniAut.pas)

program SrovnaniAut; var cena1, spotreba1, cena2, spotreba2: real;     km, cenaLitruBenzinu, cenaCelkem: real; begin      write('Zadejte cenu prvniho auta: '); {cena v Kč}      readln(cena1);      write('Zadejte spotrebu prvniho auta: '); {spotřeba v l/100 km}      readln(spotreba1);      write('Zadejte cenu druheho auta: '); {cena v Kč}      readln(cena2);      write('Zadejte spotrebu druheho auta: '); {spotřeba v l/100 km}      readln(spotreba2);      write('Zadejte planovane kilometry: ');      readln(km);      write('Zadejte cenu litru benzínu: '); {cena v Kč/l}      readln(cenaLitruBenzinu);      if cena1 + spotreba1 * km/100 * cenaLitruBenzinu {celkové náklady auta 1.}         < cena2 + spotreba2 * km/100 * cenaLitruBenzinu {celkové náklady auta 2.}         then writeln('Vyhodnejsi je prvni auto s naklady ',                       (cena1 + spotreba1 * km/100):8:2, ' Kc.')         else writeln('Vyhodnejsi je druhe auto s naklady ',                       (cena2 + spotreba2 * km/100):8:2, ' Kc.') end.

K tomu asi není co dodat... Podíváme se tedy na úlohy, kde bude větvení programu trochu složitější proto, že budeme muset uvažovat více než dvě varianty dalšího postupu.

4.3. Vnořené větvení

Poznáme a naučíme se sestavit vnořené větvení programu. To nám umožní komplikovanější rozhodování s více než dvěma variantami dalšího postupu výpočtu.

Abychom tuto neefektivitu odstranili, nabízí se využití větve else, která je provedena v případě, že podmínka za if neplatí. Program nyní bude vypadat takto:

29.

Hadani cisla (HadaniCislaEfektivne.pas)

program HadaniCislaEfektivne; var cislo, odhad: integer; begin      {inicializujeme generátor náhodných čísel}      randomize;            {vygenerujeme náhodné číslo}      cislo := random (100) + 1;      {a uživatel může hádat...}      write('Myslim si cislo (1..100). Hadejte, jake: ');      readln(odhad);      {trefil se uživatel přesně?}      if odhad = cislo         then writeln('Uhodli jste!') {ano}         else if odhad < cislo {ne, pak odpovíme, je-li odhad < cislo}                 then writeln('Myslene cislo je vetsi')                 else writeln('Myslene cislo je mensi'); end.

Všimněte si odsazení vnořeného větvení - else je umístěno pod příslušným then.

Následující program by se s trochou nadsázky hodil na notebook nějaké stěhovací firmy: jeho úkolem je spočítat, zda skříň tvaru kvádru (x krát y krát z) projde dveřmi o rozměrech a krát b.

30.

Projde skříň dveřmi? (DvereSkrin.pas)

program DvereSkrin; var a, b, x, y, z: integer;     skr1, skr2: integer; begin      write('Zadejte rozmery dveri: ');      readln(a, b);      write('Zadejte rozmery skrine: ');      readln(x, y, z);      {vybereme, které dva rozměry skříně jsou nejmenší}      if x < y then         if y < z then begin            skr1 := x;            skr2 := y         end else begin            skr1 := x;            skr2 := z         end      else         if x < z then begin            skr1 := x;            skr2 := y         end else begin            skr1 := y;            skr2 := z         end;      {projde skříň svými nejmenšími rozměry dveřmi?}      if ((skr1 < a) and (skr2 < b) {zkoušíme jedním...}         or {...a druhým způsobem}         (skr1 < b) and (skr2 < a)) then writeln('Skrin dvermi projde.')                                 else writeln('Skrin dvermi neprojde.') end.

Program opět využíval - ať teď už nevyhnutelně - vnořené větvení. Povšimněme si těchto detailů: Odsazení programového kódu je trochu jiné než u předchozího příkladu: pod sebou jsou napsány příkazy if a else u vnějšího větvení;

U vnitřních větvení (vezměme například to první if y < z then...) je za then klíčové slovo begin, dosud známé jen jako uvození začátku programu. Po dvou příkazech skr1 := x a skr2 := y je potom klíčové slovo end. Proč je zde to begin a end?

Když v jedné větvi potřebujeme více příkazů ··· Blok
begin a end slouží jako jakési "závorky" tzv. bloku příkazů, umožňující, aby více příkazů vystupovalo v roli příkazu jednoho. No, a v našem příkladu jsme přece potřebovali za then umístit dva příkazy skr1 := x a skr2 := y! Takže jsme je uzavřeli mezi begin a end:

        if y < z then begin {začátek prvního bloku}
           skr1 := x; {první blok,příkaz 1}
           skr2 := y  {první blok,příkaz 2}
        end {konec prvního bloku} else begin {začátek druhého bloku}
           skr1 := x; {druhý blok,příkaz 1}
           skr2 := z  {druhý blok,příkaz 2}
        end {konec druhého bloku} 

        if y < z then 
           begin {začátek prvního bloku}
              skr1 := x; {první blok,příkaz 1}
              skr2 := y  {první blok,příkaz 2}
           end   {konec prvního bloku} 
        else 
           begin {začátek druhého bloku}
              skr1 := x; {druhý blok,příkaz 1}
              skr2 := z  {druhý blok,příkaz 2}
           end   {konec druhého bloku} 

To je možná mírně přehlednější, důvodem, proč jsem to hned nepoužil je to, že:

1. kód zabírá více řádků (10 místo 7);
2. kód "zasahuje více doprava", protože jsou delší (=více odsazené) některé řádky.

Předposlední příklad z této sekce má za cíl uspořádat tři zadaná čísla pole velikosti. Úkol se řeší pomocí větvení, které je tentokrát vnořeno až do třetí úrovně:

31.

Seřazení tří čísel (Serazeni3cisel.pas)

program Serazeni3cisel; var x, y, z: integer; begin      write('Zadejte tri cisla: ');      readln(x, y, z);      if x < y then         if x < z then            if y < z then               writeln('Cisla jsou v poradi ',x,',',y,',',z)            else               writeln('Cisla jsou v poradi ',x,',',z,',',y)         else            writeln('Cisla jsou v poradi ',z,',',x,',',y)      else         if y < z then            if x < z then               writeln('Cisla jsou v poradi ',y,',',x,',',z)            else               writeln('Cisla jsou v poradi ',y,',',z,',',x)         else            writeln('Cisla jsou v poradi ',z,',',y,',',x) end.

Sekci o vnořeném větvení nelze zakončit jinak než příkladem, který kompletně řeší určitou ne úplně triviální úlohu. Ze střední (či dokonce základní) školy bychom si ještě měli pamatovat, co to je a jak se řeší kvadratická rovnice, tj. rovnice tvaru ax2 + bx + c = 0. Se znalostí příslušného algoritmu nyní zkusíme napsat program, který rovnici vyřeší za nás - a to tak chytře, že rozpozná i všechny možné "patologické" případy, kdy rovnice dokonce ani není kvadratická nebo kdy sice je kvadratická, ale nemá reálná řešení (kořeny). Podrobný komentář k činnosti jednotlivých úseků programu naleznete přímo v jeho zdrojovém textu:

32.

Kvadratická (nebo taky lineární, konstantní...) rovnice (KvadratickaRovnice.pas)

program KvadratickaRovnice; var a, b, c: real;     D, x1, x2 : real;     x1re, x2re, x1im, x2im : real; begin      writeln('Reseni rovnice ax2 + bx + c = 0 v komplexnim oboru. Cisla a,b,c jsou realna. ');      write('Zadejte koeficient a: ');      readln(a);      write('Zadejte koeficient b: ');      readln(b);      write('Zadejte koeficient c: ');      readln(c);      if a = 0 then {rovnice není kvadratická?}               if b = 0 then {rovnice není ani lineární? -> je konstantní}            if c = 0 then writeln('Rovnice ma nekonecne mnoho reseni. Kazde komplexni cislo x je resenim.')                     {rovnice je konstantní, ale řešení neexistuje}                     else writeln('Rovnice nema zadne reseni.')                  {rovnice je lineární, řešením je -c/b}                  else writeln('Resenim teto rovnice je ', -c/b:8:3)               {rovnice je kvadratická}               else begin                    D := sqr(b) - 4*a*c;                                        {je diskriminant < 0?}                    if D < 0 then begin                       {ano, počítáme dva komplexně sdružené kořeny}                       x1re := -b/2/a;                       x2re := -b/2/a;                       x1im := sqrt(-D)/2/a;                       x2im := -sqrt(-D)/2/a;                       writeln('Rovnice ma dve komplexne sdruzena reseni ');                       writeln('(',x1re:8:3,', ',x1im:8:3,') a (',x2re:8:3,', ',x2im:8:3,')')                    end                    {ne, testujeme, zda D=0}                    else if D = 0 then writeln('Rovnice ma jeden dvojnasobny koren ', -b/2/a:8:3)                                  else begin                                                                        {ne, rovnice má dva různé reálné kořeny}                                       x1 := (-b + sqrt(D))/2/a;                                       x2 := (-b - sqrt(D))/2/a;                                       writeln('Rovnice ma dva realne koreny ',x1:8:3, ' a ',x2:8:3)                                  end               end end.

5. Podprogramy ··· Procedury a funkce

Poznáme, že ve složitějších programech se často stává, že se některé části kódu vyskytují v programu na více místech. Takové části můžeme vyčlenit do tzv. podprogramu a ten opakovaně použít. Naučíme se vybírat vhodné části k vyčlenění.

5.1. Vyčlenění vícekrát se vyskytujících částí programu do podprogramu

Na již hotovém programu si ukážeme, jak je možné vyčlenění relativně ucelených a samostatných částí do podprogramů - procedur.

5.1.1. Když je kód moc složitý, je třeba jej členit

Složitá úloha se skládá z několika jednodušších
V posledním příkladu předchozí sekce jsme řešili rovnici ax2 + bx + c = 0. Při výpočtu kořenů takové rovnice je třeba oetřit celou řadu různých situací, které v důsledku vedou k odlišným algoritmům. Je-li například a = 0, rovnice vůbec není kvadratická, je potřeba ji řešit jako lineární. A koneckonců ani lineární rovnice bx + c = 0 vlastně lineární rovnicí v pravém slova smyslu být nemusí - může totiž nastat případ b = 0 a rovnice se zredukuje na konstantní rovnici c = 0.

Jak vidět, i v relativně jednoduché úloze, jakou je tato, řešíme de-facto několik různých dílčích úloh. Hlavní program se pak vlastně změní na jakéhosi "distributora", který podle konkrétního typu problému (typu rovnice) "zadává řešení" dílčích úloh jiným algoritmům (v ukázkovém případě algoritmům pro kvadratickou, lineární a konstantní rovnici).

Vyčlenění dílčích úloh/algoritmů
Nebylo by vhodné vyčlenit tyto dílčí algoritmy do speciálních "algoritmických modulů", které by řešily vždy jen tu dílčí úlohu? Takové "algoritmické moduly" mohou nabýt podoby tzv. podprogramů. Podprogram je určitá vymezená část programového kódu (posloupnost příkazů), která řeší nějakou definovanou dílčí úlohu, např.

• "Spočti řešení rovnice bx + c = 0, když b <> 0."
• "Spočti řešení rovnice c = 0."
• "Smaž obrazovku a vypiš úvodní 'uvítání' do programu."
• "Vypiš výsledek řešení rovnice ax2 + bx + c = 0."

Podprogramy v Pascalu
Pascal a stejně tak většina ostatních programovacích jazyků má možnost podprogramy konstruovat. V Pascalu mohou být podprogramy realizovány jako

• procedury (procedure) nebo
• funkce (function).

5.1.2. Procedury a funkce v Pascalu

Kvadratická rovnice řešená podprogramy
Nejlépe se učí na příkladech, proto bez dlouhého teoretizování ukažme na již známém problému - řešení kvadratické rovnice - jak se podprogramy konstruují.

33.

Kvadraticka rovnice (KvadrRovSProcedurami.pas)

program KvadrRovSProcedurami; var a, b, c: real;     D, x1, x2 : real;     x1re, x2re, x1im, x2im : real; {procedura na spočtení řešení konstantní rovnice c=0} procedure KonstantniRovnice(c: real); begin      if c = 0         then writeln('Rovnice ma nekonecne mnoho reseni. Kazde komplexni cislo je resenim.')         else writeln('Rovnice nema zadne reseni.') end; {procedura na spočtení řešení lineární rovnice bx+c=0} procedure LinearniRovnice(b, c: real); begin      {není rovnice jen konstantní?}      if b = 0         then KonstantniRovnice(c)         {ne, je opravdu lineární}         else writeln('Resenim teto rovnice je ', -c/b:8:3) end; {procedura na spočtení řešení rovnice ax2+bx+c=0} procedure KvadratickaRovnice(a, b, c: real); begin      {není rovnice jen lineární?}      if a = 0 then LinearniRovnice(b, c)               {ne, je opravdu kvadratická}               else begin                    D := sqr(b) - 4*a*c;                    if D < 0 then begin                       x1re := -b/2/a;                       x2re := -b/2/a;                       x1im := sqrt(-D)/2/a;                       x2im := -sqrt(-D)/2/a;                       writeln('Rovnice ma dve komplexne sdruzena reseni ');                       writeln('(',x1re:8:3,', ',x1im:8:3,') a (',x2re:8:3,', ',x2im:8:3,')')                    end                    else if D = 0 then writeln('Rovnice ma jeden dvojnasobny koren ', -b/2/a:8:3)                                  else begin                                       x1 := (-b + sqrt(D))/2/a;                                       x2 := (-b - sqrt(D))/2/a;                                       writeln('Rovnice ma dva realne koreny ',x1:8:3, ' a ',x2:8:3)                                  end               end end; begin      {v hlavním programu pouze uživatel zadá vstupy,       ty se předají do procedur}             writeln('Reseni rovnice ax2 + bx + c = 0 v komplexnim oboru. Cisla a,b,c jsou realna. ');      write('Zadejte koeficient a: ');      readln(a);      write('Zadejte koeficient b: ');      readln(b);      write('Zadejte koeficient c: ');      readln(c);      KvadratickaRovnice(a, b, c);            writeln('Konec programu.') end.

Zápis procedur v Pascalu
Vidíme, že samotné kódy podprogramů (konkrétně procedur) mají tvar:

procedure NazevProcedury(parametr: TypParametru);
begin
   ... příkazy procedury ...
end;

procedure KonstantniRovnice(c: real);
begin
     if c = 0 
        then writeln('Rovnice ma nekonecne mnoho reseni. Kazde komplexni cislo je resenim.')
        else writeln('Rovnice nema zadne reseni.')
end;

• klíčové slovo procedure: uvozuje tzv. hlavičku procedury;
• klíčová slova begin a end už známe, fungují podobně jako u hlavního programu - zde uvozují příkazovou část procedury, pouze za end tentokrát není tečka, ale středník (nejedná se o konec celého programu);
• příkazy procedury jsou zcela normální příkazy jako v hlavním programu, pozue umístěné v tzv. těle procedury.

Volání procedur
To, co jsme zatím u procedur diskutovali, byla tzv. deklarace procedury. Samotná deklarace však nemá na chod programu žádný vliv, nic reálného neudělá, stejně jako by nic reálného neudělal program, který by obsahoval jen deklaraci proměnné:

program NicJenDeklarace;
var i: integer;
begin
end.

procedure DesetHvezdicek;
begin
        writeln('')
end;

program Pokus;
procedure DesetHvezdicek;
begin
        writeln('')
end;
begin
     DesetHvezdicek;
end.

begin
     DesetHvezdicek;
     DesetHvezdicek;
     DesetHvezdicek;
end.

Volání procedur umíme, zbývá tedy vyřešit poslední záležitost, která se v příkladu s rovnicemi vyskytovala: co to bylo uvedeno v závorce v hlavičce procedur (např. procedure KonstantniRovnice(c: real);) a při volání procedur (např. řádek then KonstantniRovnice(c))? Stručná odpověď zní: byly to tzv. parametry procedur.

5.1.3. Parametry procedur

K čemu parametry jsou?
Jak víme, procedury jsou podprogram, tedy úseky kódu, které se jednou napíší (deklarace procedury) a lze v programu vícekrát využít (volání procedury). Parametry procedur nám navíc umožňují dodávat procedurám data potřebná pro jejich činnost.

Například v programu na kvadratickou rovnici máme proceduru LinearniRovnice, která má dva parametry: b a c, nesoucí vstupní informace nutné k vyřešení lineární rovnice bx + c = 0 - jsou to totiž právě její koeficienty b a c.

LinearniRovnice(3,6)

Resenim teto rovnice je   -2.000.

• formální parametry b a c (uvedené v hlavičce procedure LinearniRovnice(b, c: real) v deklaraci procedury)
• nahradili skutečnými parametry 3 a 6.

Jak se parametry deklarují
Formát deklarace procedury s parametry je velmi jednoduchý:

procedure NazevProcedury(parametr1: TypParametru1; parametr2: TypParametru2,...);

procedure NazevProcedury(parametr1, parametr2: TypParametru1_2);

Co takové deklarace znamenají?
Ukažme si to opět na příkladu s rovnicemi. Deklarace procedury LinearniRovnice měla tento tvar:

procedure LinearniRovnice(b, c: real);
begin
     {není rovnice jen konstantní?}
     if b = 0 
        then KonstantniRovnice(c)
        {ne, je opravdu lineární}
        else writeln('Resenim teto rovnice je ', -c/b:8:3)
end;

5.1.4. Jak se parametry používají při volání procedur

Krok 1: vyhodnocení skutečných parametrů
Nejprve se vyhodnotí skutečné parametry při volání - v našem případě jsou to čísla 3 a 6, ale mohly by to být i výrazy dávající hodnotu typu real, např. je možné volat LinearniRovnice(p + q, r/2), jsou-li p, q, r číselného typu. To, že skutečné parametry nejsou přímo typu real, ale například celočíselného typu (např. při volání (LinearniRovnice(i-j, k div 2), kde i, j, k jsou typu integer), nevadí. Počítač si je před předáním do procedury převede na příslušný typ formálního parametru (tedy v našem případě typ real).

Krok 2: předání skutečných parametrů do procedury
Proběhl-li krok 1 v pořádku, známe nyní hodnoty skutečných parametrů a tyto hodnoty můžeme předat do procedury. To se v našem případě děje tak, že do proměnných b a c (které díky tomu, že jsou formálními parametry procedury LinearniRovnice, existují uvnitř této procedury) přiřadí spočtené hodnoty skutečných parametrů. Pokud např. před voláním bude i = 5, j = 2 a k = 12 a zavoláme LinearniRovnice(i-j, k div 2), bude se volání chovat stejně, jako bychom rovnou zavolali LinearniRovnice(3,6), protože i-j = 3 a k div 2 = 6.

Krok 3: běh procedury
Nyní jsou v proměnných b a c uvnitř procedury LinearniRovnice hodnoty b = 3 a c = 6. S nimi se dále počítá. Procedura nejprve otestuje, zda b = 0 a když zjistí, že nikoli, rovnou spočte výsledek - řešení lineární rovnice. Ten činí -2 a procedura jej vzápětí vypíše.

Krok 4: návrat z procedury a pokračování v běhu hlavního programu
Jelikož vypsáním výsledku činnost procedury končí (jsme u end;), výpočet se opět vrací za místo, odkud byla procedura volána.

5.1.5. Jak je fyzicky předávání hodnotou realizováno?

Co je zásobník?
Zásobník je vyhrazená oblast paměti (paměťový segment) určená k ukládání dočasných dat, například návratové adresy při volání procedur/fcí nebo skutečných parametrů při jejich volání. Po návratu z procedury/fce je obsah zásobníku, použitý danou procedurou, uvolněn. Do zásobníku se též ukládají veškeré lokální proměnné procedury/fce.

Co se tedy stane v jednotlivých, výše uvedených, krocích v paměti?

1. Vyhodnocení skutečných parametrů - v nějaké pomocné (programátorovi neviditelné) proměnné si program vypočte hodnoty předávané do procedury.
2. Předání skutečných parametrů do procedury - spočtené předávané hodnoty jsou uloženy do zásobníku. (Vysvětlení pojmu zásobník viz dále.)
3. Vstup do procedury/fce - na zásobníku se vytvoří prostor pro lokální proměnné procedury/fce.
4. Běh procedury - příkazy v těle procedury mohou za jejího běhu přistupovat jak k lokálním proměnným, tak k parametrům předaným při volání.
5. Ukončení běhu těla a návrat - ze zásobníku je "vytažena" (angl. pop) návratová adresa a celá část obsahu zásobníku obsazená procedurou je uvolněna.

5.1.6. Parametry podruhé - předávání parametrů odkazem

Nyní se podívejme na situace, kdy je třeba zadané parametry v proceduře zpracovat a změnit jejich hodnoty tak, aby se změny projevily i navenek, tj. v prostředí, z něhož byly procedury volány.

Předávání parametrů odkazem
Představme si situaci, kdy budeme v programu často potřebovat prohazovat (vzájemně zaměňovat) obsahy dvou reálných proměnných. Pro tento účel by se výborně uplatnila procedura, které bychom předali dvě proměnné a procedura by je vrátila prohozené. S mechanizmem předávání parametrů, který jsme doposud používali, to však nejsme schopni realizovat - hodnoty proměnných se sice při volání dostanou dovnitř těla procedury do příslušných lokálních proměnných (představovaných parametry procedury), kde je můžeme prohodit. Jejich prohození se ovšem navenek nijak neprojeví - prohozené hodnoty zůstanou jen v lokálních proměnných procedury. Po dokončení a opuštění procedury tyto hodnoty nenávratně zmizí - byly totiž dočasně uloženy na tzv. zásobníku. Pro objasnění pojmu lokální proměnná viz #locvar (srovnání globální a lokální proměnná).

Řešením je předávat parametry do "prohazovací" procedury nikoli jako dosud hodnotou, ale odkazem.

Předávání parametrů odkazem funguje tak, že při volání procedury jsou její skutečné parametry ztotožněny s formálními a tudíž všude, kde se v těle procedury používají formální parametry, se ve skutečnosti pracuje s parametry skutečnými. Jelikož v těle procedury se do formálních parametrů může i zapisovat (tj. přiřazovat), je nutné, aby skutečnými parametry byly také proměnné - ne jen libovolné hodnoty (výrazy) daného typu. Ukažme to na příkladu.

Následující program obsahuje proceduru Prohod, která dostane jako skutečné parametry názvy dvou reálných proměnných, jejichž obsahy s pomocí další proměnné vzájemně zamění. Výsledkem volání je tedy prohození obsahu zadaných proměnných.

34.

Prohození čísel (ProhozeniCisel.pas)

program ProhozeniCisel; var a, b: real; {procedura na prohozeni obsahu dvou promennych} procedure Prohod(var x: real, var y: real); var pom: real; begin      pom := x;      x := y;      y := pom; end; {procedura vypis dvou realnych cisel} procedure Vypis(x, y: real); begin      writeln('(', x, ', ', y, ')'); end; begin      {v hlavnim programu uzivatel zada dve realna cisla       do promennych a, b.       Procedura Prohod pak pracuje primo s temito promennymi.}             writeln('Zkouska prohozeni dvou cisel v procedure. ');      write('Zadejte prvni cislo: ');      readln(a);      write('Zadejte druhe cislo: ');      readln(b);      writeln('Bylo zadano:');      Vypis(a, b);            writeln('Nyni cisla prohodime:');      Prohod(a, b);      Vypis(a, b);      writeln('Konec programu.') end.

Krok 1: předání odkazu na skutečné parametry
Skutečnými parametry při volání procedury Prohod jsou v našem případě globální proměnné a a b, které musejí být přesně stejného (identického) typu jako formální parametry. Nelze tedy naši prohazovací proceduru zavolat např. na dvě celé čísla integer. Volání funguje tak, že do procedury se předají odkazy na proměnné a a b tak, aby se všude tam, kde se v těle procedury vyskytuje x pracovalo přímo s proměnnou a a analogicky - tam, kde je uvedeno y aby se pracovalo s b.

Krok 2: běh procedury
Nyní se uvnitř procedury pracuje přímo s a a b. Obsahy těchto dvou proměnných jsou za pomoci třetí proměnné z prohozeny.

Krok 3: návrat z procedury a pokračování v běhu hlavního programu
Jakmile tělo procedury doběhne na konec, výpočet se opět vrací za místo, odkud byla procedura volána. Jak se přesvědčíme na výpisu, hodnoty v proměnných a a b byly skutečně zaměněny. Procedura funguje. Pro srovnání je ve výše uvedeném programu i procedura, jejíž parametry jsou předávány hodnotou - procedura Vypis. Zde totiž nepotřebujeme uvnitř procedury měnit stav skutečných parametrů, takže stačí předat dovnitř hodnoty.

Naprosto stejně to funguje, jsou-li odkazem předávány skutečné parametry funkcím. Není to však typické, protože u funkcí máme standardní mechanizmus, jak vracet výsledek - přímo její návratovou hodnotou, což u procedury možné není.

Hodnotu nebo odkazem?

• Stačí-li nám "jednosměrná komunikace", tj. předání hodnot do procedury/fce, pak použijeme předávání hodnotou, protože pak mohou jako skutečné parametry vystupovat i výrazy, nejen proměnné. Např. proceduru Vypis můžeme díky tomu zavolat takto:

 vypis(1+2+3, 10)

 (6, 10)

• Potřebujeme-li během procedury/fce ovlivnit i vnější prostředí, konkrétně hodnoty proměnných uvedených jako skutečné parametry, nezbývá než předat je odkazem, jak tomu bylo např. u prohazování obsahu proměnných.

35.

Přičtení hodnoty k číslu (Pricteni.pas)

program Pricteni; var a, b: real; {procedura na pricteni hodnoty k obsahu realne promenne} {prvni parametr predavan odkazem, druhy hodnotou} procedure Pricti(var x: real; y: real); begin      x := x + y; end; {procedura vypis dvou realnych cisel} procedure Vypis(x, y: real); begin      writeln('(', x, ', ', y, ')'); end; begin      {v hlavnim programu uzivatel zada realne cislo       do promenne a.       Procedura Pricti pak k teto promenne pricte hodnotu výrazu 1+2.}             writeln('Kombinace predavani odkazem/hodnotou. ');      write('Zadejte cislo: ');      readln(a);      writeln('Bylo zadano:')      Vypis(a, b);            writeln('Nyni k cislu pricteme 1+2:');      Pricti(a, 1+2);      Vypis(a, b);      writeln('Konec programu.') end.

5.1.7. Proměnné v hlavním programu a procedurách?

Formální parametry procedur jsou vlastně proměnné, jejichž hodnota je naplněna při vstupu do procedury a rámci procedury se s nimi pracuje, jako s běžnými proměnnými.

Globální a lokální proměnné

• Globální proměnnou v Pascalu rozumíme proměnnou hlavního programu. Taková proměnná je přístupná jak v příkazové části hlavního programu, tak v tělech všech procedur a funkcí - prostě všude.
• Lokální proměnnými procedury/fce nazýváme proměnné deklarované v deklaračním bloku dané procedury/fce. Tyto proměnné jsou přístupné pouze z těla příslušné procedury/fce a z těl procedur/funkcí do ní vnořených.

Na závěr si ukažme, jak skutečně překrývání viditelnosti proměnných v blocích funguje.

36.

Překrytí proměnné z nadřazeného bloku (Prekryti.pas)

program Prekryti; var a, b: real; procedure Prekryj; var a, b: real; begin      {zapisujeme nyni do LOKALNICH promennych a, b}      a := 10;      b := 20;            {vypise se 10 20}      writeln('V procedure Prekryj: ', a, b); end; begin      {v hlavnim programu nastavime hodnoty       GLOBALNICH promennych a, b}      a := 1;      b := 2;            {vypise 1,2}      writeln('V hlavnim pg.', a, b);      Prekryj;            {opet vypise 1,2}      writeln('Opet v hlavnim pg.', a, b); end.

5.2. Jak psát procedury a funkce

5.2.1. Kdy použít proceduru a kdy funkci?

1. Typicky sestavujeme funkci tehdy, potřebujeme-li podprogram, který nám bude opakovaně sloužit k výpočtu jedné hodnoty z jednoho či více vstupů. Například nejrůznější matematické výpočtu mají tuto povahu - na výstupu chceme jednu hodnotu (např. sin(x), cos(x), abs(x)).

1. Tam, kde podprogram musí vracet složenou hodnotu (pole, záznam...), funkce je nepoužitelná - je třeba formulovat jako proceduru.

5.2.2. Volba parametrů procedur a způsob jejich předávání ··· Kdy hodnotou, kdy odkazem?

Kdy předáváme parametry hodnotou?

• Jednoznačně tehdy, jsou-li to parametry výlučně vstupní, tzn. do funkce či procedury se předají

• Funkce mají velmi často pouze parametry volané hodnotou, protože z abstraktního matematického hlediska je funkce vlastně určitá "černá skříňka", do níž zadáme vstupy a "vypadne" nám výstup. Napředpokládá se u nich, že by modifikovaly hodnoty proměnných zadaných jako skutečné paramatry.

Kdy předáváme odkazem?

• tam, kde by funkce měla vracet složenou hodnotu (pole, záznam,...) - to nejde realizovat přímo jako vracená hodnota funkce, takže místo function lze klidně použít procedure a vracenou hodnotu realizovat ;

5.2.3. Tzv. vedlejší efekt procedur a funkcí

Metodicky bychom se vedlejším efektům měli zásadně vyhýbat, vedou jinak k těžko odhalitelným chybám - globální proměnné jsou pak často zcela nečekaně měněny a my nevíme kde a čím...

Procedura či funkce by měla modifikovat jen ty objekty (proměnné), které jsou buďto:

1. jejími parametry (uvedené v hlavičce procedury/funkce);
2. jejími lokálními proměnnými (uvedené v deklarační části procedury/funkce);
3. vracenou hodnotou (funkce).

Úloha č. 10. Může se předávání parametrů odkazem někdy hodit i v případě, že v těle procedury/fce nepotřebujeme tyto parametry modifikovat tak, aby se změny projevily navenek? Odpověď vlastními slovy zdůvodněte.

Úloha č. 11. Tento úkol jde trochu za rámec probíraného. Ilustruje totiž tzv. blokovou strukturu pascalských programů. Zkuste napsat program, který vychází z programu Prekryti.pas, ale v deklarační části (tj. mezi hlavičkou a begin procedury Prekryj je deklarována ještě další procedura PrekryjUvnitr, opět s lokálními proměnnými a, b. Do těla procedury PrekryjUvnitr dejte opět přiřazení do proměnných a i b. Pomocí výpisů ukažte, že přiřazení modifikuje právě ty proměnné a, b, nacházející se právě až v proceduře PrekryjUvnitr.

Úloha č. 12. Mějme následující program:

37.	Předávání odkazem/hodnotou (Predavani1.pas)
	program Predavani1; var a,b: integer; procedure Z(var x: integer; y: integer); var b: integer; begin    b := y;    x := x + b;    WriteLn(y,x:5);    y := x end; begin    a := 8;    b := 12;    Z(b,a);    WriteLn(b,a:4) end.

Úloha č. 13. Poslední úkol je skutečně tvůrčí. Napište program, který vypíše ze dvou zadaných celých čísel vždy to menší.

   Nacteni(a, b);
   Zpracovani(a, b);
   Vypis(a);

6. Opakované provádění úseku výpočtu ··· Cykly

Pochopíte, že ve většina složitějších výpočetních postupů se neobejde bez opakovaného, cyklického provádění určitých úseků programu, obvykle na základě platnosti určité podmínky.

Naučíte se poznávat problémy, při jejichž řešení je třeba použít cyklus.

Naučíte se sestavovat jednoduché cykly.

6.1. Sestavení jednoduchého cyklu

1. Nejdříve byla obě čísla uživatelem zadána a načtena do proměnných, řekněme m a n.
2. Poté byla proměnná nesoucí budoucí výsledek nastavena na nulu.
3. Dále, dokud m > 0, byla přičtena k výsledku hodnota n a proměnná m snížena o 1.
4. Výsledek (v proměnné vysledek) byl vypsán.

38.	Násobení pomocí sčítání (NasobeniScitanim.pas)
	program NasobeniScitanim; var n, m, pom, vysledek: integer; begin      write('Zadejte prvni cislo: ');      readln(n);      write('Zadejte druhe cislo: ');      readln(m);      vysledek := 0;      {v cyklu musíme m-krát přičíst n}      while m > 0 do begin         vysledek := vysledek + n;         dec(m);      end;      writeln('Soucin = ',vysledek); end.

Nová je zde konstrukce dovolující opakování úseku algoritmu: touto konstrukcí je příkaz cyklu while.

6.1.1. Cyklus s podmínkou na začátku

Ve výše uvedeném programu tedy: dokud je m > 0, dělej vysledek := vysledek + n a dec(m).

1. Program tedy tak dlouho přičítá k výsledku hodnotu n a za každé přičtení n sníží m o jedničku, až je m = 0.
2. Pak cyklus while skončí a pokračuje se dále vypsáním výsledku násobení.
3. Cyklus while je cyklem s podmínkou na začátku, takže pokud hned na začátku bude m >= 0, příkazy v těle cyklu se neprovedou ani jednou.
4. V Pascalu existuje i cyklus s podmínkou na konci, ten se pak chová tak, že jeho tělo (příkazy v těle cyklu) proběhnou vždy alespoň jednou a až po prvním průchodu tělem cyklu se podmínka poprvé testuje.

Následující příklad je dokonalejší verzí téhož, funguje i pro záporné číslo m, které v předchozím řešení nebylo přípustné. Kdyby totiž v předchozím m < 0, pak by příkazy v cyklu while nebyly ani jednou provedeny a ve výsledku by vždy zůstala nula.

Problém lze vyřešit tím, že:

1. si zapamatujeme, zda m bylo záporné,
2. poté z něj uděláme jeho absolutní hodnotu,
3. dále pokračujeme jako v předchozím
4. a na závěr pokud m bylo záporné, dosažený výsledek obrátím (-vysledek).

39.

Násobení pomocí sčítání - i pro záporný 2. činitel (NasobeniScitanimIZapornych.pas)

program NasobeniScitanimIZapornych; var n, m, pom, vysledek: integer;     kladne: boolean; begin      write('Zadejte prvni cislo: ');      readln(n);      write('Zadejte druhe cislo: ');      readln(m);      vysledek := 0;      {je m kladné?}      kladne := m > 0;      {každopádně vezmeme jeho absolutní hodnotu...}      m := abs(m);      {...a tolikrát přičteme n}      while m > 0 do begin         vysledek := vysledek + n;         dec(m);      end;      {když m bylo kladné, je to OK,...}      if kladne then writeln('Soucin = ',vysledek)                {...jinak výsledek obrátíme}                else writeln('Soucin = ',-vysledek) end.

V programu se nově objevilo:

1. funkce abs(), počítající absolutní hodnotu zadaného čísla;
2. proměnná kladne typu boolean,
3. trochu podivně vypadající přiřazení kladne := m > 0 a
4. na konci programu exoticky vypadající podmínka if kladna then ...

6.1.2. Logické (booleovské) proměnné

1. Ad 2: u proměnné kladne se poprvé setkáváme s tzv. logickou proměnnou, neboli v pascalské terminologii proměnnou typu boolean. Je to proměnná, která může nést logickou hodnotu, tedy jednu z hodnot true nebo false ("pravda" nebo "nepravda"). Tuto proměnnou použijeme na "zapamatování" toho, zda proměnná m byla kladná či nikoli:
2. Ad 3: bude-li m kladné číslo (tedy výsledek porovnání m > 0 je "pravda"), přiřadí se tato "pravda" (tedy booleovská hodnota true) do booleovské proměnné kladna.
3. Ad 4: na konci programu se potřebuje vrátit k informaci, zda hodnota m byla kladná. Tuto informaci máme v booleovské proměnné kladna a otestujeme ji podmínkou if kladna then ... else ...

Možná vás napadlo: jak to, že proměnnou kladna na konci programu netestujeme obdobně jako každou jinou proměnnou, s nimiž jsme se dosud setkávali, tedy takto: if kladna = true then ... else ...?

Základní znalosti o cyklech s podmínkou na začátku (while) a jejich sestavování máme. Podívejme se proto na oblast, kde se cykly velmi často používají - na práci se složenými datovými typy.

6.2. Co s nefunkčním programem? ··· Ladění programů

6.2.1. Program nefunguje?

V tomto případě jsme omylem neuvedli za end od hlavního programu tečku. Takovým chybám říkáme chyby při překladu, jsou typické pro začátečníky a způsobeny neznalostí syntaxe (gramatiky) Pascalu. Přestože někdy začátečníky pořádně potrápí, nejsou v zásadě nebezpečné. Projeví se totiž ještě před spuštěním programu a spuštění programu znemožňují.

Daleko horším oříškem jsou chyby, jež se projeví až za běhu programu, tj. po bezchybném překladu. Překladač nám s nimi nepomůže a pokud nejsme s to pouhým studiem zdrojového textu a sledováním běhu programu chybu odhalit, musíme program ladit (debug).

6.2.2. Ladíme program

Moderní interaktivní programování - kdy člověk přímo u klávesnice a monitoru počítače píše program, který vzápětí může vyzkoušet a opravit případé nedostatky - mění i přístup k ladění. Obecně se "méně promýšlí, více píše a zkouší", tento způsob testování se též označuje jako "try-and-see" ("vyzkoušej a uvidíš"). Je to na jednu stranu trend nepříznivý a "opravdovými programátory" těžce kritizovaný, na druhou stranu přirozený.

A aby to "zkoušení" bylo přece jen pohodlnější, existují nástroje, nahrazující výše zmíněné primitivní prostředky sledování běhu programu, jakými byly kontrolní tisky. Nástrojům na ladění programů se říká buďto počeštěně ladicí programy nebo tradičně debuggery.

6.3. Složené datové typy, jejich načítání a výpis

Seznámíte se s nejjednodušší (složeným) datovým typem – polem.

Naučíte se vytvářet jednoduchá (jednorozměrná) pole jednoduchých hodnot – čísel.

Naučíte se naplňovat pole hodnotami, jež zadá uživatel.

Vytvoříte si základní procedury pro práci s polem.

6.3.1. Kdy už nestačí jednoduché proměnné

Použitelnost jednoduchých proměnných má své meze
Jenže teď zvažme: jako bychom nad těmito dvanácti proměnnými počítali třeba celkovou roční tržbu? Museli bychom ji počítat jako výraz t1 + t2 + t3 + t4 + t5 + t6 + t7 + t8 + t9 +t10 + t11 + t12. Je to sice poněkud delší zápis a díky tomu v něm můžeme nadělat chyby, ale je to ještě únosné. Horší bude, když nám nebude stačit měsíční evidence a budeme chtít evidenci denních tržeb... Výraz na spočtení součtu těchto třistapětašedesáti jednoduchých proměnných nechci vidět! Navíc i kdybychom jej nakonec nějak realizovali - problém je obecnější: co když budeme pracovat s údaji, jejichž počet prostě pro danou úlohu nelze předem přesně stanovit? Pak je nutné použít proměnné, do nichž lze ukládat více než jednu hodnotu - tzv. složené proměnné.

Nejjednodušším příkladem složené proměnné (proměnné složeného datového typu) je tzv. pole (v Pascalu a v angličtině array). Pole je přirozeným rozšířením jedné proměnné na jistou konečnou posloupnost (uspořádaný seznam, vektor) n takových proměnných.

1. Co bude (jakého typu bude) "základní" proměnná bude?
2. Jak má být pole velké, tj. kolik "základních" proměnných se "do něj má vejít"?

Dejme tomu, že budeme chtít evidovat již zmíněné denní tržby po celý rok. Odpověď na otázku číslo 1 (jaký typ bude mít základní proměnná, tedy hodnota tržby za jeden den) je jasná: typ real by měl vyhovět. Otázka č. 2 (kolik základních proměnných v poli potřebujeme) je také jasná: tolik, aby tam měly místo tržby za každý den v roce, těchto dnů je max. 366. Program tedy bude vypadat takto:

40.

Načítání a výpis denních tržeb za rok (NacitaniVypisPole.pas)

program NacitaniVypisPole; var n, i: integer;     trzby: array[1..366] of real; begin    write('Pocet dni, pro nez budeme zadavat trzbu: ');    readln(n);    for i := 1 to n do begin       write('Zadej trzbu ve dni ',i,'.: ');       readln(trzby[i]);    end;    writeln('Do pole dennich trzeb jsme zadali tyto hodnoty: ');    for i := 1 to n do       writeln(i,'. den byla trzba ',trzby[i],' Kc'); end.

1. zeptal se na celkový počet načítaných tržeb;
2. postupně se zeptal a načetl hodnotu každé tržby;
3. načtené hodnoty vypsal.

6.3.2. Práce s polem

Deklarace pole
Jak jsme zde s polem vlastně pracovali?

1. nejdříve bylo třeba je deklarovat. Obecný tvar deklarace jednorozměrného pole je: var jmenoPole: array [dolniMezIndexu..horniMezIndexu] of ZakladniTyp
2. po deklaraci je možné s polem pracovat. Na jednotlivé prvky - složky - pole se přistupuje prostřednictvím indexu této složky. Index je uveden v hranaté závorce za identifikátorem proměnné typu pole a představuje vlastně něco jako pořadové číslo složky v poli. První složka (prvek) v poli však nemusí mít index 1 - meze indexů v poli lze stanovit podle potřeby, klidně můžeme deklarovat pole takto: var mojePole: array [-10..1] of integer. Takové pole bude mít celkem 12 prvků typu integer, indexovaných od -10 do 1. Jedinou podmínkou je, aby dolní mez indexů nebyla větší než mez horní - pole by pak nemělo žádné prvky. Indexovat také nelze reálnými (necelými) čísly.

Indexování prvků pole
Obecně lze ovšem indexovat i jinými než číselnými hodnotami, např. hodnotami nám známého typu boolean. Můžeme tedy napsat: var pole: array[false..true] of real a je to v pořádku. Pole pole má dva prvky: pole[false] a pole[true]. Platí však, že indexovat lze výhradně tzv. ordinálními datovými typy. Ve stručné referenční příručce Pascalu se o ordinálních typech dozvíte více (viz #ref_ord). Samozřejmě je také logické, že dolní a horní mez indexu by měla být stejného typu, asi dost divně by působilo něco jako: var m: array[false..5] of real;

Cyklus s předem známým počtem opakování: for
V programu se také poprvé objevil další z pascalských příkazů cyklu - for (viz referenční příručka #ref_for). Tento velmi používaný cyklus fungoval v předchozím programu takto (for i := 1 to n do ... znamená otrocky přeloženo: pro i je od 1 do n dělej ...):

1. nejdříve se do proměnné i (zvané též řídicí proměnná cyklu) přiřadí úvodní hodnota (dolní mez cyklu), tj. číslo 1;
2. poté je poprvé provedeno tělo cyklu (výpis hlášky a načtení prvku do pole);
3. proměnná i je zvýšena o 1, vracíme se na začátek cyklu;
4. není už i větší než je horní mez cyklu, tj. n?
5. pokud ano, končíme s cyklem, jinak znovu provedeme tělo cyklu (krok 2).

Cyklus for tedy postupně zvyšuje hodnotu řídicí proměnné a pro každou její hodnotu mezi dolní a horní mezí provede tělo cyklu. for cyklus je pro načítání prvků do polí, známe-li před započetím načítání jejich počet, velmi vhodným cyklem.

Pro cykly, které mohou skončit "nečekaně", např. zadáním nekladného čísla jako v předchozích příkladech, se ale for vůbec nedá použít!!!

6.3.3. Práce s polem v proceduře

41.

Načítání a výpis polí pomocí procedur (NacitaniVypisPoleProcedurou.pas)

program NacitaniVypisPoleProcedurou; {definujeme typ pole reálných čísel o 10 prvcích} type pole = array[1..10] of real; {deklarujeme proměnnou a typu pole reálných čísel o 10 prvcích} var a, b: pole;     prvku_a, prvku_b: integer; {procedura na načtení pole reálných čísel o max. 10 prvcích} {procedura v proměnné pocet_prvku vrátí  skutečný počet načtených prvků} procedure NactiPole(var p: pole; var pocet_prvku: integer); var i: integer; begin    write('Pocet prvku, ktere zadame do pole: ');    readln(pocet_prvku);    for i := 1 to pocet_prvku do begin       write('Zadej prvek ',i,'.: ');       readln(p[i]);    end; end; {procedura na výpis pole reálných čísel o max. 10 prvcích} procedure VypisPole(var q: pole; pocet_prvku: integer); var i: integer; begin    writeln('V poli jsou tyto prvky: ');    for i := 1 to pocet_prvku do writeln(q[i],' ');    writeln end; begin    {načteme do pole a}    NactiPole(a, prvku_a);    writeln('Do pole "a" se nacetlo ', prvku_a, 'prvku');    {vypíšeme z pole a}    VypisPole(a, prvku_a);    {načteme do pole b}    NactiPole(b, prvku_b);    writeln('Do pole "b" se nacetlo ', prvku_b, 'prvku');    {vypíšeme z pole b}    VypisPole(b, prvku_b); end.

V prvním příkladu s procedurou (Kvadratická rovnice, #subs_kvad) jsme používali parametry procedury jako mechanismus pro předání určitých údajů (hodnot) dovnitř procedury. Nejdříve byly spočteny hodnoty parametrů a tyto hodnoty předány do příslušných proměnných - parametrů. Nyní potřebujeme opačné předání - procedura uvnitř zjistí od uživatele rozsah načítaného pole a tento rozsah musí vrátit z procedury zpět do hlavního programu. Stejně tak musí samozřejmě vrátit i to nejdůležitější, o co nám jde, tj. obsah celého načítaného pole a nebo b.

To vše zajistíme novým mechanismem předávání parametrů, tzv. voláním (předáváním) odkazem (referencí).

Parametry předávané odkazem
V příkladu vidíme, že hlavička obou procedur obsahuje klíčová slova var před jmény proměnných pole a počtu prvků pole. Toto klíčové slovo zajistí následující chování procedury:

1. Při volání procedury se v těle procedury bude pracovat namísto s formálními parametry přímo se skutečnými parametry, tedy v prvním případě s polem a a proměnnou pocet_a.
2. Cokoli se v rámci procedury "stane" s polem (formálním parametrem) p - například do něj příkazem readln načteme hodnotu - změna se odehrává přímo v poli - skutečném parametru. Tedy v prvním případě v poli a.
3. Tím pádem procedura jakoby "vrací" určitý výsledek (změněné pole a), ve skutečnosti však přímo s tímto polem a pracuje!!!

Toto je naprosto zásadní poznatek o procedurách vůbec!

6.4. Jak něco vyhledat ··· aneb bez cyklů to nepůjde

Cykly nacházejí časté využití tam, kde "hledáme, dokud to nenajdeme". Poznáme typické problémy, kde se vyhledávání vyskytuje.

6.4.1. Vyhledávání, kde musíme prohledat vše...

Poznáte, že u některých problémů musíme k nalezení výsledku prohlédnout celou strukturu (např. pole).

Naučíme se volit a sestavovat v těchto případech adekvátní typy cyklů.

Vyhledávání prvku s minimální/maximální hodnotou
Velmi často se opakujícím klišé v programech všeho druhu je vyhledávání největšího nebo nejmenšího prvku z nějaké konečné posloupnosti. Ať už hledáme člověka největším platem, auto s nejnižší spotřebou nebo nejbližší město, ten nejjednodušší, velmi intuitivní algoritmus je v podstatě stejný (uveďme např. pro hledání největšího prvku):

1. vezmi prvek,
2. je tento prvek větší než dosud nalezené maximum?
3. pokud ano, stane se novým maximem
4. zbývají ještě nějaké prvky?
5. pokud ano, vracíme se na 1., jinak končíme s tím, že dosud nalezené maximum se stává maximem "definitivním".

42.

Maximum z posloupnosti - s předem zadaným počtem prvků (while) (VyberMaxima.pas)

program VyberMaxima; var n, x, max: integer; begin      writeln('Vyber maxima z poslupnosti');      write('Zadejte pocet cisel: ');      readln(n);      {je těch čísel více než nula?}      if n > 0 then begin           {ano, zadáme první}           write('Zadejte cislo: ');           readln(max);                      {je těch čísel více než jedno?}           while n > 1 do begin                dec(n);                                {ano, zadáváme další}                write('Zadejte cislo: ');                readln(x);                                {bylo větší než dosavadní maximum?}                if x > max then max := x; {ano, stane se samo maximem}           end;           writeln('Maximum z posloupnosti je ',max);      end else           writeln('Posloupnost byla prazdna'); end.

43.

Maximum z vzdáleností sousedních měst (VyberMaximalniVzdalenosti.pas)

program VyberMaximalniVzdalenosti; var x, pred, max: integer; begin      max := 0;      write('Zadejte vzdalenost mesta od pocatku cesty: ');      readln(x);      while x > 0 do begin           {nynější aktuální město se stane předchozím}           pred := x;           {zadáme další město}           write('Zadejte vzdalenost mesta od pocatku cesty: ');           readln(x);           {byla vzdálenost větší než dosavadní maximální?}           if x - pred > max then max := x - pred;                 {ano, město mělo doposud maximální vzdálenost}      end;      if max > 0         then writeln('Nejvetsi vzdalenost mezi sousednimi mesty je ',max)         else writeln('Nebyla zadana alespon dve mesta'); end.

1. nepamatovali jsme si přímo souřadnici města, ale její rozdíl oproti předchozí (tj. vzdálenost mezi sousedními městy) a
2. neznali jsme předem počet měst, takže jsme museli testovat (while x > 0), zda-li uživatel nezadal "ukončovací" nekladné číslo.

Na závěr sekce uveďme ještě variaci na předposlední téma - nalezení maxima v posloupnosti čísel, tentokrát pro případ, že před započetím načítání posloupnosti neznáme, kolik bude mít celkem prvků. Posloupnost bude opět ukončená zadáním nekladného čísla.

44.

Maximum z posloupnosti - nevíme předem počet prvků (MaximumZPosloupnosti.pas)

program MaximumZPosloupnosti; var max, x: integer; begin      writeln('Hledani nejvetsiho cisla v posloupnosti');      writeln('Zadavani ukoncete nekladnym cislem!');      {uživatel zadá první číslo}      write('Zadejte cislo: ');      readln(x);      {maximum nastavíme zatím na toto první číslo}      max := x;      {dokud uživatel neukončí zadávání vstupem nuly}      while x > 0 do begin            {zadal větší číslo než je momentální maximum?}            if max < x then max := x;            {a zadává znovu číslo...}            write('Zadejte cislo: ');            readln(x)      end;      writeln('Nejvetsi cislo v posloupnosti bylo ', max) end.

Tolik k vyhledávání extrémních prvků v posloupnosti. Uvedené algoritmy měly jedno společného: v každém případě musely prohledat celou posloupnost, než dokázaly odpovědět, ketrý prvkem je nejmenší/největší. Existují i efektivnější algoritmy vyhledávání maxima/minima, ty ale vyžadují použití jiných datových struktur než polí - např. tzv. haldy, nebo požadují, aby pole bylo před vyhledáváním uspořádáno - pak totiž stačí nejmenší nebo největší prvek přímo vzít ze začátku nebo konce pole.

6.4.2. Vyhledávání, kde můžeme přestat, jakmile něco najdeme

Naučíte se zjišťovat, zda se v poli vyskytuje určitý prvek (a kde se vyskytuje).

Vyhledávání prvního výskytu čísla v posloupnosti čísel
Úkolem následujícího programu je najít v předem zadané posloupnosti první výskyt zadaného prvku. Po nalezení tohoto prvního výskytu můžeme tedy s prohledáváním skončit.

45.

Vyhledávání výskytu prvku v poli (Hledani.pas)

program Hledani; var n, i, x: integer;     a: array[1..100] of integer; begin      writeln('Hledani cisla v posloupnosti');      {zadáme počet čísel}      write('Zadejte pocet cisel: ');      readln(n);      {zadáme čísla}      for i := 1 to n do begin          write('Zadej cislo: ');          readln(a[i])      end;      {zadáme hledané číslo}      write('Zadej hledane cislo: ');      readln(x);      {v cyklu testujeme, zda prvek posloupnosti je roven hledanému číslu}      i := 1;      while (i <= n) and (a[i] <> x) do inc(i);      {našli jsme hledané číslo?}      if a[i] = x then {ano}         writeln('Cislo ', x, ' je v posloupnosti poprve na ',i,'. miste')      else {ne}         writeln('Cislo ', x, ' se v posloupnosti nenachazi') end.

Program využívá dalšího logického operátoru and - celá složená podmínka platí tehdy, platí-li obě její podčásti: tedy je-li zároveň i <= n (nejsme na konci pole) a a[i] <> x (nenašli jsme hledaný prvek). Platí-li složená podmínka, pokračujeme v prohledávání dále.

6.4.3. Vylepšení: vyhledávání se zarážkou

Poznáte, že efektivita vyhledávání závisí i na sestavení podmínky prohledávacího cyklu.

Naučíte se často užívaný postup, jak vyhledávací podmínku zjednodušit.

46.

Vyhledávání se zarážkou (HledaniSeZarazkou.pas)

program HledaniSeZarazkou; var n, i, x: integer;     a: array[1..100] of integer; begin      writeln('Hledani vyskytu cisla v posloupnosti');      {zadáme počet čísel}      write('Zadejte pocet cisel: ');      readln(n);      {zadáme čísla}      for i := 1 to n do begin          write('Zadej cislo: ');          readln(a[i])      end;      {zadáme hledané číslo}      write('Zadej hledane cislo: ');      readln(x);      a[n+1] := x;      {v cyklu testujeme, zda prvek posloupnosti je roven hledanému číslu}      i := 1;      while a[i] <> x do inc(i);      {našli jsme hledané číslo nebo až zarážku?}      if i <= n then {našli jsme číslo}         writeln('Cislo ', x, ' je v posloupnosti poprve na ',i,'. miste')      else {našli jsme zarážku}         writeln('Cislo ', x, ' se v posloupnosti nenachazi') end.

Této "fintě" se říká zarážka.

6.4.4. Vyhledávání v uspořádané posloupnosti

Poznáte, že je-li prohledávaná posloupnost uspořádaná, může to "revolučně" zlepšit efektivitu vyhledávání.

Naučíte se v uspořádané posloupnosti (poli) efektivně vyhledávat.

Nedokážeme ovšem nalézt algoritmus, který by právě uspořádanosti dokázal nějak využít? Podíváme-li se na vyhledávání v uspořádané posloupnosti "selským rozumem", napadne nás asi, jestli by nebylo efektivní nejdříve "zkusit" hledaný prvek najít někde "uprostřed" posloupnosti. Většinou se samozřejmě prvním odhadem na umístění hledaného prvku "netrefíme", ale vždy alespoň zjistíme, jak velký je prvek, na nějž jsme se právě dostali.

1. buďto byl prvek, na nějž jsme uprostřed narazili, menší, než hledaný prvek - pak využijeme toho, že posloupnost je uspořádaná (řekněme vzestupně) - a další odhad směřujeme do "horní poloviny" posloupnosti: tam jsou totiž všechny prvky větší než .
2. nebo byl prvek, na nějž se narazilo, větší než hledaný - a pak analogicky hledáme jen od tohoto prvku níže - protože tam jsou všechny prvky menší než ten, na nějž se narazilo.

Každopádně testování prvního prvku v uspořádané posloupnosti představuje výrazné zúžení prostoru pro další vyhledávání: nadále totiž prohledáváme buďto jen horní, nebo jen spodní polovinu posloupnosti. Dále postupujeme analogicky: na vybranou poloviny výchozí posloupnosti se díváme jako na posloupnost (teď už kratší), v níž stejným způsobem znovu vyhledáváme.

Podívejme se na krátkou ilustraci postupného zužování (vlastně je to půlení) prohledávaného prostoru:

1. výchozí posl.: 1 6 10 11 12 20 25 30 42 100 150, vyhledáváme v ní prvek 30
2. v prvním kroku testujeme prvek ve středu posloupnosti, tedy 20. Hledaný prvek 30 > 20, takže vyhledávání nekončí, ale v dalším kroku se zaměříme jen na podposloupnost 1 6 10 11 12 20 25 30 42 100 150 (dvacítku jsme do nově prohledávané části již nezahrnovali, byla testována právě teď).
3. středem vybrané podposloupnosti je nyní 42, nyní platí 30 < 42, takže teď jdeme do "dolní" poloviny: 1 6 10 11 12 20 25 30 42 100 150;
4. vybraná podposloupnost už má nyní jen dva prvky, čili nemá střed a hledané číslo buďto jedním z těchto dvou prvků anebo se v posloupnosti vůbec nenachází. Každopádně už nemá smysl dělat další půlení prohledávaného prostoru.

Právě podle hlavní podstaty algoritmu - půlení prohledávaného prostoru - se výše nastíněnému algoritmu říká hledání půlením intervalu nebo binární vyhledávání.

Takhle jde toto vyhledávání vyřešit v Pascalu:

47.

Binární vyhledávání (BinarniVyhledavani.pas)

program BinarniVyhledavani; uses crt; const maxprvku = 10; var n, pom, x, limit, j, low, high, mid: integer;     a: array[1..maxprvku] of integer; begin      {zeptáme se na počet čísel}      write('Zadejte pocet cisel: ');      readln(n);      {zadáme výše zadaný počet čísel}      for limit := 1 to n do begin          write('Zadejte cislo: ');          readln(a[limit]);      end;      {čísla uspořádáme pomocí "bubble-sortu"}      for limit := n-1 downto 1 do          for j := 1 to limit do              if a[j] > a[j+1] then begin                 pom := a[j];                 a[j] := a[j+1];                 a[j+1] := pom              end;      {a jdeme na vlastní vyhledávání...}      repeat           write('Zadejte hledane cislo: ');           readln(x);           {počáteční nastavení mezí prohledávané části pole}           low := 0; high := n+1;           {dokud je kde vyhledávat - tj. oblast je neprázdná}           while low < high - 1 do begin                                  {nastav na střed oblasti}                 mid := (low + high) div 2;                                  {je střední prvek přímo ten hledaný?}                 if a[mid] = x then low := high+1 {ano, pak nastav tak, aby se skončilo}                  {ne, pak testuj, je-li menší}                               else if a[mid] < x then low := mid {ano, pak hledej nadále výše}                                                  else high := mid {ne, pak hledej nadále níže}           end;                      {testuj, proč jsme v předchozím cyklu skončili}           if low = high + 1 then writeln('Cislo ',x,' v posloupnosti je na pozici ',mid)                             else writeln('Cislo ',x,' v posloupnosti neni.');           writeln('Pro ukonceni stisknete ''k'', jinak cokoli pro pokracovani.');      until readkey = 'k';            {ještě vypiš celou posloupnost}      for limit := 1 to n do begin          write(a[limit], ' ');      end; end.

Na programu by nemělo nic překvapit. V jeho první části, po načtení posloupnosti hodnot, vidíme dva for cykly - ty realizují právě uspořádání zadané poslupnosti, abychom měli záruku, že následné vyhledávání prvků bude korektní.

Nový je také třetí a poslední typ cyklu, který je v Pascalu k dispozici. Je jím cyklus repeat - until, neboli cyklus s podmínkou na konci. V programu nám posloužil pro opakované zadávání a vyhledávání čísla. Tento typ cyklu funguje tak, že:

1. do těla cyklu se vstoupí bez ohledu na jakoukoli podmínku,
2. provede se tělo cyklu,
3. otestuje se podmínka na konci (tzv. ukončovací podmínka) - pokud platí, cyklus skončí a pokračuje se příkazem následujícím za until.
4. pokud ukončovací podmínka neplatila, přejde se opět zpět za repeat a tělo probíhá znovu.

Cyklus s podmínkou na konci (repeat - until) vždy alespoň jednou proběhne, v našem případě jsme se tedy alespoň jednou zeptali na hledané číslo a toto se pokusili vyhledat.

V našem programu právě takový cyklus vyhovoval, protože nám šlo přece o to, zadat číslo, toto se pokusit vyhledat a pak teprve se uživatele zeptat, zda pokračovat dále. Pokud uživatel chtěl ukončit, stiskl klávesu k. Jinak se program vrátil opět na načítání nového hledaného čísla.

V samotném vyhledávání (začíná od repeat) si všimněme nastavení horní meze prohledávané posloupnosti na n+1, přestože v posloupnosti bylo jen n prvků. Důvod je jednoduchý - toto nastavení nám zajistí nalezení hledaného prvku i v případě, že se nachází až na poslední, n-té pozici v poli.

6.5. Ale který cyklus použít a jak?

Poznáte, že "while" cyklus je sice univerzální, ale občas je dobré místo něj použít "for" nebo i "repeat".

Dokážete nadále rozpoznat, kdy se který cyklus hodí a kdy je naopak vyloučen.

Naučíte se dodržovat hlavní zásady při sestavování cyklů

6.5.1. Výběr vhodného typu cyklu (while?, repeat?, for?)

1. Začali jsme cyklem s podmínkou na začátku: while, který se uplatnil všude tam, kde se mohlo stát, že tělo cyklu nebude ani jednou realizováno díky nesplnění "pokračovací" podmínky cyklu. Cyklus while je díky tomu ze všech typů cyklů v Pascalu nejuniverzálnější a také v pascalských programech pravděpodobně nejpoužívanějším typem cyklu.
2. Dále jsme viděli cykly s předem známým počtem opakování: for, které se nabízely k použití tam, kde jsme před vstupem do cyklu dokázali říci, kolikrát cyklus má proběhnout. typické použití je například při načítání hodnot do proměnné typu pole - předem se uživatele zeptáme, kolik těch hodnot bude a poté jich daný počet ve for cyklu načteme.
3. Konečně naposledy, v předchozí sekci, jsme viděli cyklus s podmínkou na konci: repeat, který musí vždy proběhnou alespoň jednou. Tato vlastnost jej předurčuje k použití tam, kde se například načítá ze vstupu tak dlouho, až je načtená hodnota v pořádku (nebo dokud to uživatele baví). Každopádně v těchto případech nemá příliš smysl uvažovat o možnosti, že by cyklus ani jednou neproběhl - těžko totiž zjistíme, zda zadaný vstup je v pořádku, dokud alespoň jeden tento vstup nezadáme.

V následujících třech příkladech si ukážeme, jak (skoro) stejnou úlohu vyřešit pokaždé jiným typem cyklu. Na těchto srovnávacích příkladech je nejlépe vidět, co který typ cyklu přináší.

48.

Maximum z posloupnosti - s předem zadaným počtem prvků (while) (VyberMaxima.pas)

program VyberMaxima; var n, x, max: integer; begin      writeln('Vyber maxima z poslupnosti');      write('Zadejte pocet cisel: ');      readln(n);      {je těch čísel více než nula?}      if n > 0 then begin           {ano, zadáme první}           write('Zadejte cislo: ');           readln(max);                      {je těch čísel více než jedno?}           while n > 1 do begin                dec(n);                                {ano, zadáváme další}                write('Zadejte cislo: ');                readln(x);                                {bylo větší než dosavadní maximum?}                if x > max then max := x; {ano, stane se samo maximem}           end;           writeln('Maximum z posloupnosti je ',max);      end else           writeln('Posloupnost byla prazdna'); end.

49.

Maximum z posloupnosti - s předem zadaným počtem prvků - jiným typem cyklu (for) (VyberMaximaForCyklem.pas)

program VyberMaximaForCyklem; var n, x, max, i: integer; begin      writeln('Vyber maxima z posloupnosti');      {(skoro) každé číslo bude větší než konstanta "-maxint"}      max := -maxint;      write('Zadejte pocet cisel: ');      readln(n);      for i := 1 to n do begin          {zadáváme číslo}          write('Zadejte cislo: ');          readln(x);          {bylo větší než dosavadní maximum?}          if x > max then max := x; {ano, stane se samo maximem}      end;      if n > 0 then writeln('Maximum z posloupnosti je ',max) else writeln('Posloupnost byla prazdna'); end.

50.

Maximum z posloupnosti - s předem zadaným počtem prvků > 0 (repeat) (VyberMaximaRepeatCyklem.pas)

program VyberMaximaRepeatCyklem; var n, x, max: integer; begin      max := -maxint;      writeln('Hledani maxima posloupnosti');      {zadáme počet čísel}      write('Zadejte pocet cisel: ');      readln(n);      repeat          {zadáme další číslo}          write('Zadejte cislo: ');          readln(x);                    {bylo větší než dosavadní maximum?}          if x > max then max := x; {ano, stane se samo maximem}                    {a už zadáváme o číslo méně}          dec(n);      until n=0;      writeln('Maximum z posloupnosti je ',max); end.

Viděli jsme tedy vedle sebe všechny tři možné typy cyklů s jejich vlastnostmi.

6.5.2. Zásady při sestavování cyklů

1. minimalizovat počet opakování těla cyklu (počet tzv. průchodů cyklem);
2. maximálně zjednodušovat tělo cyklu - každá složitost a neefektivita se opakováním cyklu samozřejmě násobí!
3. maximálně zjednodušovat podmínku cyklu - vyhodnocení platnosti podmínky se děje také s každým průchodem cyklem, takže zjednodušení a zefektivnějí samotné podmínky má stejný význam jako zjednodušení uvnitř těla cyklu.

Na dvě časté oblasti optimalizace cyklů - minimalizace počtu operací prováděných v těle cyklu a zjednodušování podmínky cyklu, se podíváme v příští sekci.

6.6. Na co ještě stačí jednoduchý cyklus? ··· Příklady využití jednoduchých cyklů

6.6.1. Programy na test prvočíselnosti

Hlavní myšlenkou následujících algoritmů je postupné testování, zda zadané číslo

51.

Prvočísla naivně (Prvocisla1.pas)

program Prvocisla1; var n, i: integer; begin      write('Zadejte cislo, ktere otestujeme na prvociselnost: ');      readln(n);           if n >= 2 then begin           {testuji, zda mezi čísly 2..n není nějaký dělitel čísla n}           i := 2;           {skončím, až najdu dělitele čísla n}           while n mod i > 0 do inc(i);      {je-li n < 2, není to prvočíslo}      end else i := 0;            {když jsem s hledáním dělitele skončil dříve než u n, není n prvočíslo}      if i < n then writeln('Cislo ',n,' neni prvocislo.')            {když jsem s hledáním dělitele skončil až u n, je n prvočíslo}               else writeln('Cislo ',n,' je prvocislo.') end.

Program na test prvočíselnosti č. 2

52.

Prvočísla - dělitelnost čísly do poloviny (Prvocisla2.pas)

program Prvocisla2; var n, i: integer; begin      write('Zadejte cislo, ktere otestujeme na prvociselnost: ');      readln(n);      if n >= 2 then begin           i := 2;           {testujeme na dělitelnost čísly jen do poloviny n}           while (n mod i > 0) and (i <= n div 2) do inc(i);      end else i := n;      if n mod i = 0 then writeln('Cislo ',n,' neni prvocislo.')                     else writeln('Cislo ',n,' je prvocislo.') end.

53.

Prvočísla - dělitelnost čísly do odmocniny (Prvocisla3.pas)

program Prvocisla3; var n, i, odmoc: integer; begin      write('Zadejte cislo, ktere otestujeme na prvociselnost: ');      readln(n);      if n >= 2 then begin           odmoc := trunc(sqrt(n));           i := 2;                      {testujeme na dělitelnost jen čísla do odmocniny z n}           while (n mod i > 0) and (i <= odmoc) do inc(i);      end else i := n;      if n mod i = 0 then writeln('Cislo ',n,' neni prvocislo.')                     else writeln('Cislo ',n,' je prvocislo.') end.

Poslední varianta "prvočísel" optimalizuje ještě dálo počet průchodů cyklem - testujeme pouze dělitelnost lichými čísly. Když totiž uvážíme, že kromě dvojky jsou prvočísla lichá, stačí dvojku "ošetřit" předem a dále za potenciální prvočíslo považovat jen liché číslo. Pak stačí testovat dělitelnost jen lichými čísly.

54.

Prvočísla - dělitelnost čísly do odmocniny a jen lichými čísly (Prvocisla4.pas)

program Prvocisla4; var n, i, odmoc: integer; begin      write('Zadejte cislo, ktere otestujeme na prvociselnost: ');      readln(n);            {testujeme jen lichá čísla,       sudá kromě dvojky nejsou prvočísly}      if (n >= 2) and odd(n) then begin           odmoc := trunc(sqrt(n));           i := 3;           {testujeme na dělitelnost jen čísla do odmocniny z n            a to ještě jenom lichá}           while (n mod i > 0) and (i <= odmoc) do inc(i,2);      end else i := n;      if n mod i = 0 then writeln('Cislo ',n,' neni prvocislo.')                     else writeln('Cislo ',n,' je prvocislo.') end.

6.6.2. Sledování, zda posloupnost je rostoucí

Jednou z možností je sledovat oboje: do jedné booleovské proměnné si budeme pamatovat, zda je

55.

Růst či pokles 1. (RustPokles1.pas)

program RustPokles1; var pred, x: real;     rust, pokles: boolean; begin      write('Zadejte cislo: ');      readln(x);      {zatím je posloupnost i rostoucí i klesající}      rust := true;      pokles := true;      {dokud uživatel neukončí vstup nulou}      while x <> 0 do begin            {ze současného čísla se stává předchozí}            pred := x;            {a zadáváme další}            write('Zadejte cislo: ');            readln(x);                        {není to ukončovací nula?}            if x <> 0 then begin               {ne, testujeme}               rust := rust and (pred < x); {roste posloupost stále?}               pokles := pokles and (pred > x) {klesá posloupost stále?}            end      end;      if rust then writeln('Posloupnost je rostouci.')      else if pokles then writeln('Posloupnost je klesajici.')                     else writeln('Posloupnost neni rostouci ani klesajici.') end.

56.

Růst či pokles 2. (RustPokles2.pas)

program RustPokles2; var pred, x: real;     rust, pokles, rovno, porus: integer; begin      writeln('Zadavejte prvky do posloupnosti, ukoncete nekladnym cislem');      write('Zadejte cislo: ');      readln(x);      {zatím má posloupnost nulový počet růstů a poklesů}      rust := 0;      rovno := 0;      {dokud uživatel neukončí vstup nulou}      while x <> 0 do begin            {ze současného čísla se stává předchozí}            pred := x;            {a zadáváme další}            write('Zadejte cislo: ');            readln(x);            {není to ukončovací nula?}            if x <> 0 then                 {ne, testujeme}                 if pred < x then inc(rust) {roste posloupost?}                 else if pred > x then inc(pokles) {klesá posloupost?}                                  else inc(rovno) {ani to ne, číslo je stejné}      end;      {počet porušení odpovídá zatím počtu rovností v poslp.}      porus := rovno;      {ale teď k němu přičteme ten počet růstů nebo poklesů,       který je v menšině}      if pokles > rust then           porus := porus + rust      else           porus := porus + pokles;      {je počet porušení > 0?}      if porus > 0 then           writeln('Posloupnost neni rostouci ani klesajici. Pocet poruseni je ', porus)                 {ne, posloupnost je buď rostoucí, nebo klesající}      else           if pokles > 0 then writeln('Posloupnost je klesajici.')                         else writeln('Posloupnost je rostouci.') end.

6.6.3. Vyhledávání tří největších čísel v posloupnosti

57.

Tři maxima (Maxima3.pas)

program Maxima3; var max1, max2, max3, x: real;     pocet: integer; begin      write('Zadejte cislo: ');      readln(x);      pocet := 0;      {nastavíme všechny tři maxima na první zadanou hodnotu}      max1 := x;      max2 := x;      max3 := x;      {dokud uživatel neukončí vstup - nezadá nulu}      while x <> 0 do begin            {je zadané číslo větší než největší z max1..max3?}            if x > max3 then begin               max1 := max2;               max2 := max3;               max3 := x;                     {je zadané číslo větší než druhé největší z max1..max3?}            end else if x > max2 then begin                        max1 := max2;                        max2 := x;                              {je zadané číslo větší než třetí největší z max1..max3?}                     end else if x > max1 then                                 max1 := x;            {uživatel zadává další číslo}            write('Zadejte cislo: ');            readln(x);            {zvýšíme počet již zadaných čísel}            inc(pocet)      end;            {bylo vůbec zadáno dostatek čísel?}      if pocet >= 3 then writeln('Tri nejvetsi cisla byla ', max1:8:3, ', ',max2:8:3,', ',max3:8:3)      else if pocet >= 2 then writeln('Dve nejvetsi cisla byla ', max2:8:3,', ',max3:8:3)                         else writeln('Nejvetsi cislo bylo ',max3:8:3) end.

6.6.4. Něco málo z ekonomiky...

58.

Útrata (Utrata.pas)

program Utrata; var mame, polozka, utraceno: integer; begin      write('Zadejte celkovou sumu penez: ');      readln(mame);      utraceno := 0;      polozka := 0;      {dokud máme peníze, utrácíme}      while utraceno + polozka < mame do begin           utraceno := utraceno + polozka;           {další položka (zboží)}           write('Zadejte cenu polozky: ');           readln(polozka);      end;            {utratili jsme úplně všechno?}      if utraceno + polozka = mame then utraceno := mame; {ano}            writeln('Meli jsme celkem ',mame, ' Kc, utratilo se ',utraceno, ' Kc.') end.

6.6.5. Datový typ řetězec (string)

59.

Měsíční tržby (Ucet.pas)

program Ucet; var mesicu, m, den, prev, mezera, error, error2: integer;     mesice: array[1..12] of real;     trzba, celkem: real;     vstup, vstup1, vstup2: string; begin      writeln('Zadavejte vzdy na radek: cislo_dne trzba_v_Kc');      m := 1;      celkem := 0;      prev := 0;      {načteme první řádek}      readln(vstup);            {dokud řádek není prázdný}      while vstup <> '' do begin           {najdeme v řádku mezeru}           mezera := pos(' ',vstup);                      {a podle této mezery řádek rozdělíme na "vstup1" a "vstup2"}           vstup1 := copy(vstup, 1, mezera-1);           vstup2 := copy(vstup, mezera+1, length(vstup)-mezera);                      {zkusíme převést oba vstupy na čísla}           val(vstup1, den, error);           val(vstup2, trzba, error2);                      {nenastala při převodu chyba?}           if (error = 0) and (error2 = 0) then begin                {nenastala, vstupy jsou OK}                {je už další měsíc? (je datum dne nižší než předchozí?)}                if den < prev then begin                   {ano, další měsíc}                   inc(m);                   mesice[m] := 0;                end;                {připočteme tržbu k měsíční tržbě}                mesice[m] := mesice[m] + trzba;           end;           {a načítáme další řádek}           prev := den;           readln(vstup);      end;      mesicu := m;      {vypíšeme tržby ve všech načtených měsících}      for m := 1 to mesicu do begin          writeln('Trzba v mesici ',m,'. byla ', mesice[m]:7:2, ' Kc.');          celkem := celkem + mesice[m]      end;      {a vypíšeme průměrnou měsíční tržbu}      writeln('Prumerna mesicni trzba byla ', (celkem/mesicu):7:2) end.

Program poprvé používá datový typ řetězec (string), viz #datatypes. Proměnné vstup, vstup1, vstup2, deklarované jako řetězce mohou tudíž nabývat "textových" hodnot. Hodnota řetězce může být obecně libovolná posloupnost znaků (písmena, číslice, jiné znaky). Délka této posloupnosti může být omezena uvedením maximálního počtu znaků do hranatých závorek za označení typu string - např. bychom napsali: vstup, vstup1, vstup2: string[100];, čímž bychom limitovali počet znaků v retězcích na sto.

Obsahem řetězce mohou obecně být jakékoli znaky. V praxi ale dosti často interpretujeme hodnotu řetězce určitým přesně vymezeným způsobem. Například v tomto našem programu hodnotu do proměnné vstup zadává uživatel v příkazu readln(vstup). Může sice zadat cokoli, ale program předpokládá, že bude zadána dvojice čísel oddělených mezerou.

Dále se v programu objevuje pascalská procedura val, určená k převodu řetězce na reálné, případně též celé číslo. Jako první parametr zadáme řetězec, jenž obsahuje číslo (jako posloupnost znaků se znaménkem atd.), které se má převést. Druhým parametrem je proměnná (tento parametr je tudíž volán/předáván odkazem), do níž bude uloženo převedené číslo. Konečně třetím parametrem je proměnná typu integer, kam val vrátí kód případné chyby při převodu.

6.6.6. Současné vyhledání maxima i minima

60.

MaxMin in One (MaxMinInOne.pas)

program MaxMinInOne; var min, max, i, n: integer;     a: array[1..100] of integer; begin      writeln('Hledani maxima/minima na jeden pruchod');      writeln('Zadejte pocet cisel: ');      readln(n);      {zadává postupně všechna čísla}      for i := 1 to n do begin          write('Zadej cislo: ');          readln(a[i]);      end;      {je jich lichý počet -> první zvlášť, pak po dvojicích}      if odd(n) then begin          {nastavíme max i min na první číslo}          max := a[1];          min := a[1];          i := 2;      {je jich sudý počet -> můžeme brát dvojice hned}      end else begin                {nastavíme max a min podle prvních dvou čísel}          {větší z nich do maxima, menší do minima}          if a[1] > a[2] then begin             min := a[2];             max := a[1];          end else begin             min := a[1];             max := a[2];          end;          i := 3;      end;      {dokud není konec posloupnosti}      while i < n do begin                  {větší ze dvojice a[i], a[i+1] může změnit maximum, menší minimum}            if a[i] < a[i+1] then begin               if a[i] < min then min := a[i];               if a[i+1] > max then max := a[i+1];            end else begin               if a[i+1] < min then min := a[i+1];               if a[i] > max then max := a[i];            end;            inc(i)      end;      writeln('Minimum bylo ', min, ', maximum bylo ',max,'.') end.

6.6.7. Něco z bankovnictví...

61.

Úroky (Uroky.pas)

program Uroky; var vklad, urok_sazba: real;     celkem, predchozi: real; begin      celkem := 0;      write('Zadejte vklad v Kc a urokovou sazbu v procentech: ');      readln(vklad, urok_sazba);      {zadáním úrokové sazby 0 se program ukončí}      while urok_sazba >= 0 do begin            {momentální stav na účtu se stává předchozím,             počítáme totiž nový stav}            predchozi := celkem;                        {celkový stav po přidání vkladu a zúročení}            celkem := (celkem + vklad)*(1+urok_sazba/1200);                        {kolik přibylo}            writeln('Za tento mesic pribylo na uctu celkem ',                     celkem-predchozi:7:2,' Kc.');                                 {kolik ukládáme?}            write('Zadejte vklad v Kc a urokovou sazbu v procentech: ');            readln(vklad, urok_sazba);      end;      writeln('Na uctu je celkem ',celkem:7:2, ' Kc.'); end.

Jen pro připomenutí: úroková sazba v programu uvažovaná je roční (per annum, p.a.). Abychom zjistili, o kolik procent vklad naroste za měsíc, musíme ji vydělit 12 (a ještě 100, protože jsme zadávali v procentech a chceme výsledek v setinách).

6.6.8. Různé

Inteligentní hádání myšleného čísla
Nejprve se vrátíme k našemu prapůvodnímu prográmku na hádání čísla, jenž si počítač "vymyslí" (čili vygeneruje jako pseudonáhodné). Tentokrát to trochu obrátíme - číslo si bude myslet člověk-uživatel a program bude chytře kladenými dotazy zjišťovat, jaké číslo si obsluha myslela. Uživatel odpovídá -1, 0 nebo 1 podle toho, zda si myslí číslo větší, stejné nebo menší než počítač hádal. Odpovídat by měl popravdě, pokud se v odpovědech dojde ke sporu, program to pozná.

62.

Binární hádání čísla (BinarniHadaniCisla.pas)

program BinarniHadaniCisla; var x, low, high, odhad: integer; begin      write('Zadejte rozsah, ze ktereho si budete myslet cislo (1..x): ');      readln(high);      low := 1;      repeat           odhad := (low + high) div 2; {zkusíme hádat v polovině intervalu...}           write('Muj odhad mysleneho cisla: ', odhad);           write(' je vetsi=+1, roven=0, mensi=-1 nez myslene cislo?: ');           readln(x);           if x < 0 then low := odhad {odhad byl menší, takže jdeme od něj výš}                    else if x > 0 then high := odhad {odhad byl větší, takže jdeme od něj níž}                                  else low := high + 1 {našli jsme -> nastavíme "low" tak,                                                                  abychom ihned opustili repeat cyklus}      until low + 1 >= high;      {výše uvedeným algoritmem musí program vždy uhodnout myšlené číslo,       není-li tomu tak, pak uživatel "švindloval" - někdy odpověděl nesprávně       - to poznáme!}             if low = high + 1 then writeln('Myslene cislo je ', odhad)                        else writeln('Svindlujete!') end.

Nejdelší rostoucí podposloupnost
Smyslem dalšího programu je nalézt v postupně načítané neprázdné posloupnosti celých kladných čísel nejdelší rostoucí podposloupnost. Uživatel zadává postupně kladná čísla a vstup ukončí zadáním nekladného čísla, např. nuly.

63.

Rostoucí podposloupnost (RostouciPodposloupnost.pas)

program RostouciPodposloupnost; var max_delka_rost, d, pred, x: integer; begin      writeln('Zadavejte prvky posloupnosti, ukoncete nekladnym cislem');      write('Zadejte cislo: ');      readln(x);      {předchozí číslo zatím žádné nebylo}      pred := x;      max_delka_rost := 1;      d := 1;      {dokud uživatel nezakončí vstup nulou}      while x > 0 do begin            {je číslo větší než předchozí?}            if pred < x then inc(d) {ano, rostoucí podposloupnost je zase o delší}                        else begin                         {ne, rostoucí podposl. je u konce.                         Byla delší než doposud nejdelší?}                                  if d > max_delka_rost then max_delka_rost := d;                                                                    {resetujeme délku rostoucí podposloupnosti na 1 }                                  d := 1;                             end;            {ze současného čísla se stane předchozí...}            pred := x;            {...a můžeme načítat další číslo}            write('Zadejte cislo: ');            readln(x)      end;      writeln('Nejdelsi rostouci podposloupnost mela ', max_delka_rost, ' prvku') end.

Kam zajít pro pomoc?
Program, jež právě uvedeme, určuje město nejbližší místu setkání (resp. srážky) dvou automobilů. Je zadáno:

1. mest měst na přímce (města zadána svým názvem a souřadnicí);
2. dvě auta, každé v některém z měst (města zadána číslem - jejich indexem) a
3. rychlosti těhto dvou aut (záporná rychlost = opačný směr);
4. obě auta vyjednou ve stejný okamžik;
5. úkolem je najít bod, ve kterém se setkají (srazí...) a
6. město, které je k místu setkání aut nejblíž (kam jít pro pomoc při srážce...).

64.

Sražená auta (SrazenaAuta.pas)

program SrazenaAuta; type pole_mest = array[1..10] of real; var mesta: pole_mest;     nazvy_mest: array[1..10] of string[20];     vychozi1, vychozi2, mest, i: integer;     rychlost1, rychlost2: real;     vzdal_srazky, cas_srazky: real; {funkce najde město nejbližší k zadanému místu se vzdalenosti "vzdalenost"} {hledá binárním vyhledáváním - viz příslušný příklad} function nejblizsi_mesto( var m: pole_mest;                           poc_mest: integer;                           vzdalenost: real ): integer; var low, high, mid: integer; begin         low := 0; high := poc_mest+1;         while (high-low > 1) do begin                 mid := (low+high) div 2;                 if vzdalenost > m[mid] then                         low := mid                 else if vzdalenost < m[mid] then                                 high := mid                      else low := high + 1;         end;         if low >= high then                 nejblizsi_mesto := mid         else                 if abs(vzdalenost-m[low]) <= abs(vzdalenost-m[high]) then                         nejblizsi_mesto := low                 else                         nejblizsi_mesto := high; end; begin         write('Zadejte pocet mest :');         readln(mest);         {zadá se název města 1 s polohou 0}         write('Zadejte nazev vychoziho mesta :');         readln(nazvy_mest[1]);         {zadají se názvy a polohy všech dalších měst}         {poloha < 0 znamená, že město je "vlevo" od prvního města}         for i:= 2 to mest do begin                 write('Zadejte nazev a vzdalenost mesta ',i,'. od prvniho mesta: ');                 readln(nazvy_mest[i]);                 readln(mesta[i]);         end;         for i:= 2 to mest do                 writeln('Mesto ',i, '. ',nazvy_mest[i], ' je od prvniho mesta vzdaleno ',mesta[i],' km.');         write('Zadejte cislo vychoziho mesta prvniho auta :');         readln(vychozi1);         write('Zadejte rychlost prvniho auta :');         readln(rychlost1);         write('Zadejte cislo vychoziho mesta druheho auta :');         readln(vychozi2);         write('Zadejte rychlost druheho auta :');         readln(rychlost2);         {spočte čas srážky}         cas_srazky := (mesta[vychozi2]-mesta[vychozi1])/(rychlost1-rychlost2);         {a místo srážky - tj. její vzdálenost od bodu 0}         vzdal_srazky := mesta[vychozi1] + cas_srazky * rychlost1;         {vypíše město nejbližší k místu srážky - jeho název}         writeln('Pro pomoc by meli jet do mesta ',                  nazvy_mest[nejblizsi_mesto(mesta, mest, vzdal_srazky)],'.'); end.

Auta do měst!

Pod nepříliš "ekologicky" znějícím názvem následujícího programu se skrývá úkol najít z množiny aut to, které se nejdříve dostane do města.

1. Je dána přímka, na níž leží mest měst, poloha každého je udána jednou souřadnicí.
2. Je dáno aut aut, u každého víme, ve kterém městě se na začátku nachází a jakou má rychlost - záporná rychlost znamená, že auto jede "doleva" (proti orientaci souřadnic).
3. V jednu chvíli se všechna auta rozjedou "svými" rychlostmi a směry a úkolem je určit, které z nich bude nejdříve v (jiném než jeho startovním) městě.

65.

Auta do měst (AutaDoMest.pas)

program AutaDoMest; const maxmest = 10;         maxvzd = 1e10;         maxcas = 1e10; var mesta: array[0..maxmest+1] of real;     rychl_aut: array[1..maxmest] of real;     vychozi_mesto_aut: array[1..maxmest] of integer;     mest, aut, nejdriv_auto, nejblizsi_mesto, i: integer;     cas, min_cas: real;      begin         {uživatel zadá počet měst do proměnné "mest"}         write('Zadejte pocet mest:');         readln(mest);                  {uživatel zadá polohy měst - vzdálenosti měst od počátku}         for i:= 2 to mest do begin                 write('Zadejte vzdalenost mesta ',i,'. od prvniho mesta: ');                 readln(mesta[i]);         end;                  {program nastaví fiktivní "města" na začátek a konec pole měst}         mesta[0]:= -maxvzd;         mesta[maxmest+1]:= +maxvzd;                  {uživatel zadá počet aut}         write('Zadejte pocet aut:');         readln(aut);                  {uživatel zadá výchozí města a rychlosti aut}         for i:= 1 to aut do begin                 write('Zadejte cislo mesta, odkud vyjizdi auto ',i,': ');                 readln(vychozi_mesto_aut[i]);                 write('Zadejte rychlost auta ',i,': ');                 readln(rychl_aut[i]);         end;                  min_cas := maxcas;                  {pro každé z počtu "aut" aut spočte, kdy dojede do města}         for i:= 1 to aut do begin                 if rychl_aut[i] < 0 then { když rychlost < 0 => auto jede "doleva" }                         if abs((mesta[vychozi_mesto_aut[i]]                                 -mesta[vychozi_mesto_aut[i]-1])                                 /rychl_aut[i]) < min_cas then begin                                                                  {jestliže jsme právě narazili na rychlejší příjezd do města,                                  zapamatujeme jej do proměnné "min_cas"}                                                                   min_cas := abs((mesta[vychozi_mesto_aut[i]]                                                 -mesta[vychozi_mesto_aut[i]-1])/rychl_aut[i]);                                 nejblizsi_mesto := vychozi_mesto_aut[i]-1;                                 nejdriv_auto := i;                         end else { to "else" patří k nejbližšímu "if",                                                   aby následující                                                   "else" již patřilo k prvnímu "if" }                                                                    else { rychlost > 0 => auto jede "doprava" }                                          if abs((mesta[vychozi_mesto_aut[i]]                                 -mesta[vychozi_mesto_aut[i]+1])/rychl_aut[i])                                 < min_cas then begin                                                                  {jestliže jsme právě narazili na rychlejší příjezd do města,                                  zapamatujeme jej do proměnné "min_cas"                                  - druhá větev pro opačný směr auta }                                                                   min_cas := abs((mesta[vychozi_mesto_aut[i]]                                                 -mesta[vychozi_mesto_aut[i]+1])                                                 /rychl_aut[i]);                                 nejblizsi_mesto := vychozi_mesto_aut[i]+1;                                 nejdriv_auto := i;                         end         end;         writeln('Do mesta nejdrive (v case ',min_cas:8:2,') dojede auto ',                  nejdriv_auto, ' a to do mesta ',nejblizsi_mesto); end.

6.7. Další složené datové typy ··· Záznamy

• Prvními byly proměnné jednoduché - např. var i: integer; byla deklarace jednoduché proměnné typu celé číslo. Taková proměnná nesla v jeden okamžik jednu celočíselnou hodnotu.
• Druhou možností bylo pole, nesoucí současně více prvků (hodnot), přístupných přes indexy. Příkladem je pole rychl_aut: array[1..maxmest] of real; z předchozí ukázky.

Se záznamem (těchto tří hodnot) pak můžeme manipulovat jako s hodnotu jednou, tzn. máme-li dvě proměnné téhož typu záznam, můžeme je vzájemně přiřazovat, tj. kopírovat obsah mezi nimi, jediným přiřazovacím příkazem. Následující program ukáže více:

66.

Záznam o kontaktu na osobu (Zaznam.pas)

program Zaznam; uses crt; type kontakt = record                 jmeno: string;                 tlf_cislo: longint; {typ "dlouhe cele cislo"}                 email: string;         end; var k: kontakt; {procedura naplní kontakt údaji} procedure napln_kontakt(var k: kontakt); begin     with k do begin         write('Zadej jmeno: ');         readln(jmeno);         write('Zadej tlf cislo: ');         readln(tlf_cislo);         write('Zadej e-mailovou adresu: ');         readln(email);     end; end; {procedura vypíše kontakt} procedure vypis_kontakt(var k: kontakt); begin     with k do begin         writeln;         writeln('--- Kontakt ---');         writeln('Jmeno: ',jmeno);         writeln('Telefonni cislo: ', tlf_cislo);         writeln('E-mailova adresa: ', email);     end; end; begin     clrscr;     napln_kontakt(k);     vypis_kontakt(k); end.

1. na naplnění proměnné typu záznam o kontaktu na osobu a
2. vypsání kontaktu.

Dále je ze zdrojového kódu patrné, jak je možné přistupovat k složkám proměnné typu záznam. Konstrukcí with promennaTypuZaznam do prikaz zpřístupníme v příkazu prikaz složky záznamu promennaTypuZaznam. Jinou možností, jak zpřístupnit složku, je přes "tečkovou notaci". Za jméno proměnné typu záznam přidáme tečku a jméno složky - výsledkem je odkaz na příslušnou složku této proměnné. Následující program dělá totéž jako ten předchozí, ovšem s "tečkovou notací":

67.

Záznam o kontaktu - zpřístupnění složky záznamu 'tečkou' (Zaznam2.pas)

program Zaznam2; uses crt; type kontakt = record                 jmeno: string;                 tlf_cislo: longint; {typ "dlouhe cele cislo"}                 email: string;         end; var k: kontakt; {procedura naplní kontakt údaji} procedure napln_kontakt(var k: kontakt); begin     write('Zadej jmeno: ');     readln(k.jmeno);     write('Zadej tlf cislo: ');     readln(k.tlf_cislo);     write('Zadej e-mailovou adresu: ');     readln(k.email); end; {procedura vypíše kontakt} procedure vypis_kontakt(var k: kontakt); begin     writeln;     writeln('--- Kontakt ---');     writeln('Jmeno: ',k.jmeno);     writeln('Telefonni cislo: ', k.tlf_cislo);     writeln('E-mailova adresa: ', k.email); end; begin     clrscr;     napln_kontakt(k);     vypis_kontakt(k); end.

Tento způsob přístupu je ale v případě složitějších záznamů méně přehledný než přes with.

6.7.1. Pole záznamů

1. přidat nový kontakt
2. vypsat všechny kontakty.

68.

Adresář kontaktů (Adresar.pas)

program Adresar; uses crt; const maxkontaktu = 100; type kontakt = record                 jmeno: string;                 tlf_cislo: longint; {typ "dlouhe cele cislo"}                 email: string;         end; var kontakty: array[1..maxkontaktu] of kontakt;     novy_kontakt: kontakt;     kontaktu: integer;     c: char; {funkce přidá nový kontakt do adresáře  a vrátí počet kontaktů} function pridej_kontakt: integer; var k: kontakt; begin     if kontaktu < maxkontaktu then begin         with k do begin             write('Zadej jmeno: ');             readln(jmeno);             write('Zadej tlf cislo: ');             readln(tlf_cislo);             write('Zadej e-mailovou adresu: ');             readln(email);         end;         kontaktu := kontaktu + 1;         kontakty[kontaktu] := k;     end;     pridej_kontakt := kontaktu; end; {procedura vypíše i-tý kontakt} procedure vypis_kontakt(i: integer); begin     if i <= kontaktu then begin         with kontakty[i] do begin             writeln;             writeln('--- Kontakt c. ',i, ' ---');             writeln('Jmeno: ',jmeno);             writeln('Telefonni cislo: ', tlf_cislo);             writeln('E-mailova adresa: ', email);         end;     end else         writeln('Kontakt c. ',i,' neexistuje, kontaktu je pouze ',kontaktu); end; {procedura vypíše vsechny kontakty} procedure vypis_kontakty; var i: integer; begin     for i := 1 to kontaktu do         vypis_kontakt(i) end; begin     clrscr;     repeat         writeln('-------------------------');         writeln('Adresar kontaktu na osoby');         writeln('K -> konec programu');         writeln('N -> zadat novy kontakt');         writeln('V -> vypsat vsechny kontakty');         writeln;         {čeká na stisk klávesy udávající požadovanou činnost}         c := upcase(readkey);         case c of               'N': pridej_kontakt;               'V': vypis_kontakty;         end     until c = 'K' end.

var z: record
		  pocet_lidi: integer;
		  lidi: array [1..100] of string
	   end

Úloha č. 14. Rozšiřte výše uvedený program o funkci "vypiš kontakt číslo x", tedy tak, aby se zeptal uživatele na číslo kontaktu a ten vypsal.

Úloha č. 15. Další vaše rozšíření by mělo umožňovat databázi (tj. v poli) kontaktů vyhledávat: najde a vypíše záznam, kde jméno bude rovno jménu zadanému. Dva řetězce lze porovnat běžným = (rovná se).

Pole záznamů podruhé - program telefonní tarify
V příkladu "Srovnání telefonních tarifů" se podívejme na jiný příklad využití pole záznamů. Jedním prvkem pole bude opět záznam o několika složkách. Mimochodem, taková struktura se velmi blíží tomu, co známe z databází - totiž databázové tabulce:

1. prvky pole odpovídají řádkům v tabulce;
2. prvky (složky) záznamu odpovídají sloupcům v tabulce (i s tím, že sloupce jsou "nadepsané" titulkem značícím, co hodnoty ve sloupci znamenají).

1. název tarifu;
2. měsíční paušální platba;
3. minuty zdarma v tomto paušálu;
4. minutové hovorné (předpokládejme jednotné do všech sítí) pro hovory nad minuty zdarma

69.

Srovnání telefonních tarifů (TelefonniTarify.pas)

program TelefonniTarify; const maxtarifu = 10;         maxcena = 1e10; type tarif = record                 pausal, hovorne: real;                 volne_min: integer;         end; var tarify: array[1..maxtarifu] of tarif;     min_cena: real;     provolane_min: integer;     tarifu, nejlevn_tarif, i: integer; {funkce spočte náklady tarifu "t" při provolaných minutách "prov_min"} function naklady(t: tarif; prov_min: integer): real; begin         with t do                 if prov_min > volne_min then                         naklady := pausal + (prov_min - volne_min) * hovorne                 else                         naklady := pausal end; begin         write('Zadejte pocet tarifu:');         readln(tarifu); {zadáme postupně údaje o všech tarifech}         for i:= 1 to tarifu do begin                 writeln('********');                 write('Zadejte mesicni pausalni poplatek v tarifu ',i,'.: ');                 readln(tarify[i].pausal);                 write('------- minutove hovorne: ');                 readln(tarify[i].hovorne);                 write('------- mesicni volne minuty: ');                 readln(tarify[i].volne_min);         end;         write('Zadejte provolane minuty mesicne:');         readln(provolane_min);         nejlevn_tarif := 1;         min_cena := maxcena; {vyhledáme nejlevnější tarif při daném počtu provolaných minut měsíčně}         for i:= 1 to tarifu do             {pro i-tý tarif udělej srovnání s dosud nejlevnějším tarifem}             if naklady(tarify[i], provolane_min) < min_cena then begin                     {i-tý tarif je levnější než dosud nejlevnější tarif...} nejlevn_tarif := i;                     nejlevn_tarif := i;                     {...a jeho měsíční cena je:}                     min_cena := naklady(tarify[i], provolane_min)             end;         writeln('Nejlevneji vychazi tarif ',nejlevn_tarif, ' s naklady ',min_cena:9:2,' Kc.'); end.

6.7.2. "Slovíčkaření"

Nalezení nejdelšího slova
Úkolem prvního je najít v zadané "větě" (řetězci slov oddělených mezerami) nejdelší slovo. Budeme předpokládat, že na konci není tečka a že mezi každými dvěma slovy "uvnitř" je právě jedna mezera.

70.

Nejdelší slovo (NejdelsiSlovo.pas)

program NejdelsiSlovo; const maxslov = 100; var s: string;     i, pred, nejdelsi_slovo, delka_nejd_sl: integer; begin         write('Zadejte vetu:');         readln(s);         {za konec řetězce si poznačíme mezeru navíc}         s[length(s)]:=' ';         {předp., že nejdelší slovo bylo na začátku řetězce}         nejdelsi_slovo := 1;         delka_nejd_sl := 0;         pred := 1;         i := 1;         {dokud nejsme na konci řetězce}         while i <= length(s) do begin                          {narazili jsme na mezeru - předěl slov?}                 if s[i] = ' ' then begin                                          {ano, bylo právvě dokončené slovo zatím to nejdelší?}                         if (i-pred) > delka_nejd_sl then begin                                          {ano, poznačíme si jeho polohu a délku}                                 nejdelsi_slovo := pred;                                 delka_nejd_sl := i-pred;                         end;                         pred := i+1                 end;                 inc(i)         end;         writeln('Nejdelsi slovo je ''',                  {z řetězce vybereme to nejdelší slovo}                  copy(s, nejdelsi_slovo, delka_nejd_sl),'''.'); end.

Nejvícekrát se opakující slovo
Následující program nalezne v zadaném řetězci slovo (posloupnost nemezerových znaků), které se nejvícekrát opakuje po sobě. Např. v řetězci nesnese se se sestrou ani s bratrem ani s matkou ani s otcem se nejvícekrát po sobě opakuje slovo se.

71.

Opakující se slovo (OpakujiciSeSlovo.pas)

program OpakujiciSeSlovo; const maxslov = 100; var s: string;     i, pred, delka_pred, opakovani: integer;     nejvice_opakovani, nejvice_opak_slovo, delka_nejvice_opak_slova: integer; {srovnání dvou slov z řetězce s,  slova začínají na pozicích zac1, zac2} function stejna(s: string; zac1, zac2: integer): boolean; var delka: integer; begin         delka := pos(' ', s, zac1+1);         stejna := copy(s, zac1, delka) = copy(s, zac2, delka) end; begin         write('Zadejte vetu:');         readln(s);                  {opět poznačíme mezeru na konec řetězce...}         s[length(s)] := ' ';                  nejvice_opakovani := 1;         nejvice_opak_slovo := 1;         i := pos(' ',s);         delka_nejvice_opak_slova := i-1;                  pred := 1;         delka_pred := 1;         opakovani := 1;                  {dokud nedojdeme na konec řetězce}         while i < length(s) do begin                 {je toto a předchozí slovo stejné?}                 if stejna(s, pred, i) then begin                         {ano, jsou stejná}                         inc(opakovani);                                                  {opakuje se to slovo vícekrát, než je dosavadní maximum?}                         if (opakovani > nejvice_opakovani) then begin                                                          {ano, pak si ho zapamatujeme i s počtem opakování}                                 nejvice_opak_slovo := pred;                                 nejvice_opakovani := opakovani;                                 delka_nejvice_opak_slova := pos(' ', s, pred)-pred;                         end;                 end else                         {ne, nejsou stejná, "resetujeme" počet opakování na 1}                         opakovani := 1;                 pred := i;                 i := pos(' ', s, i)+1;         end;                  writeln('Nejvicekrat opakovane slovo je ',                  copy(s, nejvice_opak_slovo, delka_nejvice_opak_slova),                  ', opakuje se ',                  nejvice_opakovani,'.'); end.

Zedníci
Poslední program z této sekce by mohl sloužit jako jednoduchá pomůcka pro stavební firmu, která potřebuje sestavit pracovní party zedníků tak, aby party mohly být na stavby nasazovány celistvě, tzn. žádnou partu bychom nemuseli při přeřazování na jinou práci "trhat". Úkolem je zjistit maximální počet lidí v jedné partě (party jsou stejně velké) tak, aby party mohly postupně obsloužit dvě různé stavby bez změn v počtu lidí v partě.

72.

Zedníci a dvě stavby (Zednici.pas)

program Zednici; var zedniku, na_stavbu1, na_stavbu2, skupina: integer; {najde největšího společného dělitele čísel a,b} function nsd(a,b: integer): integer; var pom: integer; begin         repeat                 a:=a mod b;                 pom:=a;                 a:=b;                 b:=pom         until b=0;         nsd := a; end;      begin         write('Zadejte celkovy pocet zedniku:');         readln(zedniku);                  write('Zadejte pocet zedniku na stavbu 1.:');         readln(na_stavbu1);                  write('Zadejte pocet zedniku na stavbu 2.:');         readln(na_stavbu2);                  {skupina musí mít nejvýš tolik dělníků,          aby skupiny mohly na obě stavby vždy celistvé}                   skupina := nsd(na_stavbu1, na_stavbu2);                  writeln('Nejvetsi mozne skupiny budou mit ',skupina, ' zedniku.');         writeln('Na stavbu 1. pujde ', na_stavbu1 div skupina, ' skupin.');         writeln('Na stavbu 2. pujde ', na_stavbu2 div skupina, ' skupin.'); end.

Úloha č. 16. Napište program, který bude postupně načítat posloupnost kladných reálných čísel zadávanou z klávesnice a zjistí její aritmetický, geometrický a harmonický průměr. Posloupnost bude ukončena zadáním čísla 0.

Úloha č. 17. Napište program, který bude postupně načítat posloupnost kladných reálných čísel zadávanou z klávesnice, zjistí a nakonec vypíše nejdelší nerostoucí podposloupnost nachazející se v zadávané posloupnosti. (Podposloupností se myslí souvislý úsek hodnot z původní posloupnosti.) Posloupnost bude ukončena zadáním čísla 0.

7. Jeden cyklus nestačí ··· aneb vnořené cykly

7.1. Vícerozměrná pole - matice, jejich načítání a výpis

Seznámíte se s vícerozměrným polem.

Naučíte se naplňovat takové pole hodnotami, jež zadá uživatel.

Vytvoříte si základní procedury pro práci s dvourozměrným polem - maticí.

7.1.1. Praktické použití vícerozměrných polí

7.1.2. Deklarace a přístup k prvkům vícerozměrných polí

Podívejme se nyní, jak vícerozměrné pole zadeklarovat a načíst do něj hodnoty. Uveďme to na příkladu pole dvojrozměrného, obecnější popis nalezneme v referenci (viz #ref_array).

• deklarace má tvar nazevPole: array [dolniMezIndexu1..horniMezIndexu1, dolniMezIndexu2..horniMezIndexu2] of ZakladniTyp. Většina prvků této deklarace má stejný význam jako u pole jednorozměrného, přibývá zde vlastně jen rozsah druhého indexu dolniMezIndexu2..horniMezIndexu2.
• k prvkům dvojrozměrného pole přistupujeme opět pomocí indexů v hranatých závorkách, a to takto: nazevPole[prvniIndex, druhyIndex]. Indexy přitom oddělujeme čárkou.

Na programu níže vidíme příklad deklarace proměnné typu dvojrozměrné pole (matice), načtení hodnot do této matice a výpis matice.

73.

Načítání a výpis pole (NacitaniVypisMatice.pas)

program NacitaniVypisMatice; var p, q, i, j: integer;     m: array[1..5, 1..2] of real; begin    writeln('Nacitani prvku do matice');    write('Pocet radku matice: ');    readln(p);    write('Pocet sloupcu matice: ');    readln(q);    {v cyklu načteme p řádků matice}    for i := 1 to p do begin       {v cyklu načteme q prvků p-tého řádku matice}       writeln('Zadej postupne prvky ',i,'. radku: ');       for j := 1 to q do begin          write(j,'. prvek: ');          readln(m[i,j]);       end;       writeln;    end;    writeln('Do matice M jsme zadali tyto prvky: ');    {v cyklu vypíšeme p řádků matice}    for i := 1 to p do begin       {v cyklu vypíšeme q prvků p-tého řádku matice}       for j := 1 to q do          write(m[i,j]:7:2);       {a po každém řádku odřádkujeme}       writeln;    end end.

7.1.3. Vícerozměrná pole jako parametry procedur

74.

dtto, ale s procedurami (NacitaniVypisMaticeProcedurou.pas)

program NacitaniVypisMaticeProcedurou; type matice = array[1..5, 1..2] of real; var m: matice;     p, q, i, j: integer; {procedura na načtení matice, sama se zeptá  na zadávaný počet řádků/sloupců} procedure NactiMatici(var mat: matice; var radku: integer; var sloupcu: integer); var i, j: integer; begin    write('Pocet radku matice: ');    readln(radku);    write('Pocet sloupcu matice: ');    readln(sloupcu);        for i := 1 to radku do begin       writeln('Zadej postupne prvky ',i,'. radku: ');       for j := 1 to sloupcu do begin          write(j,'. prvek: ');          readln(mat[i,j]);       end;       writeln;    end end; {procedura na výpis matice,  vypíše zadaný počet řádků/sloupců} procedure VypisMatici(var mat: matice; radku, sloupcu: integer); var i, j: integer; begin    for i := 1 to radku do begin       for j := 1 to sloupcu do          write(mat[i,j]:7:2);       writeln;    end end; begin    {načte matici}    NactiMatici(m, p, q);    {v proměnné p je počet řádků, v q je počet sloupců matice M}    writeln('Do matice M jsme zadali tyto prvky: ');    VypisMatici(m, p, q) end.

Povšimněme si, že i u procedury VypisMatici používáme u parametru typu dvojrozměrné pole předávání odkazem, nikoli hodnotou. Zdá se to divné, vždyť přece uvnitř procedury VypisMatici matici nepotřebujeme modifikovat (něco v ní měnit) a nepotřebujeme tudíž pracovat přímo s proměnnou m - skutečným parametrem při volání procedury VypisMatici z hlavního programu. Stačilo by nám přece předat do vypisovací procedury jen hodnoty matice - skutečného parametru. Důvod, pro předáváme matici do procedury odkazem, je tentokrát nikoli teoretický, ale ryze praktický:

1. zatímco předání odkazu technicky znamená předání jedné adresy (což je vlastně jedno celé číslo),
2. tak předání hodnoty představuje zkopírování celého skutečného parametru (tedy v našem případě matice p krát q čísel) do zásobníku.

7.1.4. Problémy s "objemnějšími" strukturami

Pole není "nafukovací" struktura
Tedy přinejmenším v Pascalu... Potřebujeme-li ukládat rozsáhlejší data do pole, nezbývá než si předem rozmyslet, jaký maximální rozsah (počet prvků) může pole mít a podle toho příslušnou proměnnou v deklaraci dimenzovat. Pak často tuto kapacitu nevyužijeme a přesto proměnná stále obsazuje paměť jako by byla využita celá.

Podívejme se zpět na poslední program s načítáním matice: procedura NactiMatici se uživatele zeptala na rozsah (řádků x sloupců), jaký bude matice mít. To však neznamenalo, že by procedura až podle této uživatelské informace deklarovala příslušně velké pole. To z principu nejde, protože deklarace musejí být v deklarační části (procedury či hlavního programu) a s velikostí pole už potom hýbat nelze. Nezbývalo proto nic jného, než sice mít pole nadimenzované na obrovský rozsah a podle skutečné potřeby z něj využívat jen část. Využívaná část je v programu specifikovaná proměnnými p a q a v procedurách formálními parametry radku, sloupcu.

Pokud nestačí pole, použijeme dynamické proměnné
Pokud by nám nevyhovovala možnost nadeklarovat matici dostatečně velkou a využívat z ní jen část, museli bychom vzít na pomoc tzv. dynamické proměnné, resp. dynamické datové struktury, které umožňují vytvářet nové proměnné za běhu programu podle momentální potřeby - například by nebyl problém dynamicky vytvořit další řádek matice. Nebyla by to ovšem matice přesně ve smyslu array [Indexy1, Indexy2] of ZakladniTyp, ale spíše něco jako seznam (posloupnost) řádků (jednorozměrných polí).

Problematikou dynamických proměnných se zde podrobněji zabývat nebudeme.

7.1.5. Co rozhodně s velkými strukturami nedělat?

Zbytečně nepřiřazovat
Jak víme, s poli můžeme snadno pracovat jako s celky, lze tedy i obrovské matice přiřadit jedním příkazem (např. mat1 := mat2). Co to však znamená? Samozřejmě při takového přiřazení musí dojít ke zkopírování (duplikaci) jednoho pole (mat2) do pole na levé straně přiřazení (mat1). Pokud se jedná např. o matice 100 x 100 celých čísel typu longint (jedno číslo obsadí 4 bajty), pak při přiřazení kopírujeme 4 x 100 x 100 bajtů, tj. skoro 40 kB dat. Místo často zbytečného přiřazování celých rozsáhlých polí zkusme raději přiřazovat jen jednotlivé prvky nebo u vícerozměrných polí (matic) jen jednotlivé řádky. Většinou to stačí :-)

Nepředávat do procedur hodnotou
To jsme již diskutovali. Je-li parametrem procedury pole (což je jinak metodicky zcela v pořádku), pak by mělo být předáváno odkazem, ne hodnotou (v hlavičce procedury uvést před jménem parametru-pole var!).

Nedeklarovat velké struktury lokálně v procedurách
Velkých struktur, které nejsou vytvářeny jako dynamické, by mělo být v programu co neméně. Starší verze Turbo Pascalu (vč. verze 5.5) nedovolují více než celkem 64 kB prostoru pro všechny staticky deklarované proměnné dohromady. Že se to zdá dostatečný prostor? Zkuste zodpovědět následující otázku:

Úloha č. 18. Je možné v Turbo Pascalu 5.5 deklarovat pole následujícího typu: array [-100..100, -100..100] of integer nebo array [1..10000] of real?

Zdánlivé východisko z "paměťové krize" by mohlo v jistých případech představovat deklarování velých struktur až uvnitř procedur, jako lokální proměnné těchto procedur. Takové proměnné nezabírají "nedostatkový" 64kilobajtový prostor pro statická data, ale... zabírají ještě omezenější prostor pro lokální proměnné!!! Ty jsou totiž umístěny v zásobníku, pro nějž je v programech psaných v TP 5.5 vyhrazeno maximálně 64 kB. Těchto 64 kB musí ovšem sdílet všechny současně volané procedury, takže pokud jen z hlavního programu voláme proceduru a v jejím těle již žádnou proceduru nevoláme, je to OK. Pokud ovšem i z procedury znovu voláme tutéž nebo jinou proceduru, která si opět "nárokuje" prostor pro své lokální proměnné, může se kapacita zásobníku brzy vyčerpat.

Situace je o to horší, že při běžném nastavení překladače Turbo Pascalu nás program na vyčerpání (přetečení) zásobníku ani neupozorní. Dojde to většinou tak daleko, že se program (nebo i celý operační systém, je-li to DOS) obvykle zhroutí. Abychom aspoň tomu zabránili, můžeme nastavit kontrolu přetečení zásobníku (Stack checking):

7.2. Jednoduché algoritmy řazení

7.2.1. V čem je problém?

Algoritmům, které se postarají o uspořádání posloupnosti podle nějakého klíče, se říká algoritmy řazení nebo též tradičně, ale nepřesně, třídicí algoritmy. Při uspořádávání posloupnotsi jde vlastně o přeuspořádání prvků výchozí posloupnosti tak, aby výsledná posloupnost obsahovala tytéž prvky, ale v požadovaném pořadí.

V této souvislosti se hovoří také o speciální skupině algoritmů řazení, které v případě, že podle zvoleného kritéria nedokážou některé prvky uspořádat (neumíme rozhodnout, který je menší/dříve), zachovají jejich výchozí pořadí. Takovým algoritmům se říká stabilní - "nemění pořadí tam, kde nemusí".

7.2.2. Řazení intuitivně: "opakovaným výběrem minima" (Select Sort)

Intuitivní představa řadicího algoritmu zhruba odpovídá následujícímu postupu (řadíme od nejmenšího prvku po největší - vzestupně):

1. z celé posloupnosti vybereme nejmenší prvek, prohodíme jej s prvním prvkem;
2. opět vybíráme nejmenší prvek, tentokráte však pouze z podposloupnosti dosud neuspořádaných prvků (tj. z posloupnosti "o první prvek kratší";
3. takto vybraný (vlastně už druhý) nejmenší prvek opět prohodíme s prvním prvkem dosud neuspořádané podposloupnosti;
4. ... takto postupujeme dále, v každém kroku vždy vybereme minimum, prohodíme je na začátek dosud neuspořádané podposloupnosti a tím se nám dosud neuspořádaná část posloupnosti zkrátí o jeden prvek;
5. končíme, jakmile je celá posloupnost uspořádaná.

75.

Řazení "opakovaným výběrem minima" (resp. maxima) (SelectSort.pas)

program SelectSort; const max = 100; var i, j, pom, zac, min_cislo, kde_min, pocet : integer;         a: array[1..max] of integer; begin         write('Zadejte pocet cisel: ');         readln(pocet);         {zadáme celou posloupnost}         for i := 1 to pocet do begin                 write('Zadejte cislo: ');                 readln(a[i]);         end;         {v cyklu budeme postupně zvyšovat počátek, odkud vyhledáváme nejmenší prvek}         for zac := 1 to pocet do begin                 {předpokládáme, že první prvek je nejmenší...}                 kde_min := zac;                 min_cislo := a[kde_min];                 {... a v cyklu hledáme prvek skutečně nejmenší}                 for j := zac to pocet do                         {menší než dosud nejmenší -> stává se prozatím nejmenším}                         if a[j] < min_cislo then begin                                 min_cislo := a[j];                                 kde_min := j;                         end;                 {nejmenší nalezený "prohodíme" do již uspořádané části}                 pom := a[zac];                 a[zac] := a[kde_min];                 a[kde_min] := pom;         end;         {nakonec vypíšeme celou uspořádanou posloupnost}         write('Usporadana posloupnost je:');         for i := 1 to pocet do begin                 write(a[i], ' ');         end;          end.

7.2.3. Řazení "probubláváním" (Bubble Sort)

Nevýhodou řazení výběrem minima je neefektivnost při řazení již uspořádané posloupnosti – fakt, že je uspořádaná, nám u tohoto algoritmu řazení nijak nezrychlí. Vždy totiž opakovaně vybíráme minimum z dosud neuspořádané části posloupnosti a jak víme, k vybrání minima z neuspořádaného pole je nezbytné toto pole projít celé - bez ohledu na to, že některé úseky zde již mohou být (třeba částečně) uspořádané.

Podívejme se proto na algoritmus, který se chová v jistém smyslu "přirozeněji" než řazení výběrem minima. Tzv. algoritmus řazení "probubláváním" (bubble sort) postupuje následovně (uvažujme opět řazení vzestupně):

1. bere vždy dvojice po sobě ležících prvků;
2. je-li dvojice správně vzájemně uspořádaná, nedělá nic, není-li správně uspořádaná, prohodí vzájemně tyto dva prvky;
3. vezme další dvojici (viz krok 1.) a tak postupuje do konce posloupnosti;
4. tímto jedním průchodem posloupností se dosáhne přinejmenším toho, že největší prvek bude "probubláváním vytlačen" na konec posloupnosti. O správnosti uspořádání dalších prvků takto nelze nic říci ->
5. Je tedy třeba opakovat výše uvedený postup tak dlouho, dokud nebudou uspořádany úplně všechny prvky.

76.

Řazení "probubláváním" (BubbleSort.pas)

program BubbleSort; const max = 100; var i, j, pom, pocet : integer;         a: array[1..max] of integer; begin         write('Zadejte pocet cisel: ');         readln(pocet);         {zadáme celou posloupnost}         for i := 1 to pocet do begin                 write('Zadejte cislo: ');                 readln(a[i]);         end;         {v cyklu budeme postupně snižovat horní mez "probublávání"}         for i := pocet-1 downto 1 do                 {v cyklu porovnáváme vždy dvě sousední čísla}                 for j := 1 to i do                         {jestliže jsou sousední čísla špatně uspořádaná, tak...}                         if a[j] > a[j+1] then begin                                 {...je prohodíme}                                 pom := a[j];                                 a[j] := a[j+1];                                 a[j+1] := pom;                          end;         {nakonec vypíšeme celou uspořádanou posloupnost}         write('Usporadana posloupnost je: ');         for i := 1 to pocet do begin                 write(a[i], ' ');         end; end.

Stačí tedy vnější cyklus formulovat tak, že skončí, nebude-li ve vnitřním cyklu (v jednom "probublání") realizována žádná výměna.

Úloha č. 19. Použijte tuto optimalizaci na výše uvedený program.

7.2.4. Řazení "vkládáním" (Insert Sort)

77.

Řazení "vkládáním" (InsertSort.pas)

program InsertSort; const max = 100; var i, zac, pocet : integer;         a: array[0..max] of integer; begin         writeln('Razeni posloupnosti vzestupne metodou vkladani');         {zadáme počet čísel}         write('Zadejte pocet cisel: ');         readln(pocet);                  {zadáme čísla}         for i := 1 to pocet do begin                 write('Zadejte cislo: ');                 readln(a[i]);         end;                  {budeme postupně zařazovat čísla počínaje druhým}         for zac := 2 to pocet do begin                 i := zac-1;                 a[0] := a[zac];                                  {s číslem v cyklu postupujeme dolů,                  dokud není na správném místě}                 while a[0] < a[i] do begin                         a[i+1] := a[i];                         dec(i)                 end;                 a[i+1] := a[0];         end;                  {vypíšeme uspořádanou posloupnost}         write('Usporadana posloupnost je:');         for i := 1 to pocet do begin                 write(a[i], ' ');         end;          end.

Úloha č. 20. Použijte vnitřní cyklus z Insert Sortu jako proceduru, zařazující další prvek do již uspořádané poslupnosti.

Mezi efektivní algoritmy řazení patří například

• řazení rozdělováním (Quick Sort),
• řazení slučováním (Merge Sort) nebo
• řazení haldou (Heap Sort).

7.3. Lze "naše" tři algoritmy řazení ještě vylepšit?

7.3.1. Složitost algoritmů

1. výpočetní čas - doba, po kterou výpočetní proces realizující daný algoritmus, využívá procesor;
2. paměť "spotřebovanou" výpočtem - nemyslí se tím samozřejmě nějaké nevratné znehodnocení paměti průběhem výpočtu, nýbrž maximální objem paměti výpočtem použité.

Protože algoritmus je ze své podstaty obecným postupem, jak řešit určitý problém, je jasné, že konkrétní realizace téhož algoritmu pokaždé nad různými přípustnými vstupy spotřebovává výpočetní zdroje v různé míře - obvykle úměrně velikosti vstupních dat. Čím rozsáhlejší jsou vstupní data, tím trvá výpočet obvykle déle. To samozřejmě nemusí platit absolutně. Jsou algoritmy, u nichž není délka výpočtu na velikosti vstupních dat vůbec závislá - je konstantní.

Velikost vstupních dat je samozřejmě vágní pojem, pro konkrétní výpočty a srovnávání složitosti je nutné zadefinovat ji přesněji. Pro jednoduchost se velikost vstupních dat často modeluje jedním číslem a složitost se vypočítává jako funkce tohoto čísla.

Kromě exaktní definice velikosti vstupních dat potřebujeme také srovnatelné měřítko pro hodnoty složitosti - zejména skutečná spotřeba výpočetního času je samozřejmě závislá nejen na algoritmu a jeho programové implementaci, ale do značné míry též na výpočetním výkonu použitého počítače. Je tedy třeba vhodnou definicí složitosti eliminovat vlivy různého prostředí, v němž program podle daného algoritmu běží.

Časovou složitostí algoritmů se proto z těchto důvodů obvykle chápe nikoli skutečný čas spotřebovaný na výpočet nad daným objemem dat, ale počet elementárních výpočetních kroků (operací), potřebných k transformaci těchto vstupních dat na výstupy programu. Typickou elementární operací může být např. sečtení dvou celých čísel, jejich porovnání, výpis na obrazovku,...

Pokud vnímáme to, že tentýž algoritmus může být použit pro výpočet nad daty s velmi odlišným rozsahem - lišící se i o několik řádů - snadno přijmeme to, že se často vyplatí sledovat místo skutečného počtu elementárních výpočetních kroků nad vstupními daty dané velikosti jen tzv. asymptotickou složitost daného algoritmu. Asymptotická složitost (AS) je tedy zhruba řečeno taková složitost, u jejíhož určování nás vůbec nezajímá, jak dlouho trvá výpočet nad "málo rozsáhlými" daty. Zajímáme se tedy o závislost délky výpočtu na velikosti vstupních dat až pro data dostatečně velká na to, aby se na nich při výpočtu neprojevily "okrajové záležitosti" chodu programu, jako je např. úvodní inicializace proměnných, otvírání souborů, tisk výsledků atd. Prostě na asymptotickou složitost má vliv pouze "samotný výpočet" bez jeho "okrajové režie". Také nás u asymptotické složitosti nezajímají rozdíly v rychlosti, které lze vystihnout nějakou multiplikativní konstantou - dva algoritmy mají stejnou AS, liší-li se délky výpočtů obou z nich nad stejnými daty vždy "zhruba" k-krát, kde k je konstanta, nezávislá n avelikosti vstupních dat. Trvá-li výpočet nad prvním z algoritmů vždy 10 krát déle než nad druhým, bez ohledu na velikost vstupních dat, mají oba algoritmy asymptotickou složitost stejnou.

7.3.2. Složitost algoritmů řazení

Složitost řazení "probubláváním"
Úkolem je tedy určit, kolik elementárních operací - v tomto případě tím myslíme operaci porovnání dvou prvků - se provede během vykonání tohoto algoritmu řazení, vzhledem k počtu prvků vstupní posloupnosti. Počet prvků vstupní posloupnosti se totiž jeví jako výhodné měřítko velikosti vstupních dat - je totiž evidentní, že považovat za velikost vstupních dat například maximuální číslo v posloupnosti je zcela irelevantní, protože rychlost uspořádávání na velikosti čísel vůbec nezávisí. Pro posuzování složitosti uvažujeme samozřejmě opět nejhorší případ, tj. jako bychom řadili tak "nešikovně" uspořádanou vstupní posloupnst dané velikosti, aby délka výpočtu byla největší možná.

Kolik elementárních operací se tedy při jednou uspořádání posloupnosti tímto algoritmem provede?

1. Vynecháme načtení posloupnosti, to nemá s řazením nic společného.
2. Počet operací začneme zkoumat od vnějšího cyklu. Ten proběhne v případě neoptimalizovaného algoritmu právě pocet-1 krát.
3. V každém jednom průchodu vnějším cyklem se provede vnitřní cyklus pro hodnoty od 1 do i.
4. V těle vnitřního cyklu proběhne vždy porovnání a někdy ještě i záměna ("prohození") sousedních prvků.
5. Celkem tedy proběhne: 1 + 2 + 3 + 4 + ... + n-1 porovnání a nejvýše tolik záměn.

Počet elementárních operací během "bublinového" řazení posloupnosti délky n prvků je tedy přímo úměrný druhé mocnině n.

Složitost řazení "vkládáním"
Úkolem je tedy opět určit, kolik elementárních operací - v tomto případě tímto termínem také myslíme operaci porovnání dvou prvků - se provede během vykonání tohoto algoritmu řazení, vzhledem k počtu prvků vstupní posloupnosti. Opět také respektujeme metodu "analýzy nejhorší případu", tedy tak "nešikovně" uspořádané vstupní posloupnst dané velikosti, aby délka výpočtu byla největší možná.

Kolik elementárních operací se tedy při jednou uspořádání posloupnosti tímto algoritmem provede?

1. Vynecháme načtení posloupnosti, to nemá s řazením nic společného.
2. Počet operací začneme zkoumat od vnějšího cyklu. Ten proběhne v případě neoptimalizovaného algoritmu právě pocet-1 krát. Každý průchod vnějším cyklem realizuje u tohoto algoritmu vložení jednoho dalšího prvku (i-tého) do již uspořádané posloupnosti prvků s indexy 1..1-1.
3. V každém jednom průchodu vnějším cyklem se tedy provede zařazení jednoho prvku. Jak to dopadne v nejhorším případě?
4. Nejhorší případ nastane, když s vkládaným prvkem musíme "probublat" až na začátek posloupnosti. V tomto případě se provede i-1 operací porovnání.
5. Celkem tedy v nejhorším případě proběhne: 1 + 2 + 3 + 4 + ... + n-1 porovnání.

Počet elementárních operací během řazení vkládáním nad posloupností délky n prvků je tedy stejně jako u předchozího přímo úměrný druhé mocnině n. Čili asymptoticky nenastává žádné zlepšení.

Podívejme se však na toto řazení trochu "optimističtěji", analyzujme pro zajímavost nejlepší případ. Najlepším případech zde nastává v situaci, kdy posloupnost je již předem uspořádaná. Potom v každý průchod vnějším cyklem představuje pouze zjištění, že vkládaný prvek vlastně nikam "níže" vkládat nemusíme, protože je již na svém místě. Délka výpočtu v tomto nejlepším případě závisí na n pouze lineárně.

Složitost řazení "opakovaným výběrem minima"
A to už zkuste určit sami...

Úloha č. 21. Spočtěte, kolik elementárních operací - porovnání dvou hodnot - si vyžádá uspořádání pole o n prvcích metodou "opakovaného výběru minima".

"Živá" ukázka algoritmů řazení
Jako "třešničku na dortu" si ukažme, jak v reálu vypadá činnost některých řadicích algoritmů. Z nám známých je bude řazení "probubláváním" (Bubble Sort), řazení "výběrem minima" (Selection Sort) a z efektivních algoritmů řazení "rozdělováním" (Quick Sort). Demo je sestaveno jako Java applet (applets/demo.html). Aby demo fungovalo, je třeba v prohlížeči povolit provádění appletů.

8. "Výběrovky" ··· aneb abychom se po práci nenudili my ani naši žáci

S touto kapitolou si rozšíříte obzory za hranice "povinného" obsahu kurzu.

Poznáte typy úloh, jaké se mohou vyskytnout např. v zadáních programátorských soutěží (např. matematická olympiáda kategorie P).

Tyto úlohy budete moci zadávat nadaným žákům "navíc".

Tato sekce si neklade za cíl podat souvislý výklad o metodice výuky nadaných studentů. Uvádíme zde jen malý nástin toho, jak mohou vypadat "méně triviální" úlohy, které by však měly být řešitelné s programátorským aparátem zhruba srovnatelným s tím, co jsme právě prošli.

Úloha č. 22. Je dáno n slov. Jak dlouho lze hrát nad těmito slovy slovní kopanou "na první/poslední písmeno", když lze každé ze slov použít nejvýše jedenkrát (m-krát, ale to by nemělo být těžší).

Řešení úlohy vyžaduje znalost základních algoritmů nad grafy. Uzly grafu jsou v tomto případě představovány písmeny vyskytujícími se na začátku nebo konci některého ze slov. Slova potom představují hrany mezi těmito uzly (písmeny), vždy tak, že hrana (slovo) vychází z toho uzlu, na jehož písmeno slovo začíná, a vede do uzlu, na jehož písmeno slovo přiřazené hraně končí. Úkol se tímto převádí na problém nalezení nejdelší cesty v grafu.

Úloha č. 23. "LIFE" ve zjednodušené podobě. Program vygeneruje matici "černých a bílých" buněk (na každém políčku je současně nejvýše jedna buňka) a poté v každém "tiku" aktivuje jednu buňku. Ta, pokud může, ve spolupráci s jinou "svou" - stejné barvy - "sežere" nepřátelskou buňku umístěnou mezi nimi. (vodorovně nebo svisle, ne diagonálně)

Tento úkol není algoritmicky složitý. Klíčovou částí programu bude hlavní cyklus, který bude v každém průchodu realizovat jeden "tik simulačních hodin". V každém tiku se změní stav "světa" buněk, přesněji řečeno, může se změnit okolí právě aktivované buňky "sežráním" sousední buňky.

Úloha č. 24. Horolezec má několik lan, u každého je udána délka a celková cena lana. Dále má spojky, kterými lze spojit vždy dvě lana k sobě. Cena spojky je pro všechny stejná. Má za úkol vyrobit případným spojováním více lan jedno lano o zadané délce (nebo delší) tak, aby bylo co nejlevnější.

Úloha č. 25. Najděte nejkratší cestu ze zadaného města (uzlu) do jiného zadaného města. (použijte Dijkstrův algoritmus na hledání nejkratší cesty - viz Literatura: Libicher, I., Töpfer, P.: Od problému k algoritmu a programu)

K tomuto není co dodat. Jde skutečně o jeden ze základních algoritmických problémů z teorie grafů.

Úloha č. 26. Je dána úsečka (přímá cesta) s počátkem označeným 0 a délkou s. Na cestě je n bodů (čerpadel PHM), každý je dán dvojicí (Si, Pi), kde Si je vzdálenost bodu od počátku a Pi je, jednotková cena PHM v dané stanici. Auto má ve výchozím bodu nádrž o celkové kapacitě V naplněnu objemem V0. Navrhněte optimální schema tankování, aby celková útrata za PHM na cestě byla minimální.

Úloha č. 27. Je dána "krajina" složená z navazujících úseček daných krajními body o souřadnicích (s0,0), (s1, h1), (s2, h2),..., (sn, 0). Ze kterého bodu (si, hi) je vidět do krajiny nejdále?

Úloha č. 28. Firmě zbývá na konci roku x Kč, které musí co nejdůkladněji (s nejmenším zbytkem do dalšího roku) utratit. Skoro všechno už je vyprodané, takže má možnost koupit buďto výrobky A s cenou a Kč/ks nebo výrobky B s cenou b Kč/ks. Kolik čeho má koupit, aby jí zbylo nejméně Kč?

9. Přehled metodik analýzy problémů, návrhu a implementace programů ··· Moderní programovací nástroje

metodiky a zásady strukturovaného a objektového programování, jejich zvládnutí a vyučování; událostmi řízené programování, komponentně orientované programování

přehled tradičních a moderních programovacích nástrojů, vizuální a "internetové" programování

9.1. Jak se programování za poslední léta změnilo?

9.1.1. Změna úloh

Objevují se zcela nové oblasti využití výpočetní techniky, nastupují globální počítačové sítě - Internet a obecně se více pozornosti věnuje počítačům jako komunikačním nástrojům. Celkově se počítače mnohem více posunují běžným uživatelům - neodborníkům na ICT - v jejich každodenní praxi. Počítače se začínají masivněji využívat ve vzdělávání ne všech úrovních a typech škol.

Při veškeré bohatosti a relativní pohodlnosti obsluhy dnešních počítačů ovšem nelze říci, že by typický uživatel byl zcela zbaven nutnosti upravovat si pracovní prostředí v počítači, vytvářet si drobné pomůcky usnadňující mu opakované nebo pracné úkony, sestavoval si různé šablony, prezentační styly, vzory dokumentů apod.

9.1.2. Změna metodiky

Rostou požadavky na rychlost uvádění aplikací do provozu. Stále více se proto využívá prostředků typu RAD (Rapid Application Development), kde cílem není vytvořit zcela optimální program, ale program rychle navrhnout a zprovoznit.

Metodika se stále více posouvá na abstraktnější úroveň - už nenavrhujeme programy a datové struktury v konkrétním univerzálním programovacím nebo databázovém jazyku, ale modelujeme je ve speciálním nástroji, který sám zajistí jejich konečnou realizaci v požadovaném programovacím či databázovém jazyku. Více pozornosti se věnuje analýze problému, protože návrh a implementace programových a datových struktur je lépe automatizovatelná

9.1.3. Změna nástrojů

9.2. Moderní programování

Čím je charakteristické moderní programování?

• Komplexní metodiky konstrukce programů
• Posun k vyšším úrovním abstrakce
• Použití moderních (vizuálních) nástrojů
• Vysoká automatizace konstrukčního procesu
• Masivní spolupráce v rámci internetových komunit

9.2.1. Moderní programovací nástroje

Nové metodiky jsou také ve větší či menší míře podporovány moderními nástroji. Moderní vývojové nástroje nástroje podporují mj. tzv. vizuální programování, kdy část programu - typicky jeho uživatelské rozhraní - je tvořena modifikací existujících vizuálních komponent přímo na obrazovce pomocí myši.

Na obrázku níže vidíme dostatečně ilustrativního reprezentanta této třídy vývojových nástrojů - pokračovatele Pascalu - Delphi.

9.2.2. Moderní programovací jazyky

Úmyslně uvádíme moderní programovací jazyky až zde, po programovacích nástrojích, protože posun k abstraktnějším metodám návrhu znamená menší pozornost jednotlivým programovacím jazykům a příklon spíše k obecným postupům konstrukce programů, nevázaných na konkrétní jazyk.