Počítač za mě řeší opakované úkoly

Co se naučíš:

• Nechat počítač opakovat nějakou činnost po celou dobu, kdy je splněna nějaká podmínka (např. dokud není s něčím hotov), pomocí tzv. while cyklu.
• Využít cyklu k systematickému postupnému vyřešení problému po jednotlivých menších krocích.
• Vzájemně cykly vnořovat: opakovaným krokem cyklu může být provedení „menšího“ cyklu, s vlastními opakovanými „malými“ kroky.

Program s hádankou z předchozí kapitoly by zasloužil rozšířit. Co když uživatel očekávanou odpověď zná, ale jen se překlepl? Mohli bychom mu dát šanci se opravit — a ptát se ho prostě do té doby, dokud správně neodpoví.

Úloha:

Sestroj vývojový diagram opakovaného hádání až do uhodnutí.

Řešení

Vývojový diagram může vypadat např. takto:

Nezapomeň svůj diagram aspoš krátce vyzkoušet, aby bylo jasné, jestli funguje správně.

Příklad: Hádání až do uhodnutí

V Pythonu bude očekávaným způsobem fungovat např. následující zdrojový kód (nezapomeň doplnit správné řešení hádanky).

1 def Hadanka () :
2 	ZadaniHadanky = "Syn muze na obrazku je syn meho otce. Kdo je na obrazku?"
3 	SpravnaOdpoved = *zde dopln spravnou odpoved*
4 
5 	OdpovedUzivatele = input (ZadaniHadanky)
6 	while OdpovedUzivatele != SpravnaOdpoved :
7 		print("Je mi lito, to neni spravne.")
8 		OdpovedUzivatele = input ("Zkus to znovu:")
9 	print("Spravne, dobra prace!")

Vlož zdrojový kód na příslušné místo v interaktivní konzoli, doplň správnou odpověď a prozkoušej, co dělá!

while cyklus

Terminologie

Koncept cyklu je v informatice velmi důležitý a najdou se pro něj různá označení. Neměla by tě zmást: cyklus, opakování, smyčka, iterace, anglické loop. While cyklu se jinak říká také cyklus řízený podmínkou nebo cyklus s neznámým počtem opakování (protože předem zpravidla není jasné, kolikrát bude třeba tělo cyklu provést).

Vidíš, že se program dokolečka vyptává na řešení hádanky, dokud uživatel nezadá očekávanou správnou odpověď. Ve zdrojovém kódu také vidíš nové klíčové slovo while a za ním podmínku, podobně jako to znáš s if. A funguje to podobně: podmínka je vyhodnocena, a pokud platí, provede se odsazený zdrojový kód. Rozdíl je, že po dokončení odsazené části kódu (tzv. těla cyklu) se program vrátí zpátky k podmínce, znovu ji vyhodnotí, a tohle opakuje dokud je podmínka splněna. Až se program podmínku vyhodnotí a ona platit nebude, tělo cyklu víckrát neprovede a v práci bude pokračovat dál.

Pro podmínky platí stejné podmínky jako v případě rozhodování: musí to být nějaký výraz, který lze vyhodnotit na True nebo False.

While cyklus je takřka všude

While cyklus řídí např. mnoho počítačových her. Dokud není konec (třeba dokud není splněn úkol), provádí se jedno „kolo“: načte a zpracuje se vstup od hráče, o malý kousek se změní polohy postaviček atp. a nová situace se vykreslí na displej. Podobná hlavní smyčka funguje i v operačním systému. Sice to vypadá, že třeba plynule pohybuješ ukazatelem myši, ve skutečnosti ale jen počítač rychle vyhodnocuje drobné pohyby a zobrazuje změny — dokud systém nevypneš.

Počítání opakování

Neomezená možnost hádání je možná příliš. Co třeba dát pokusy jen tři?

Odstrašující příklad: Hádanka na tři pokusy

Mohli bychom samozřejmě prostě třikrát zopakovat stejný kousek zdrojového kódu, třeba takhle:

 1 def Hadanka() :
 2 	ZadaniHadanky = "Cihla vazi kilo a pul cihly. Kolik kil vazi cihla?"
 3 	SpravnaOdpoved = *zde dopln spravnou odpoved*
 4 	OdpovedUzivatele = input (ZadaniHadanky)		# prvni pokus
 5 	if OdpovedUzivatele == SpravnaOdpoved :
 6 		print("Spravne, dobra prace!")
 7 		return
 8 	print("Je mi lito, to neni spravne.")	# vetev "if" ma na konci return, takze tento radek se provede jen pri nesplneni podminky
 9 	OdpovedUzivatele = input ("Zkus to znovu:")		# druhy pokus
