Jak rozdělit čtrnáctilitrový demižon vína napůl pomocí kanystru na benzín a sudu od piva? Úloh tohohle ražení se dá najít spousta. Zkusme napsat program, který je zvládne všechny... ačkoliv mu to bude trvat dost dlouho.
Pravidla hry dovolují přelívat víno z jedné nádoby do druhé tak, aby se buďto první vyprázdnila nebo druhá naplnila. Každá nádoba má známý objem a na začátku obsahuje daný obsah vína. Náš program má najít postup, jak se dostat do nějakého cílového stavu (pro každou flašku máme dané množství vína, jaké má na konci obsahovat) a to na co nejmenší počet přelití.
Hloupé ale dostačující řešení je nechat počítač přelívat pro každou (systematicky zvolenou) dvojici flašek a kontrolovat, jestli už nejsme v cílovém stavu. Dlužno podotknout, že pro n flašek je n · (n-1) dvojic a když řešení potřebuje k kroků, bude počítač muset udělat něco jako (n · (n-1))k pokusů. To je dost strašné, ale pro tři flašky a krátká řešení to na obyčejném počítači doběhne.
K řešení s výhodou použijeme rekurzi.
Řešení.def prelij(objemy, stav, odkud, kam): mnozstvi = min(stav[odkud], objemy[kam] - stav[kam]) vysledek = list(stav) vysledek[odkud] -= mnozstvi vysledek[kam] += mnozstvi return tuple(vysledek) def reseni(objemy, stav, cil, kroky, nejde_rychleji): if stav == cil: return [stav] elif kroky == 0: return False for odkud in range(len(stav)): for kam in range(len(stav)): vysledek = prelij(objemy, stav, odkud, kam) if vysledek not in nejde_rychleji or nejde_rychleji[vysledek] <= kroky - 1: pokus = reseni(objemy, vysledek, cil, kroky - 1, nejde_rychleji) if pokus: pokus.append(stav) return pokus else: nejde_rychleji[vysledek] = kroky return False>> reseni((14, 9, 5), (14, 0, 0), (7, 7, 0), 13, dict())[::-1]
Příklad. Napište funkci jde_proskrtat(zdroj, cil), která rozhodne, jestli jde pouhým odebíráním písmen získat z jednoho textu druhý. Základní myšlenkou se inspirujte u programu na přelévání vína.
def jde_proskrtat(zdroj, cil):
if zdroj == cil:
return True
if not zdroj:
return False
for i in range(len(zdroj)):
# ...tady musite neco doplnit
return # a tady taky
Příklad. Přepište předchozí funkci tak, aby běžela přijatelně rychle.
Nápověda.def jde_proskrtat(zdroj, cil):
if not cil: # pokud je cil prazdny retezec
return True
zacatek = zdroj.find(cil[0])
if zacatek == -1:
return False
return # ...tady musite neco doplnit
Příklad. Přepište předchozí funkci bez rekurze.
Nápověda.def jde_proskrtat(zdroj, cil):
zacatek = 0
for znak in cil:
pozice = zdroj.find(znak, zacatek)
if # tady musite doplnit podminku i jeji kod
zacatek = pozice
return # a co tady?
Příklad. Napište funkci jde_doplnit(zdroj, cil), která rozhodne, jestli jde pouhým přidáváním písmen získat z jednoho textu druhý.
Pracovali jste doteď pečlivě?
str.split, str.join, str.findFunkce str.split(oddělovač, počet) se nám bude hodit až později ke čtení souborů s bludištěm, tematicky ale zapadá sem. Když ji zavoláme na nějaký řetězec bez parametrů, navrátí seznam jednotlivých slov v původním řetězci, rozdělených podle mezer, řádků a tabulátorů. Jako parametr jí můžeme dát řetězec, který bude sloužit jako oddělovač. Druhý parametr může být číslo, které omezí počet nalezených oddělovačů a zbytek řetězce nechá vcelku.
>>> "nazdar světe jak se vede".split() ['nazdar', 'světe', 'jak', 'se', 'vede'] >>> "nazdar světe jak se vede".split("a") ['n', 'zd', 'r světe j', 'k se vede'] >>> "nazdar světe jak se vede".split("a", 2) ['n', 'zd', 'r světe jak se vede'] # všimněte si, že délka výsledného seznamu je nanejvýš pocet + 1
Příklad. Všimněte si (zkuste), že oddělovač nesmí být prázdný řetězec. Jak z řetězce vyrobíte seznam všech jeho znaků?
Funkce str.join(sekvence) dělá v určitém smyslu pravý opak, spojí řetězce ze sekvence do jednoho. Důležité (a odlišné od většiny programovacích jazyků) je, že se volá na oddělovač; chceme-li řetězce spojit bez oddělovače, zavoláme ji na prázdný řetězec "". Sekvence může být například seznam, a musí obsahovat jen řetězce (ne například čísla).
>>> ["nazdar", "světe", "jak", "se", "vede"].join("... ") Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'list' object has no attribute 'join' >>> "... ".join(["nazdar", "světe", "jak", "se", "vede"]) 'nazdar... světe... jak... se... vede'
Funkce str.find(řetězec) navrací první pozici (index), na které najdeme zadaný řetězec. Když hledáme něco delšího než jedno písmeno, vrací pozici začátku. Když nenajde nic, vrací -1.
>>> "nazdar".find("z") 2 >>> "nazdar"[2] 'z' >>> "nazdar".find("zdar") 2 >>> "nazdar".find("q") -1
breakPříkazem break vyskočíte z nejbližšího cyklu, který se právě provádí. Funguje na for i na while cykly. Svým způsobem se podobá příkazu return ve funkci, ale nemůže nic navracet.
Podobný příkaz je continue, který se chová podobně, ale cyklus nezastaví; jen přeskočí na další otočku, na další prvek sekvence.
>>> for znak in "toto je ex-papoušek": ... if znak == " ": ... continue ... if znak == "-": ... break ... print(znak) ... t o t o j e e x
Příklad. Některé programovací jazyky nabízejí cyklus s podmínkou na konci (známý jako do...while), který podobně jako while cyklus běží, dokud je podmínka splněná, ale ta podmínka se vyhodnocuje až na konci. Cyklus proto vždy proběhne aspoň jednou. Rozmyslete si, jako něco podobného napsat v Pythonu pomocí while cyklu a příkazu break, a jaké jsou jiné možnosti.
Konec odbočky v intermezzu.
Příklad. Napište funkci split(text, oddělovač), která navrátí totéž jako text.split(oddělovač) (ale samozřejmě aniž byste tuhle zabudovanou funkci použili).
Asi budete muset napsat while cyklus, kterým projdete všechny postupně všechny výskyty oddělovače v textu. Ten se vám bude hodit i v následujícím příkladu.
def split(text, znak):
vysledek = list()
pozice = 0
while 1:
dalsi = text.find(znak, pozice)
if # něco
break
vysledek.append # něco
pozice = # něco
vysledek.append # něco
return vysledek
Tuhle část zápisků jsme ještě neprobrali.
Příklad. Napište funkci pocet_preklepu(zdroj, cil), která spočítá, jaký nejmenší počet písmen je potřeba ubrat a přidat, abychom získali z řetězce zdroj řetězec cil. Podrobněji nás ty úpravy nezajímají, stačí počet.
Všimněte si, že tentokrát nějaké řešení vždycky existuje: můžeme všechno smazat a pak to napsat načisto. Pokud oba řetězce nemají žádná společná písmena, bude to i nejlepší řešení, ale takové případy nás při počítání překlepů moc nezajímají.
Abyste získali přijatelně rychlé řešení, vyjděte z následující úvahy: poslední písmeno řetězce zdroj buďto musíme smazat, nebo ho najdeme někde v řetězci cil a pak musíme smazat všechno za ním. V obou případech nám z řetězce zdroj zbude nějaká kratší část a na tu můžeme zavolat rekurzi. Když je zdroj prázdný, nezbývá než dopsat všechna písmena řetězce cil. Ze všech možností vybírejte tu s nejméně chybami a nepřehlédněte, že "najdeme někde" v tomto odstavci znamená vyzkoušet cyklem všechny výskyty.
def pocet_preklepu(zdroj, cil):
if not zdroj:
return len(cil)
min_pocet = pocet_preklepu(zdroj[?], cil) + 1
pozice = -1
while 1:
pozice = cil.find(zdroj[?], pozice + 1)
if pozice == -1:
break
pocet = pocet_preklepu(zdroj[?], cil[?]) + len(cil) - (?)
if pocet < min_pocet:
min_pocet = pocet
return min_pocet
Příklad. Přepište předchozí funkci bez použití rekurze.
Budete si potřebovat uchovávat předpočítané výsledky volání té funkce pro nějaké části obou řetězců. Nejrozumnější mi přijde pamatovat si výsledky pro nějaký prefix řetězce zdroj a všechny prefix řetězce cil, pak můžete spočítat hodnoty pro prefix řetězce zdroj o písmeno delší. Prefix znamená začátek řetězce, v Pythonu psáno řetězec[:něco]. V kódu z předchozího příkladu vlastně stačí nahradit volání funkce čtením ze seznamu a výsledky si opatrně ukládat do jiného seznamu. A napsat dva vnořené cykly.