5. Opakované výpočty

1. Podmínka  while
2. Zápis běhu programu
3. Počítání číslic
4. Zkrácené přiřazení
5. Tabelární data
6. Dvojrozměrné tabulky
7. Zapouzdření a zobecnění
8. Další zapouzdření
9. Lokální proměnné podruhé
10. Další zobecnění
11. Newtonova metoda
12. Algoritmy
13. Rekurze
14. Glosář
15. Cvičení

5.1 Podmínka  while

Počítače se často používají k automatickému výpočtu opakujících se úloh. Opakované provádění stejných nebo podobných úloh bez chyb je něco, co počítače dělají lépe než lidé.

Opakované provádění řady příkazů se nazývá iterace. Protože iterace se často používají, poskytuje Python několik nástrojů k jejich usnadnění. Nejprve se seznámíme s příkazem while (zatímco).

Použití příkazu while si ukážeme na funkci countdown:

def countdown(n):
    while n > 0:
        print(n)
        n = n-1
    print("Pal!")

Příkaz while se dá číst téměř jako prostý text: "Pokud bude n > 0, vytiskni hodnotu n a potom ji zmenši o 1. Když se dostaneš k 0, vytiskni slovo Pal!"

Formálněji popíšeme tok výpočtu s příkazem while takto:

1. Vyhodnoť podmínku while s výstupem False nebo True.
2. Je-li hodnocení False, vystup ze smyčky while a pokračuj dalším příkazem.
3. Je-li hodnocení True, proveď všechny příkazy v těle podmínky a vrať se ke kroku 1.

Tělo podmínky tvoří všechny příkazy pod záhlavím se stejným odsazením.

Tento typ toku programu se nazývá smyčka, protože se ve třetím kroku vracíme k počátku. Uvědomme si, že když je podmínka nepravdivá již při prvním běhu smyčkou, příkazy uvnitř smyčky se nikdy neprovedou.

Tělo smyčky by mělo měnit hodnotu jedné či více proměnných tak, aby se podmínka nakonec stala nepravdivou a smyčka skončila. Jinak by se opakovala do nekonečna, a byla by to nekonečná smyčka. Nekonečný zdroj zábavy pro programátory jsou poznámky na adresu některých reklamních výzev, jako je "Namydli, spláchni, opakuj", což je neuzavřený cyklus, neboli nekonečná smyčka.

V případě funkce countdown můžeme dokázat, že smyčka končí, protože víme, že hodnota n je konečná a že se při každém průchodu smyčkou zmenšuje, takže nakonec se musíme dostat k nule. V jiných případech to tak zřejmé být nemusí.

def sequence(n):
    while n != 1:
        print(n)
        if n%2 == 0:       # n is even
            n = n/2
        else:              # n is odd
            n = n*3+1

Podmínkou pro tuto smyčku je n!=1, takže bude rotovat tak dlouho, dokud nebude n=1, čímž se stane podmínka nepravdivá.

Při každém průchodu smyčkou program vrácí hodnotu n a zkontroluje, je-li sudá či lichá. Je-li sudá, je n děleno 2. Je-li lichá, nahradí se hodnotou n*3+1. Například, pro sequence(3) je výsledná posloupnost 3, 10, 5, 16, 8, 4, 2 .

Protože se n někdy zvětšuje, jindy zmenšuje, nemáme zřejmý důkaz, že n někdy dospěje k 1, nebo že program skončí. Pro jisté hodnoty n můžeme ukončení dokázat. Například, bude-li počáteční hodnotou mocnina 2, bude n stále sudé, dokud nedospěje k 1. V předchozím případě výsledná posloupnost takovou řadu (počínající číslem 16) obsahuje.

Odhlédneme-li od zmíněných čísel, je na místě otázka, zda umíme dokázat, že tento program je konečný pro všechny hodnoty n. Zatím se to nikomu nepodařilo!

5.2 Zápis běhu programu

K efektivnímu psaní počítačových programů potřebuje programátor vyvinout schopnost zaznamenat průběh běžícího programu. Znamená to "stát se počítačem" a sledovat průběh provádění, zaznamenávajíc stavy všech proměnných a všechny výstupy, které program generuje po provedení jednotlivých instrukcí.