10 	if OdpovedUzivatele == SpravnaOdpoved :
11 		print("Spravne, dobra prace!")
12 		return
13 	print("Je mi lito, to neni spravne.")
14 	OdpovedUzivatele = input ("Zkus to znovu:")		# treti pokus
15 	if OdpovedUzivatele == SpravnaOdpoved :
16 		print("Spravne, dobra prace!")
17 		return
18 	print("Je mi lito, to neni spravne.")

Asi je ti ale jasné, že takový postup není zrovna šťastný. Je to nepřehledné. Když se rozhodnu upravit odpovědi, tak je musím upravit na několika místech. Když chci změnit povolený počet hádání, tak musím přidávat nebo ubírat zdrojový kód, i když na principu úlohy se nic nemění. Informatici se prostě snaží zbytečně neopakovat, takže s uvedeným kódem nemohou být spokojeni.

Příklad: Omezení počtu pokusů efektivně

Jak tedy omezení počtu pokusů naprogramuje informatik? Zamyslí se, jak by stejný úkol řešil ve „skutečném“ světě. Mohl by postupovat třeba tak, že by si pamatoval počet zbývajících pokusů a postupně je odčítal. Skončil by v případě, kdy hadač uhodl odpověď, nebo vyčerpal pokusy. Napadá tě jiný možný postup?

 1 def Hadanka() :
 2 	# inicializace - to je napr. nastaveni rozlicnych pocatecnich hodnot
 3 	ZadaniHadanky = "Cihla vazi kilo a pul cihly. Kolik kil vazi cihla?"
 4 	SpravnaOdpoved = *zde dopln spravnou odpoved*
 5 	ZbyvajiciPokusy = 3
 6 	
 7 	# hadani
 8 	OdpovedUzivatele = input (ZadaniHadanky)		# prvni pokus
 9 	ZbyvajiciPokusy = ZbyvajiciPokusy - 1			# zapocitam probehly pokus
10 	while OdpovedUzivatele != SpravnaOdpoved and ZbyvajiciPokusy > 0:
11 		print("Je mi lito, to neni spravne. Zbyvajici pokusy:", ZbyvajiciPokusy)
12 		OdpovedUzivatele = input ("Zkus to znovu:")	# dalsi pokus
13 		ZbyvajiciPokusy = ZbyvajiciPokusy - 1		# zapocitam probehly pokus
14 	
15 	# zaverecne vyhodnoceni - bud je uhodnuto, nebo dosly pokusy
16 	if OdpovedUzivatele == SpravnaOdpoved :
17 		print("Spravne, dobra prace!")
18 	else:
19 		print("Je mi lito, povolene pokusy jsou vycerpany.")

Který z posledních dvou zdrojových kódů ti připadá lepší? Proč?

Který program vyniká jakými vlastnostmi, a které vlastnosti programu upřednostňuješ? Uvažuj např.:

• Srozumitelnost
• Stručnost, úspornost, počet použitých řádků
• Rychlost provedení programu, množství využité paměti, počet použitých proměnných
• Snadnost případných úprav
• Dostatek komentářů

Úloha: Sestroj vývojový diagram hádání s omezením počtu pokusů.

Řešení

Příklad vývojového diagramu, který odpovídá uvedenému zdrojovému kódu (není to ale jediné možné řešení)

Se situací, kdy je třeba něco počítat (tak jako zde pokusy), se v informatice setkáš dost často. Dobře si proto všimni, jak a kde všude s proměnnou ZbyvajiciPokusy pracujeme:

• Nejprve je třeba nastavit výchozí hodnotu (jinak není odkud počítat).
• Na začátku každého opakování kontrolujeme, jestli už pokusy nejsou vyčerpány.
• Nezapomeneme každý pokus započítat, tedy upravit hodnotu proměnné ZbyvajiciPokusy.
• Proměnnou navíc můžeme využít k informování uživatele o tom, kolik pokusů mu ještě zbývá.

