MPZI_predavanje_14

O listama i o rekurziji

Baratanje listama

Pridruživanje i kopiranje lista

Pridruživanjem liste novoj varijabli, ta varijabla postaje samo drugi naziv iste liste:

... rekosmo, samo drugi naziv:

Nova se lista—istoga sadržaja—dobiva kopiranjem:

Za ugniježđene liste treba upotrijebiti funkciju deepcopy():

Tvorba lista i dodavanje komponenata

.append() — dodavanje komponente na kraj liste:

sažeta tvorba liste (list comprehension):

.extend() — dodavanje liste na kraj liste:

• umjesto funkcije .extend() može se upotrijebiti operator +=:

• dvije se liste mogu nadovezati operatorom +:

... pribrojnici se pritom ne mijenjaju:

.insert() — umetanje komponente na određeno mjesto u listi:

.pop() — uklanjanje komponente s određenoga mjesta u listi:

Funkcije map(), reduce() i filter()

Funkcija map()

... ako je $f$ funkcija jedne varijable, a lista $l$ ima komponente $l_0,\,l_1,\,\ldots,\, l_{n-1}$, rezultat poziva  map (f, l)  nova je lista  $[f(l_0),\,f(l_1),\,\ldots,\, f(l_{n-1})]$.

... isto, primjenom petlje for:

... isto, primjenom sažete tvorbe liste:

... štoviše:

Neimenove funkcije (lambda–funkcije)

map() i lambda

Ako je $f$ funkcija dviju varijabli i ako su  $a = [a_0,\,a_1,\,\ldots,\,a_{n-1}]$  i  $b = [b_0,\,b_1,\,\ldots,\,b_{n-1}]$  dvije liste s jednakim brojem komponenata, onda je rezultat poziva  map (f, a, b)  lista  $[f(a_0,b_0),\, f(a_1,b_1),\,\ldots,\,f(a_{n-1},b_{n-1})]$.

... isto, primjenom petlje:

(Domaća zadaća: napišite funkciju something() primjenom sažetih tvorbi lista i primjenom petlji for  :o)

Funkcija reduce()

... umjesto petlje

... to jest

• $r \leftarrow 0$
• $r \leftarrow r + l_0 = 0 + l_0$
• $r \leftarrow r + l_1 = (0 + l_0) + l_1$
• $r \leftarrow r + l_2 = ((0 + l_0) + l_1) + l_2$
• $\cdots$
• $r \leftarrow r + l_{n-1} = (\cdots (((0 + l_0) + l_1) + l_2)\cdots) + l_{n-1}$

... možemo primijeniti funkciju

... općenito, neka su $f$ funkcija dviju varijabli,  $l = [l_0,\,l_1,\,\ldots,\, l_{n-1}]$  i  $x_0$ broj;  rezultat $r$ poziva  reduce (f, l, x0)  izračunava se na sljedeći način:

• $r \leftarrow x_0$,
• $r \leftarrow f (r, l_0) = f (x_0, l_0)$
• $r \leftarrow f (r, l_1) = f (f (x_0, l_0), l_1)$
• $r \leftarrow f (r, l_2) = f (f (f (x_0, l_0), l_1), l_2)$
• $\cdots$
• $r \leftarrow f (r, l_{n-1}) = f (\cdots(f (f (f (x_0, l_0), l_1), l_2)\cdots), l_{n-1})$

Duljina vektora $\mathbf{v}$:  $v = \|\mathbf{v}\| = \displaystyle\sqrt{\sum_{i=0}^{n-1}v_i^2}$

Drugi oblik poziva funkcije reduce() — bez trećega parametra:

... što je, primjenom petlje, 

... dakle, za funkciju $f$ dviju varijabli i  $l = [l_0,\,l_1,\,\ldots,\, l_{n-1}]$,  rezultat $r$ poziva  reduce (f, l)  izračunava se na sljedeći način:

• $r \leftarrow f (l_0, l_1)$
• $r \leftarrow f (r, l_2) = f (f (l_0, l_1), l_2)$
• $\cdots$
• $r \leftarrow f (r, l_{n-1}) = f (\cdots(f (f (f (l_0, l_1), l_2), l_3)\cdots), l_{n-1})$

Skalarni umnožak vektora $\mathbf{u}$ i $\mathbf{v}$:  $s = \mathbf{u}\cdot\mathbf{v} = \displaystyle\sum_{i=0}^{n-1} u_i\,v_i$

Funkcija filter()

... ako su $p$ relacijska ili logička funkcija (takozvani predikat — funkcija čije su vrijednosti True ili False) i $l$ lista, onda je rezultat poziva filter (p, l) nova lista koja sadrži one komponente $l_i$ liste $l$ za koje je $p(l_i) =$ True.

... isto, primjenom petlje:

... isto, primjenom sažete tvorbe liste:

Rekurzivne funkcije

Neformalno, funkcija koja poziva samu sebe naziva se rekurzivnom funkcijom.

 Strože i potpunije, definicija rekurzivne funkcije sastavljena je od dva dijela:

1. temeljni dio sa slučajem ili slučajevima koji se mogu neposredno izračunati,
2. rekurzivni dio koji je pak sastavljen od tri koraka:
   1. podjela zadaće u jednostavnije ili manje (pod)zadaće,
   2. rješavanje svake od tih (pod)zadaća pozivom funkcije,
   3. sastavljanje rješenjâ (pod)zadaća u rješenje zadaće

Izračunavanje cjelobrojne potencije

„Naivni” algoritam

$n > 0$

$x^n =\, x\, \underbrace{\times\, x\times \cdots\times x}_{n-1\;\text{puta}}$

složenost algoritma:  $\mathcal{O}(n)$ množenja

Rješenje pomoću petlje

Rješenje pomoću rekurzije

rekurzivni dio:  $x^n =\, x\times x^{n-1}$

temeljni dio:  $x^1 = x$

Učinkovitiji algoritam

$\begin{array}{ll}
n\;\;\text{paran:} &  x^n \:=\: x^{\,2\,n/2} \:=\: x^{n/2}\!\times x^{n/2} \:=\: \big(\,x^{n/2}\,\big)^{2} \\
n/2\;\;\text{paran:} &  x^n \:=\: x^{\,2\cdot 2\cdot n/4} \:=\: \big(\,x^{n/4}\!\times x^{n/4}\,\big)\!\times \big(\,x^{n/4}\!\times x^{n/4}\,\big) \:=\: \big(\,x^{n/4}\,\big)^{2}\!\times \big(\,x^{n/4}\,\big)^{2} \:=\: \big(\big(\,x^{n/4}\,\big)^{2}\,\big)^{2} \\
n = 2^k: & x^n \:=\: x^{2^k} \:=\: \underbrace{\big(\cdots\big(\,x^2\,\big)^{2}\cdots\big)^{2}}_{k\:\text{puta}}\\
\phantom{x} \\
n\;\;\text{neparan:} &  x^n \:=\: x\times\big(\,x^{(n-1)/2}\,\big)^2
\end{array}$ 

složenost algoritma:  $\mathcal{O}(\log_2n)$ množenja/kvadriranja

... i još neke sitnice

$n = 0$

$\begin{array}{lll} x \ne 0: & & x^0 = 1 \\ x = 0: & & \text{nedefinirano}^* \end{array}$

$^*$ hmm ... prisjetite se napomene u predavanju 11.

$n < 0$

$n = -m$  za  $m>0$,  pa je  $x^n \,=\, x^{-m} \,=\, \dfrac{1}{x^m} \,=\, \left(\dfrac{1}{x}\right)^{\!m} $