• Lekce 10
  • Úlohy
  • Co jsme probrali?

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.

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

sieve = []

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

# 0 and 1 are not prime
sieve[0] = False
sieve[1] = False

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

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

primes = []

for i in range(limit):
    if sieve[i]:
        primes.append(i)

print(primes)

Opakování funkcí

• Znovu jsme si vysvětlili, co to je funkce

• Ukázali jsme si příklad se zdravením lidí

  # seznam jmen
  jmena = ["alice", "bob", "cecilie", "david"]
  
  def pozdrav_jmeno(jmeno):
      print(f"Dobry den, {jmeno}!")
  
  def pozdrav_jmena(seznam_jmen):
      for jmeno in seznam_jmen:
          pozdrav_jmeno(jmeno)
  
  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

  def fib(n):
  if (n <= 0):
      return 0
  elif (n == 1):
      return 1
  else:
      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

  def fib_cached(n, cache={}):
    if (n <= 0):
        # pokud n <= 0, vraťme 0
        return 0
    elif n == 1:
        # pokud n == 1, vraťme 1
        return 1
    elif n in cache:
        # pokud už jsme n-té Fib. číslo již vypočítali, vrátíme ho
        return cache[n]
    else:
        # pokud ne, vypočteme ho
        num = fib_cached(n - 1, cache) + fib_cached(n - 2, cache)
        # zapamatujeme si ho
        cache[n] = num
        # vrátíme ho
        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)