Opakované zmenšování problému

Někdy while cyklus využijeme k řešení problému tak, že problém postupně zmenšujeme a zmenšujeme, až je řešení jasné a plyne z něj i řešení původního „velkého“ problému.

Příklad: Počet potřebných otázek k uhodnutí (bitů k zakódování) jedné z daného počtu možností

V kapitole o informaci jsme došli k tomu, že počet bitů nutných k určení jedné možnosti z daného počtu odpovídá počtu otázek, kterými počet možností vždy o polovinu snižujeme (jestli potřebuješ, připomeň si to!). To nám dává návod na výpočet. Předpokládejme pro začátek, že všechno pěkně vychází a pokaždé můžeme půlit přesně.

Například při 32 možnostech bude půlení postupovat takto:

1. 32 není jedna, takže musíme aspoň jednu otázku položit. Položíme ji chytře, takže odpověď na ni ubere polovinu možností (získáme jeden bit informace). 32/2=16
2. 16 také není jedna, takže možnosti rozpůlíme další otázkou (nebo bitem). 16/2=8.
3. 8 také není jedna, půlíme dál: 8/2=4.
4. 4 možnosti opět rozdělíme: 4/2=2.
5. Ze 2 možností další otázkou jednu vyloučíme, zbyde 1.
6. Došli jsme k poslední možnosti, není se tedy na co ptát. Potřebovali jsme k tomu 5 půlení.

Jak tohle naprogramovat? Mohli bychom přímo zakódovat, jak vlastně výpočet probíhá:

def PocetBitu( PocetMoznosti ) :
	PocetPuleni = 0
	if PocetMoznosti == 1:	# uz jsme hotovi a koncime, nebo budeme pulit?
		return PocetPuleni
	else :
		PocetMoznosti = PocetMoznosti / 2
		PocetPuleni = PocetPuleni + 1
	if PocetMoznosti == 1:	# uz jsme hotovi a koncime, nebo budeme pulit?
		return PocetPuleni
	else :
		PocetMoznosti = PocetMoznosti / 2
		PocetPuleni = PocetPuleni + 1
	... atd. ...

Je vidět, že se postup kromě začátku opakuje stále dokola, dokud nejsme na konci výpočtu. Myšlenka vypadá slibně, ale by dobré se zbavit nutnosti kopírovat dokola tentýž nebo podobný kousek zdrojového kódu.

Úloha: Formulace postupu

• Zformuluj pečlivě (jako algoritmus, slovy, vývojovým diagramem nebo rovnou jako program) postup pro výpočet nejmenšího jistě postačujícího počtu otázek (se dvěma možnostmi odpovědi) k určení jedné z daného počtu možností. Nadále předpokládej, že půlit lze přesně.
• Soustřeď se na přesné určení toho, co se v postupu opakuje, co se při každém opakování mění a za jakých podmínek opakování končí.
• Ověř správnost svého postupu na příkladech (tzv. testovacích datech — na 2 možnosti je třeba jediná otázka, na 8 možností 3 otázky atp.).

Nápověda

• Opakuje se půlení, tedy snižování počtu možností.
• Půlení počítáme, příslušná proměnná postupně roste.
• Cyklus opakujeme, dokud zbývá víc než jedna možnost.

Řešení

Popis svými slovy:

1. Spočti zbylé možnosti. Pokud zbývá jediná, je hotovo. Odpovědí je celkový počet provedených půlení.
2. Pokud zbývá víc než jedna možnost, sniž jejich počet na polovinu a započti jedno půlení.
3. Pokračuj bodem 1.

Vývojový diagram uvedeného postupu

Jak by vypadalo řešení s cyklem? Naprogramujeme jeden z možných postupů. Vychází přímo z předchozího zdrojového kódu, takže simuluje průběh dotazování. Dělí možnosti na poloviny a počítá, kolikrát bylo třeba dělit, než zbyla jediná možnost. Výsledný počet půlení odpovídá počtu otázek (resp. bitů) potřebných k jednoznačnému určení jedné z možností.

def PocetBitu(PocetMoznosti) :
    PocetPuleni = 0
    while PocetMoznosti != 1:
        PocetMoznosti = PocetMoznosti / 2
        PocetPuleni = PocetPuleni + 1
    return PocetPuleni