Abychom porozuměli tomuto procesu, sledujme volání funkce sequence(3) z předchozího odstavce. Na počátku záznamu máme lokální proměnnou n (parametr funkce) s počáteční hodnotou 3. Protože 3 není totožné 1, provede se smyčka while. Číslo 3 je tištěno a 3%2 == 0 je hodnoceno. Protože je vyhodnoceno jako False, provede se větev else, kde se hodnota výrazu 3*3+1 přiřadí k  n.

Při ručním zápisu si pro každou proměnnou a výstup vytvoříme záhlaví sloupce; v našem příkladě asi takto:

   n              output
  ---             ------
   3                 3
   10

Protože 10 != 1 se vyhodnotí jako True, provádí se opět tělo smyčky a tiskne se 10. Jelikož podmínka 10%2 == 0 je pravdivá, provádí se větev if a n získává hodnotu 5. Na konci záznamu máme:

   n              output
  ---             ------
   3                 3
   10                10
   5                 5
   16                16
   8                 8
   4                 4
   2                 2
   1

5.3 Počítání číslic

Následující funkce spočítá počet číslic kladného celého čísla v desetinném formátu:

def num_digits(n):
    count = 0 
    while n:        # totéž jako while n != 0:
        count = count+1
        n = n//10    # celočíselné dělení
    return count

Volání num_digits(710) vrátí 3.

Na této funkci si můžeme ukázat další prvek výpočtu zvaný počítadlo (accumulator). Proměnná count je zavedena s hodnotou 0 a potom zvětšována o 1 při každém provedení smyčky. Když smyčka skončí, obsahuje count výsledek - celkový počet provedení (cyklů) smyčky, což je také počet číslic zadaného čísla.

Kdybychom chtěli počítat jenom číslice s hodnotou 0 nebo 5, pomůžeme si přidáním podmínky před zvyšováním stavu počítadla:

def num_zero_and_five_digits(n):
    count = 0
    while n:
        digit = n%10
        if digit == 0 or digit == 5:      
            count = count+1
        n = n//10
    return count

5.4 Zkrácené přiřazení

Zvětšování proměnné je tak běžné, že pro něj Python poskytuje zkrácenou syntaxi:

>>> count = 0
>>> count += 1
>>> count
1
>>> count += 1
>>> count
2
>>> 

>>> n = 2
>>> n += 5
>>> n
7
>>> 

>>> n = 2
>>> n *= 5
>>> n
10
>>> n -= 4
>>> n
6
>>> n /= 2
>>> n
3
>>> n %= 2
>>> n
1

5.5 Tabelární data

Jedním z vhodných použití smyčky je generování tabelárních dat. Předtím, než byly počítače běžně přístupné, musely být logaritmy, siny, kosiny a jiné funkce čísel počítány ručně. Pro ulehčení výpočtu obsahovaly matematické příručky dlouhé tabulky s uspořádanými hodnotami těchto funkcí. Vytváření tabulek bylo zdlouhavé, nudné a občas plné chyb.

Když se na scéně objevily počítače, jedna z prvních reakcí byla: "Sláva! Můžeme tvořit tabulky na počítači, který nedělá chyby." To se ukázalo být (většinou) pravdivé, ale i krátkozraké. Brzy nato se staly kalkulátory a počítače tak všudepřítomné, že se tabulky staly zbytečné.

Tedy téměř. Pro některé operace používají počítače tabulky hodnot jako přibližnou mezihodnotu, kterou potom v dalším výpočtu upřesňují. Někdy byly chybné právě tyto tabulky; nejproslulejší jsou ty, které Intel Pentium používal k výpočtu dělení v plovoucí řádové čárce.

Při sestavování tabulek se prováděly opakované výpočty pro monotónně měněné vstupní hodnoty. Příkladem opakovaného výpočtu budiž následující program, který vytvoří posloupnost hodnot v levém sloupci a příslušné mocniny čísla 2 v pravém:

