Temat 2: Funkcje w języku Python

Wstecz; Ostatnia modyfikacja: 2.03.2015

---

• Project Euler - problemy matematyczno-obliczeniowe.
• Słowniki (tablice hasujące)

d={}
d={1:"a",2:"b",3:"c"}
d[4]="d"
2 in d
"b" in d
d.pop(2)
for k in d: print(k)
for v in d.values(): print(v)
for (k,v) in d.items(): print(k,v)

• Funkcje w języku Python

def sq(x):        # nazwa i parametry funkcji
  return x**2     # zwracana wartość (None domyślnie)
sq(123456)

• Ćwiczenie rozgrzewkowe: napisz funkcje fib(n) liczącą n-ty wyraz ciągu Fibonacciego.
• Funkcje nienazwane (lambda-abstrakcja)

f=lambda x:x**2
print(f(f(123456)))
sorted(["aaz","dddd","cc","b"], key=lambda e:e[-1])  # przykład praktycznego zastosowania

• Funkcje rekurencyjne

def fact(x):
  if x==0: return 1
  return x*fact(x-1)

• parametry opcjonalne

def cipher(t, r=13):
  d = {}       # slownik (tablica hashujaca) - bardzo przydatna struktura
  for c in (ord('a'), ord("A")):
    for i in range(26):
      d[chr(i+c)] = chr((i+r) % 26 + c)
  return "".join([d.get(c, c) for c in t])

cipher("La Bamba", r=1)

• funkcje wyższych rzędów

def comp(f, n=1): # n-krotne zlozenie funkcji f
  if n == 0: return lambda x:x
  if n == 1: return f
  return lambda x: f(comp(f, n-1)(x))  # wynikiem jest funkcja

comp(lambda x:x**2,2)(10)   # przyklady
comp(cipher, 2)("La Bamba")

• też składanie funkcji, ale znacznie szybciej

def comp(f, n=1):
  if n == 0: return lambda x:x
  elif n == 1: return f
  elif n % 2 == 0: 
    return lambda x:comp(lambda x: f(f(x)), n/2)(x)
  else: return lambda x: f(comp(lambda x: f(f(x)), n/2)(x))

• Jak policzyć liczbę wywołań funkcji fact?
Sposób 1 - funkcje są obiektami - dodajemy atrybut count.

def fact(x):
  fact.i+=1
  if x<=0: return 1
  return x*fact(x-1)
fact.i=0
fact(10)
fact.i

• Sposób 2 - zmienne globalne.

count = 0
def fact(x):
  global count    # co sie stanie, gdy usuniemy slowo global?
  count+=1 
  if x<=0: return 1
  return x*fact(x-1)
fact(10)
count

• Technika spamiętywania

def fact(x):
  fact.i += 1
  if not hasattr(fact, "mem"):
    fact.mem = {}
  if x in fact.mem: return fact.mem[x]
  if x<=0: return 1
  fact.mem[x] = x*fact(x-1)
  return fact.mem[x]

fact.i=0
print(fact(20))
print(fact.i)  # przeanalizuj zanim uruchomisz - liczba wywolan
fact.i=0       # resetujemy liczbe wywolan
print(fact(25))
print(fact.i)  # a tutaj?

• Ćw 1: napisz funkcję, która dla danego słowa zastępuje wszystkie wystąpienia (poza pierwszym wystąpieniem) pierwszej litery w tym słowie poprzez '*'. Np. f("mama")="ma*a". f("ananas")="an*n*s"
• Ćw 2: napisz program, który wczytuje plik tekstowy i wypisuje N słów o największej liczbie wystąpień. Przetestuj swój program na (i) Biblii (kopia), (ii) Romeo i Julii (kopia).
• Ćw 3: (i) zaimplementuj funkcję liczącą n-ty wyraz ciągu Fibonacciego, korzystając ze wzroru rekurencyjnego; (ii) dodaj kod, który policzy liczbę wywołań tej funkcji; (iii) zastosuj technikę spamiętywania by organiczyć liczbę wywołań tej funkcji; (iv) jakie znasz inne algorytmy liczenia n-tego wyrazu tego ciągu? (v) spróbuj rozwiązać: Even Fibonacci numbers
• Ćwiczenia 1: ćwiczenia ze skryptu 1
• Ćwiczenia 2: ćwiczenia ze skryptu 2