Vlož zdrojový kód do interaktivní konzole a vyzkoušej, jestli funguje správně.

Náš program má ovšem jednu zásadní nevýhodu. Počítá správně jen v případě, že je počáteční počet možností mocninou dvou. Abychom mohli počítat potřebné otázky pro obecný počet možností, potřebujeme rozlišit případy s lichým počtem (kdy je třeba uvažovat „větší“ polovinu, tedy zaokrouhlit výsledek dělení nahoru). Jak ale rozpoznat sudost a lichost čísla? To zjistíš v příští kapitole.

Opakování opakování

Opět podobně jako v případě rozhodování (if), i while můžeme zanořovat. Při každém opakování cyklu tak proběhne několik opakování vnořeného „menšího“ cyklu. Jednoduchým příkladem je stavba cihlové zdi nebo okopávání záhonu. Zeď stavíme po jednotlivých řádcích, a jednotlivé řádky stavíme po jednotlivých cihlách. Podobně každou rýhu v záhoně okopáváme stejným způsobem (tedy opakovaně), a samotné okopávání jedné rýhy se opět skládá z opakovaných úkonů.

Příklad: Stavební robot

Jednoduchý program pro robota na stavbu zdí by mohl vypadat takto:

1 def PostavZed (CilovaVyska, CilovaSirka) :
2 	AktualniVyska = 0
3 	while AktualniVyska < CilovaVyska :	# tedy "dokud nemame dost vysokou zed"
4 		AktualniSirka = 0			# zacneme novy radek
5 		while AktualniSirka < CilovaSirka :	# dokud neni radek hotov
6 			PrilozDoRadkuCihlu(AktualniVyska, AktualniSirka)	# prilozime cihlu k cihle
7 			AktualniSirka = AktualniSirka + 1	# prilozenou cihlu pripocteme k sirce radku
8 		AktualniVyska = AktualniVyska + 1		# radek je hotov, zase mame o kus vyssi zed

Tohle je ale jednoduché, proto si hned ukážeme o trošku složitější příklad.

Příklad: Výpočet ciferace

Vznikající program

Učebnice sice nabízí několik fází vývoje programu, ideální ale bude studentům živě předvést, jak program tvoříte.

Ciferace je výsledek počítání ciferného součtu, dokud je co sčítat. Například z čísla 849 získáme ciferný součet 8+4+9=21, ale cifry čísla 21 lze znovu sečíst, čímž už dostaneme výslednou ciferaci, 2+1=3. Ciferace se hodí např. při určování dělitelnosti třemi a devíti nebo při kontrole správnosti výpočtu.

Dokážeš přesně popsat postup výpočtu ciferace? Zkus si několik příkladů a sleduj, které kroky se opakují a za jakých podmínek. Zde uvedeme jedno možné řešení.

Zjistíš, že opakuješ počítání ciferného součtu, dokud nedosáhneš jednociferného čísla. Samotný ciferný součet získáváš postupným sčítáním jednotlivých cifer. Je třeba trocha přemýšlení, abychom přiměli Python pracovat s ciframi pomocí operátorů, které už známe.Výsledný program by se mohl vyvíjet např. takto:

1 def Ciferace ( n ) :
2     dokud je n viceciferne...
3         spocti ciferny soucet
4         pouzij soucet jako novou hodnotu
5     vrat vyslednou hodnotu

1 def Ciferace ( n ) :
2     while n >= 10 :	#dokud je n viceciferne...
3         # spocti ciferny soucet
4         Soucet = 0
5         dokud zbyvaji cifry...
6             nejakou cifru pricti k souctu a odeber z cisla
7         # pouzij soucet jako novou hodnotu
8         n = Soucet
9     return n	# vrat vyslednou hodnotu

 1 def Ciferace ( n ) :
 2     while n >= 10 :	#dokud je n viceciferne...
 3         # spocti ciferny soucet
 4         Soucet = 0
 5         while n != 0 :	# dokud zbyvaji cifry...
 6             pricti k dosavadnimu souctu posledni cifru 
 7             odstran posledni cifru z pracovni hodnoty n
 8         # pouzij soucet jako novou hodnotu
 9         n = Soucet