x = 1
while x < 13:
    print(x, '\t', 2**x)
    x += 1

Řetězec '\t' zastupuje znak tab, neboli tabulátor. Zpětné lomítko označuje začátek "escape" sekvence, což je pořadí několika určených znaků, které nahrazují neviditelné znaky např. pro tab nebo nový řádek ('\n').

"Escape" sekvence se může použít kdekoliv v řetězci; v našem příkladě je v řetězci pouze znak pro tab. (Jak zapíšeme zpětné lomítko v řetězci?)

Jak jsou postupně znaky a řetězce zobrazovány na obrazovce, jsou kontrolovány neviditelným hlídačem, zvaným kurzor, který zaznamenává jejich polohu.

Znak pro tabulátor posune kurzor doprava k nejbližší pomyslné zarážce. Tabulátory jsou vhodné pro tvorbu uspořádaných řádků, jako má tento výstup z předchozího programu:

1       2
2       4
3       8
4       16
5       32
6       64
7       128
8       256
9       512
10      1024
11      2048
12      4096

Protože mezi sloupci máme znaky tab, není pozice druhého sloupce závislá na počtu číslic v prvním sloupci.

5.6 Dvojrozměrné tabulky

Dvojrozměrná tabulka je tabulka ve které odečítáme údaje v průsečíku řádku a sloupce. Dobrým příkladem je tabulka násobení. Řekněmež, že chceme zobrazit tabulku pro násobení čísel od 1 do 6.

Dobrým začátkem je zápis smyčky, která vytiskne všechny násobky dvou na jeden řádek:

i = 1
while i <= 6:
    print(2*i, "\t", end="")
    i += 1
print()

První řádek vytvoří proměnnou i, která působí jako počítadlo, neboli proměnnou smyčky. Při procházení smyčkou se hodnota i zvětšuje od 1 do 6. Při každém průchodu se vytiskne hodnota 2*i, následovaná mezerou tabelátoru.

Přechod na nový řádek ve funkci print potlačí instrukce end=" ". Po ukončení smyčky vytiskne funkce print() nový řádek.

Výstup programu je tento:

>>> 
2   4   6   8   10   12
>>>

Výborně, jen tak dál. Dalším krokem bude zapouzdření a generalizace.

5.7 Zapouzdření a zobecnění

Zapouzdření je proces zabalení části kódu do funkce, umožňující využít všechny výhody, kterými funkce disponují. Viděli jsme již dva příklady zapouzdření: print_parity a is_divisible v kapitole 4.

Zobecněním se míní přetvoření určité funkce, jako je například tvorba násobků dvou tak aby tiskla násobky jakéhokoliv čísla.

Následující funkce zapouzdří předchozí smyčku a zobecní ji tak aby vracela násobky  n.

def print_multiples(n):
    i = 1
    while i <= 6:
        print(n*i, "\t", end="")
        i += 1
    print()

Všechno, co jsme pro zapouzdření museli udělat bylo to, že jsme přidali záhlaví funkce s parametrem  n.

Zavoláme-li tuto funkci pro argument 2, dostaneme stejný výstup jako předtím. Pro argument 3 obdržíme:

>>>
3    6    9    12   15   18
>>>

Pro argument 4 je výstup:

>>>
4    8    12    16   20   24
>>>

Nyní patrně už umíme odhadnout jak vytvořit tabulku pro násobení - opakovaným voláním print_multiples pro různé argumenty. Vlastně můžeme použít ještě jednu smyčku:

i = 1
while i <= 6:
    print_multiples(i)
    i += 1

Všimněme si, jak podobná je tato smyčka té, která je uvnitř print_multiples. Výměna funkce print voláním funkce print_multiples bylo vše, co jsme učinili.

Výstup tohoto programu je tabulka pro násobení:

>>>
1    2    3     4    5    6 
2    4    6     8    10   12
3    6    9     12   15   18
4    8    12    16   20   24
5    10   15    20   25   30
6    12   18    24   30   36
>>>

5.8 Další zapouzdření

Abychom si ještě jednou předvedli zapouzdření, vezměme kód z předcházejícího odstavce a zabalme jej do funkce:

