• Lekce 10
  • Úlohy
  • Co jsme probrali?
    • Eratosthenovo sito
    • Opakování funkcí
    • Rekurze

Lekce 10

Úlohy

Žádné nejsou.

Co jsme probrali?

Eratosthenovo sito

Společně jsme si naprogramovali algoritmus pro hledání prvočísel do nějakého maxima.

1
limit = int(input("Select limit:  "))
2

3
sieve = []
4

5
for i in range(limit):
6
    sieve.append(True)
7

8
# 0 and 1 are not prime
9
sieve[0] = False
10
sieve[1] = False
11

12
for i in range(2, limit):
13
    if not sieve[i]:
14
        continue
15

16
    for multiple in range(2 * i, limit, i):
17
        sieve[multiple] = False
18

19
primes = []
20

21
for i in range(limit):
22
    if sieve[i]:
23
        primes.append(i)
24

25
print(primes)

Opakování funkcí

• Znovu jsme si vysvětlili, co to je funkce
• Ukázali jsme si příklad se zdravením lidí

  1
  # seznam jmen
  2
  jmena = ["alice", "bob", "cecilie", "david"]
  3
  
  4
  def pozdrav_jmeno(jmeno):
  5
      print(f"Dobry den, {jmeno}!")
  6
  
  7
  def pozdrav_jmena(seznam_jmen):
  8
      for jmeno in seznam_jmen:
  9
          pozdrav_jmeno(jmeno)
  10
  
  11
  pozdrav_jmena(jmena)
  

• Jako doplňující materiál se můžete podívat sem.

Rekurze

• Rekurzivní funkcí myslíme tu, která uvnitř svého těla volá sama sebe
  • Může se zacyklit do nekonečna
    • To ale nechceme, chceme určit konečnou podmínku (tehdy funkce skončí)
• Používají se na řešení úloh, které se dají seskládat s dílčích řešení, které se počítají stejným způsobem.
  • Třeba výpočet faktoriálu, Fibonacciho posloupnost, mocniny, apod.
• Na hodině jsme se zabývali Fibonacciho posloupností. Sestrojili jsme pro výpočet $n$-tého Fibonacciho čísla rekurzivní funkci:

  1
  def fib(n):
  2
  if (n <= 0):
  3
      return 0
  4
  elif (n == 1):
  5
      return 1
  6
  else:
  7
      return fib(n - 1) + fib(n - 2)
  

  • Je ale neefektivní (má exponenciální časovou složitost), protože počítá více stejných čísel najednou
    • Můžeme si je někde pamatovat a poté využít bez zbytečného znovuvypočítání
    • Tomu říkáme caching
• Výpočet $n$-tého Fibonacciho čísla s použitím cache:

  1
  def fib_cached(n, cache={}):
  2
    if (n <= 0):
  3
        # pokud n <= 0, vraťme 0
  4
        return 0
  5
    elif n == 1:
  6
        # pokud n == 1, vraťme 1
  7
        return 1
  8
    elif n in cache:
  9
        # pokud už jsme n-té Fib. číslo již vypočítali, vrátíme ho
  10
        return cache[n]
  11
    else:
  12
        # pokud ne, vypočteme ho
  13
        num = fib_cached(n - 1, cache) + fib_cached(n - 2, cache)
  14
        # zapamatujeme si ho
  15
        cache[n] = num
  16
        # vrátíme ho
  17
        return num
  

  • V definici funkce můžete vidět argument cache={}
    • To říká, že druhý argument funkce fib_cached má výchozí hodnotu, kterou je prázdný slovník
• Pokud byste si o rekurzi chtěli ještě něco přečíst, můžete zde (začátek této stránky, potom už se tam píše o něčem jiném)