Procvičování: seznamy

Příklad. Najděte dvatisícečtrnácté prvočíslo.

Jsou tu napsaná postupně čtyři řešení. Jestli se chcete něco naučit, první tři si můžete zkoušet naprogramovat sami, než se podíváte na hotový kód.

Přímočaré řešení je postupně hledat prvočísla od nejmenšího a počítat si, kolik jsme jich už potkali. Když napočítáme do 2014, vrátíme to, co jsme právě našli.

Celé číslo n větší než jedna je prvočíslo, právě když je dělitelné jen sebou samým a jedničkou. Můžeme tedy napsat cyklus, který ho bude zkoušet dělit vším mezi 2 a n-1 a pokud vždy po dělení zůstane zbytek, držíme v ruce prvočíslo.

Pomůžou nám ale znalosti z matematiky, konkrétně to, že každé kladné celé číslo jde rozložit na součin prvočísel. To znamená, že nemusíme naše n dělit úplně vším, stačí zkoušet všechna prvočísla menší než n – a ta už jsme ale spočítali. Stačí si je pamatovat, k tomu se bude hodit seznam.

Zlepšení je viditelné: zatímco prvním způsobem trval (na mém počítači doma) výpočet prvocislo(2014) 2.7 vteřiny, tenhle vylepšený výpočet trvá 0.3 vteřiny. (Poznámka: místo desetinné čárky píšu tečku, byť by se to češtinářům nelíbilo, ale programátory by čárka mohla plést.) Můžeme si ale ještě přilepšit díky tomu, že prvočísla máme v seznamu od nejmenšího. Když zkoušíme dělit nějakým p a víme, že žádným menším prvočíslem naše n dělitelné není, musel by být jeho prvočíselný rozklad aspoň p * p nebo větší. Anebo má rozklad jenom jeden činitel, což by znamenalo, že n je prvočíslo. Když se tedy dostaneme k dělení číslem p takovým, že p2 > n, můžeme cyklus skončit s jistotou, že n je prvočíslo.

def prvocislo(poradi):
	prvocisla = list()
	n = 1
	while len(prvocisla) < poradi:
		n += 1
		je_prvocislo = True
		for p in prvocisla:
			if p*p > n:
				break
			if n % p == 0:
				je_prvocislo = False
				break
		if je_prvocislo:
			prvocisla.append(n)
	return prvocisla[-1]

S touhle funkcí trvá na mém počítači výpočet 0.03 vteřiny. Všimněte si, že čím větší hodnotu po funkci budete chtít, tím se budou rozdíly ve výpočetním čase ještě drastičtěji zvyšovat. K tomuto tématu se určitě ještě mnohokrát vrátíme podrobněji.

Procvičování: slovníky

Příklad. Napište funkci na počítání Fibonacciho čísel.

Fibonacciho čísla jsou daná rekurzivním předpisem F0 = 0, F1 = 1, jinak Fn = Fn-1 + Fn-2. Přímočarý postup je napsat si rekurzivní funkci, která bude počítat přesně hodnoty podle toho zadání.

Potíž je v tom, že i obě volání funkce, ke kterým dojde během výpočtu, každé potřebují taky zavolat funkci fib dvakrát a tak dál, dokud se všechna volání nedostanou k jedničce nebo nule, teprv potom něco navrátí. Jednak tedy vidíme, že celkový počet volání funkce je větší než příslušné Fibonacciho číslo (a ta rostou hodně rychle), z jiného pohledu si můžeme přímo odvodit, že počet volání bude aspoň 2n/2. Výpočet fib(180) proto zaručeně nedoběhne, než rozpínající se Slunce pohltí naši planetu. Sto osmdesát není zas tolik, co se s tím dá dělat?

Jednoduché vylepšení je použít slovník a pamatovat si v něm výsledky, které máme spočítané. Dřív než funkce fib začne něco počítat, zkusí hotový výsledek vytáhnout ze slovníku, a když něco nového spočítá, přidá to tam. Na začátku můžeme do slovníku dát hodnoty pro F0 a F1, aby byl kód funkce kratší. Důležité je, slovník musí být někde nastálo pro všechna volání funkce, takže ho musíme nastavit v kódu mimo funkci.

Teď už výpočet fib(180) trvá něco jako 10-4 vteřiny, a to je první pokus: druhý a další dotaz už mají výsledek připravený pod nosem, takže ho navrátí ještě asi stokrát rychleji.

Poznamenejme ještě, že s rekurzivními funkcemi je potřeba zacházet opatrně a tohle není dobrý způsob, jak počítat Fibonacciho čísla. Když se volání funkce zavrství do sebe moc, Python na nás vyhodí RuntimeError. Sice můžeme omezení rekurze změnit voláním funkce setrecursionlimit z modulu sys, ale ani to nefunguje donekonečna. Za nejhezčí řešení považuju to, když si z celé Fibonacciho posloupnosti pamatujeme jen poslední dvě čísla a ta sečteme v každém kroku nějakého cyklu, abychom získali to následující.