def print_mult_table():
    i = 1
    while i <= 6:
        print_multiples(i)
        i += 1

Tento proces je běžná rozvojová metoda. Vytvářený kód zapisujeme do řádků mimo funkci, případně jej zkoušíme v překladači (IPP). Jakmile nám chodí, zabalíme jej do funkce.

Tato metoda je zvláště užitečná, když na počátku ještě nevíme, jak program do funkcí rozdělit. Program tak vzniká postupným vývojem.

5.9 Lokální proměnné podruhé

Proměnné, vytvořené uvnitř funkce jsou lokální; mimo svou domovskou funkci nejsou přístupné. Můžeme tedy mít více proměnných se stejným jménem, pokud se neobjeví ve stejné funkci.

Funkce print_mult_table volá funkci print_multiples, přičemž v obou funkcích se vyskytuje proměnná se stejným jménem i.

Zobrazení zásobníku pro tento program ukazuje, že proměnné i ve skutečnosti nejsou tytéž. Vztahují se k různým hodnotám a změna jedné neovlivní druhou (v kapitole 10.4 se dozvíme, že každá funkce má svůj vlastní jmenný prostor).

Hodnota i v print_mult_table se mění od 1 do 6. Ve schematu to je aktuálně 3. V příštím cyklu smyčky to bude 4. Při každém cyklu volá print_mult_table funkci print_multiples s aktuální hodnotou i jako argumentem. Tato hodnota se přiřadí parametru n.

Uvnitř funkce print_multiples se hodnota i mění také od 1 do 6. Ve schematu to je aktuálně 2. Změna této hodnoty nemá žádný vliv na hodnotu i v print_mult_table

Je obvyklé a zcela legální používat různé lokální proměnné se stejným jménem. Zvláště jména i a j se často používají jako proměnné smyčky. Vyhýbat se jim v jedné funkci, protože jsme je použili v jiné, může vést ke zhoršené čitelnosti programu.

5.10 Další zobecnění

Pro další příklad zobecnění předpokládejme, že chceme program, který by vytiskl tabulku násobení jakékoliv velikosti, nikoliv pouze šest krát šest. Můžeme přidat parametr do print_mult_table:

def print_mult_table(high):
    i = 1
    while i <= high:
         print_multiples(i)
         i = i + 1

Hodnotu 6 jsme nahradili parametrem high. Zavoláme-li print_mult_table(7), zobrazí se:

>>>
1    2    3    4    5    6 
2    4    6    8    10   12
3    6    9    12   15   18
4    8    12   16   20   24
5    10   15   20   25   30
6    12   18   24   30   36
7    14   21   28   35   42
>>>

To je prima, až na to, že asi chceme, aby byla tabulka čtvercová - se stejným počtem řádků jako sloupců. Zajistíme to přidáním dalšího parametru do print_multiples abychom určili, kolik sloupců by tabulka měla mít.

Tento parametr schválně nazveme high, abychom předvedli, že různé funkce mohou mít parametr se stejným jménem (stejně jako lokální proměnné). Zde je celý program:

def print_multiples(n,high):
    i = 1
    while i <= high:
        print(n*i, "\t", end="")
        i += 1
    print()

def print_mult_table(high):
    i = 1
    while i <= high:
        print_multiples(i, high)
        i += 1

Povšimněme si, že s přidáním nového parametru jsme museli změnit první řádek funkce (záhlaví funkce), a také jsme museli změnit místo, kde je funkce v print_mult_table volána.

Dle očekávání generuje program čtvercovou tabulku 7x7:

>>>
1    2    3    4    5    6    7
2    4    6    8    10   12   14
3    6    9    12   15   18   21
4    8    12   16   20   24   28
5    10   15   20   25   30   35
6    12   18   24   30   36   42
7    14   21   28   35   42   49
>>>

Provedeme-li zobecnění vhodným způsobem, často dostaneme program se schopnostmi, které jsme nezamýšleli. Například si lze všimnout, že v důsledku toho, že ab = ba, všechny hodnoty se v tabulce opakují dvakrát. Mohli bychom ušetřit inkoust kdybychom tiskli jen polovinu tabulky. Zařídíme to pouhou změnou jednoho řádku v print_mult_table. Změňme