10     return n	# vrat vyslednou hodnotu

 1 def Ciferace ( n ) :
 2     while n >= 10 :	#dokud je n viceciferne...
 3         # spocti ciferny soucet
 4         Soucet = 0
 5         while n != 0 :	# dokud zbyvaji cifry...
 6             # pricti k dosavadnimu souctu posledni cifru (zbytek po deleni deseti)
 7             PosledniCifra = (n % 10)
 8             Soucet = Soucet + PosledniCifra
 9             # odstran posledni cifru z pracovni hodnoty n
10             n = n - PosledniCifra
11             n = n / 10
12         # pouzij soucet jako novou hodnotu
13         n = Soucet
14     return n	# vrat vyslednou hodnotu

Na posupném vývoji zdrojového kódu je patrné, že programy obvykle nepíšeme „od začátku do konce“. Místo toho začneme přibližnou hrubou strukturou, která často ani není napsaná v cílovém programovacím jazyce. Zápis postupně zpřesňujeme, doplňujeme detaily a „překládáme“ do programovacího jazyka. Začít rovnou psát hotový zdrojový kód je zejména pro začátečníky zbytečně obtížné, přitom k tomu není důvod. Mnohem lepší je pracovat postupně, po malých krůčcích. Efektivními postupy vytváření zdrojového kódu se zabývá oblast zvané softwarové inženýrství.

Jinou variantu programu získáme, když si uvědomíme, že se při výpočtu často používá ciferný součet. Mohli bychom ho tedy počítat v samostatné funkci, tak jej oddělíme. Výsledek může někomu připadat srozumitelnější (dělá ovšem to samé — přesvědč se o tom!):

 1 def CFS (c) :
 2 	Soucet = 0
 3 	while c != 0 :
 4 		PosledniCifra = (c % 10)
 5 		Soucet = Soucet + PosledniCifra
 6 		c = c - PosledniCifra
 7 		c = c / 10
 8 	return c
 9 
10 def Ciferace ( n ) :
11 	while n >= 10 :
12 		n = CFS (n)
13 	return n

Shrnutí

• K opakování nějaké činnosti dokud platí zadaná podmínka slouží while cyklus. Podmínka se zadává stejně, jako to už znáš u rozhodování if.
• Cyklus while se často hodí k postupnému řešení problému po jednotlivých, malých (čili snáze zvládnutelných) a vzájemně podobných krocích, dokud nedojdeme do cíle.
• Jednotlivé konstrukce lze kombinovat, např. v rámci každého opakování while rozhodovat pomocí if, nebo dokonce umístit opakování v rámci opakování. Tak vznikají složitější programy.

Úlohy

Prozatím aspoň několik námětů:

• Naprogramuj cvičně základní početní operaceSčítání a odčítání (pomocí přičtení či odečtení jedničky), násobení a mocnění, dělení pro přirozená čísla pouze s použitím jednoduššch operací. Např. násobení jen s pomocí sčítání může vypadat takto:

def Soucin ( a , b ):
    Vysledek = 0
    while a > 0 :
        Vysledek = Vysledek + b
        a = a - 1
    return Vysledek

• Uprav početní operace tak, aby fungovaly i pro záporná čísla.

Trénování násobilky

Rozšiř program z minulé kapitoly tak, aby...

• výsledek početního příkladu vyžadoval opakovaně, dokud nebude správně
• umožňoval hádat několikrát za sebou, např.:
  • umožnit zadat počet
  • pokaždé se uživatele zeptat, jestli chce další příklad
  • ukončit procvičování třeba zadáním nuly namísto výsledku
• zkoušet i jiné operace než násobení

• Uprav hádanku na program k hádání čísla z daného rozsahu
  • Jestli chceš, aby program k hádání vybral náhodné číslo, podívej se na rozšiřující úlohu s násobilkou v minulé kapitole
  • Hádání čísla doplň o odpovědi „větší“ a „menší“ pro uživatele podle toho, jaký je jeho odhad vůči hádanému číslu
  • Hádání čísla doplň o odpovědi „samá voda“ a „přihořívá“ pro uživatele podle toho, jestli se správnému číslu blíží, nebo vzdaluje
• Naprogramuj převádění z desítkové do dvojkové, osmičkové, šestnáctkové soustavy. Vstupem je tedy desítkové přirozené číslo, výstupem řetězec znaků reprezentující číslo v jiné soustavě.
  • Funkci zobecni tak, aby umožňovala převod do soustavy a o libovolném základu.