print_multiples(i, high)

na

print_multiples(i, i)

a obdržíme

>>>
1
2    4
3    6    9
4    8    12   16
5    10   15   20   25
6    12   18   24   30   36
7    14   21   28   35   42   49
>>>

5.11 Newtonova metoda

Smyčky jsou časo užívány v programech, které spočítají výsledek tak, že začnou s přibližnou hodnotou a opakovaným výpočtem výsledek zpřesňují.

Například, jedním ze způsobů počítání druhé odmocniny čísla je Newtonova metoda. Při určení odmocniny čísla n začneme vpodstatě libovolnou aproximací (přibližnou hodnotou), kterou zpřesníme pomocí tohoto vzorce:

better = (approx + n/approx)/2

Výpočet se opakuje tak dlouho, až se zpřesněná hodnota téměř neliší od předchozí. Pro provádění výpočtu napíšeme funkci:

def sqrt(n):
    approx = n/2.0
    better = (approx + n/approx)/2.0
    while better != approx:
        approx = better
        better = (approx + n/approx)/2.0  
    return approx

5.12 Algoritmy

Newtonova metoda je příkladem algoritmu - mechanického způsobu řešení jisté kategorie problémů (v našem případě počítání druhé odmocniny).

Definovat algoritmus není snadné. Když jsme se učili násobit jednomístná čísla, tak jsme se vlastně naučili 100 konkrétních řešení.

Pokud jsme však byli "líní", mohli jsme se naučit několika trikům. Například, pro součin čísla n a 9 zapíšeme n-1 jako první číslici a 10-n jako druhou číslici výsledku. Tento trik je obecným řešením pro násobení libovolného jednomístného čísla číslem 9. Toto je algoritmus!

Podobnými algoritmy jsou techniky, které jsme se naučili pro sčítání s převáděním, odčítání s půjčováním a dělení. Jedním z rysů algoritmu je, že ke svému provedení nevyžaduje nadměrnou inteligenci. Jsou to mechanické procesy, kde jeden krok vyplývá z předchozího podlé jednoduchého souboru pravidel.

Dle našeho názoru je zarážející, že lidé stráví tolik času ve škole pro zvládnutí algoritmů, které vlastně nevyžadují žádnou inteligenci.

Proces navrhování algoritmu je na druhé straně zajímavý, intelektuálně náročný a je středobodem toho, čemu říkáme programování.

Některé věci, které lidé dělají zcela přirozeně, bez potíží a nevědomky, se nejobtížněji vyjadřují algoritmicky. Dobrým příkladem je chápání přirozeného jazyka. Všichni jej používáme, ale dosud nebyl nikdo schopen vysvětlit jak to děláme, přinejmenším ne v algoritmické formě.

5.13 Rekurze

Hovoříme-li o opakovaných výpočtech, nelze pominout rekurzivní volání funkcí. Toto téma je podrobně probíráno ve čtyřech odstavcích 13. kapitoly. Na tomto místě je uvedena pouze základní informace.

Rekurze je technika, při které funkce volá samu sebe. Funkci countdown(n) můžeme s pomocí rekurze zapsat takto:

def countDown(n):
    if n < 1:      # Základní (mezní) případ 
        return
    print(n)
    countDown(n-1)

Správně definovaná rekurze vyhovuje těmto dvěma požadavkům:

• Má deklarovaný základní případ u kterého opakovaný výpočet končí
• Hodnota argumentu rekurzivního volání směřuje k hodnotě základního případu

Pomocí rekurze lze elegantně počítat například hodnotu faktoriálu (n!) nebo Fibonacciho čísla (viz odst. 13.2).

Alternativou k rekurzivnímu opakovanému výpočtu je iterativní výpočet (viz odst. 13.4) pomocí idiomu

    FOR i in ITERABLE:
        do something - např. print(i)	

5.14 Glosář

5.15 Cvičení