Processing math: 100%

MPZI_predavanje_14

2371 days ago by fresl

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:

       
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
       
[1, 2.00000000000000, 300, 3/2, 'zadnji element']
[1, 2.00000000000000, 300, 3/2, 'zadnji element']

... rekosmo, samo drugi naziv:

       
[1, 2.00000000000000, 300, 3/2, 'zadnji element']
[1, 2.00000000000000, 300, 3/2, 'zadnji element']

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

       
[1, 2.00000000000000, 300, 3/2, 'zadnji element']
[1, 2.00000000000000, 300, 3/2, 'zadnji element']
       
[1, 2.00000000000000, 300, 3/2, 'zadnji element']
[1, 2.00000000000000, 300, 3/2, 'zadnji element']
[1, 2.00000000000000, 300, 3.1415926535897932385, 'zadnji element']
[1, 2.00000000000000, 300, 3/2, 'zadnji element']
[1, 2.00000000000000, 300, 3/2, 'zadnji element']
[1, 2.00000000000000, 300, 3.1415926535897932385, 'zadnji element']

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

       
[1, 2.00000000000000, 'a', 3/2, 'zadnji element']
[1, 2.00000000000000, 'a', 3/2, 'zadnji element']
       
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
       
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
[1, 2.00000000000000, 'tri', 3/2, 'pet']
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
[1, 2.00000000000000, 'tri', 3/2, 'zadnji element']
[1, 2.00000000000000, 'tri', 3/2, 'pet']



Tvorba lista i dodavanje komponenata


.append() — dodavanje komponente na kraj liste:

       
0 []
1 [1]
2 [1, 8]
3 [1, 8, 27]
4 [1, 8, 27, 64]
5 [1, 8, 27, 64, 125]
6 [1, 8, 27, 64, 125, 216]
0 []
1 [1]
2 [1, 8]
3 [1, 8, 27]
4 [1, 8, 27, 64]
5 [1, 8, 27, 64, 125]
6 [1, 8, 27, 64, 125, 216]
       
[1, 8, 27, 64, 125, 216]
[1, 8, 27, 64, 125, 216]


sažeta tvorba liste (list comprehension):

       
[1, 8, 27, 64, 125, 216]
[1, 8, 27, 64, 125, 216]
       
[13, 13, 13, 13, 13, 13, 13, 13, 13, 13]
[13, 13, 13, 13, 13, 13, 13, 13, 13, 13]
       
       
[0, 2, 4, 6, 8]
[0, 2, 4, 6, 8]


.extend() — dodavanje liste na kraj liste:

       
[1, 8, 27, 64, 125, 216]
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728]
[1, 8, 27, 64, 125, 216]
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728]
  • umjesto funkcije .extend() može se upotrijebiti operator +=:
       
[1,
 8,
 27,
 64,
 125,
 216,
 343,
 512,
 729,
 1000,
 1331,
 1728,
 2197,
 2744,
 3375,
 4096]
[1,
 8,
 27,
 64,
 125,
 216,
 343,
 512,
 729,
 1000,
 1331,
 1728,
 2197,
 2744,
 3375,
 4096]
  • dvije se liste mogu nadovezati operatorom +:
       
[-64,
 -27,
 -8,
 -1,
 0,
 1,
 8,
 27,
 64,
 125,
 216,
 343,
 512,
 729,
 1000,
 1331,
 1728,
 2197,
 2744,
 3375,
 4096]
[-64,
 -27,
 -8,
 -1,
 0,
 1,
 8,
 27,
 64,
 125,
 216,
 343,
 512,
 729,
 1000,
 1331,
 1728,
 2197,
 2744,
 3375,
 4096]

... pribrojnici se pritom ne mijenjaju:

       
[1,
 8,
 27,
 64,
 125,
 216,
 343,
 512,
 729,
 1000,
 1331,
 1728,
 2197,
 2744,
 3375,
 4096]
[1,
 8,
 27,
 64,
 125,
 216,
 343,
 512,
 729,
 1000,
 1331,
 1728,
 2197,
 2744,
 3375,
 4096]


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

       
[-1,
 1,
 8,
 27,
 64,
 125,
 216,
 343,
 512,
 729,
 1000,
 1331,
 1728,
 2197,
 2744,
 3375,
 4096]
[-1,
 1,
 8,
 27,
 64,
 125,
 216,
 343,
 512,
 729,
 1000,
 1331,
 1728,
 2197,
 2744,
 3375,
 4096]


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

       
27
27
       
[-1,
 1,
 8,
 64,
 125,
 216,
 343,
 512,
 729,
 1000,
 1331,
 1728,
 2197,
 2744,
 3375,
 4096]
[-1,
 1,
 8,
 64,
 125,
 216,
 343,
 512,
 729,
 1000,
 1331,
 1728,
 2197,
 2744,
 3375,
 4096]

 

 

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

 

Funkcija map()

... ako je f funkcija jedne varijable, a lista l ima komponente l0,l1,,ln1, rezultat poziva  map (f, lnova je lista  [f(l0),f(l1),,f(ln1)].

       
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
       
       
[1, 8, 27, 64, 125, 216, 343, 512, 729]
[1, 8, 27, 64, 125, 216, 343, 512, 729]

... isto, primjenom petlje for:

       
[1, 8, 27, 64, 125, 216, 343, 512, 729]
[1, 8, 27, 64, 125, 216, 343, 512, 729]

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

       
[1, 8, 27, 64, 125, 216, 343, 512, 729]
[1, 8, 27, 64, 125, 216, 343, 512, 729]

... štoviše:

       
[1, 8, 27, 64, 125, 216, 343, 512, 729]
[1, 8, 27, 64, 125, 216, 343, 512, 729]

 

Neimenove funkcije (lambda–funkcije)

       
<function <lambda> at 0x7f94ac22d5f0>
<function <lambda> at 0x7f94ac22d5f0>
       
27
27
       
5
5

 

map() i lambda

       
[1, 8, 27, 64, 125, 216, 343, 512, 729]
[1, 8, 27, 64, 125, 216, 343, 512, 729]
       
[13, 13, 13, 13, 13, 13, 13, 13, 13]
[13, 13, 13, 13, 13, 13, 13, 13, 13]

 

Ako je f funkcija dviju varijabli i ako su  a=[a0,a1,,an1]  i  b=[b0,b1,,bn1]  dvije liste s jednakim brojem komponenata, onda je rezultat poziva  map (f, a, b)  lista  [f(a0,b0),f(a1,b1),,f(an1,bn1)].

       
[10, 10, 10, 10, 10, 10, 10, 10, 10]
[10, 10, 10, 10, 10, 10, 10, 10, 10]

... isto, primjenom petlje:

       
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[10, 10, 10, 10, 10, 10, 10, 10, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[10, 10, 10, 10, 10, 10, 10, 10, 10]
       
[0, -7/9, -11/4, -45/7, -38/3, -23, -81/2, -217/3, -140]
[0, -7/9, -11/4, -45/7, -38/3, -23, -81/2, -217/3, -140]

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

 

Funkcija reduce()

... umjesto petlje

       
45
45

... to jest

  • r0
  • rr+l0=0+l0
  • rr+l1=(0+l0)+l1
  • rr+l2=((0+l0)+l1)+l2
  • rr+ln1=((((0+l0)+l1)+l2))+ln1

... možemo primijeniti funkciju

       
45
45

... općenito, neka su f funkcija dviju varijabli,  l=[l0,l1,,ln1]  i  x0 broj;  rezultat r poziva  reduce (f, l, x0)  izračunava se na sljedeći način:

  • rx0,
  • rf(r,l0)=f(x0,l0)
  • rf(r,l1)=f(f(x0,l0),l1)
  • rf(r,l2)=f(f(f(x0,l0),l1),l2)
  • rf(r,ln1)=f((f(f(f(x0,l0),l1),l2)),ln1)

 

Duljina vektora vv=v=n1i=0v2i

       
       
25
25
       
(7, 24)
(7, 24)
       
25
25
       
25
25

 

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

       
45
45

... što je, primjenom petlje, 

       
45
45

... dakle, za funkciju f dviju varijabli i  l=[l0,l1,,ln1],  rezultat r poziva  reduce (f, l)  izračunava se na sljedeći način:

  • rf(l0,l1)
  • rf(r,l2)=f(f(l0,l1),l2)
  • rf(r,ln1)=f((f(f(f(l0,l1),l2),l3)),ln1)

 

Skalarni umnožak vektora u i vs=uv=n1i=0uivi

       
       
(1, 2, -11, 3/2, 6, -1/2, 5, 1/2, 0, 2)
(2/3, 0, -11, -1, -1, 1, -2/3, 4, 0, -15/2)
(1, 2, -11, 3/2, 6, -1/2, 5, 1/2, 0, 2)
(2/3, 0, -11, -1, -1, 1, -2/3, 4, 0, -15/2)
       
292/3
292/3
       
292/3
292/3
       
292/3
292/3


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 li liste l za koje je p(li)= True.

       
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
       
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

... isto, primjenom petlje:

       
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

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

       
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

 


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

xn=x×x××xn1puta

složenost algoritma:  O(n) množenja

 

Rješenje pomoću petlje

       
       
8
8
       
81
81
       
-524288
-524288
       
95367431640625
95367431640625

 

Rješenje pomoću rekurzije

rekurzivni dio:  xn=x×xn1

temeljni dio:  x1=x

       
       
8
8
       
81
81
       
-524288
-524288
       
95367431640625
95367431640625

 

Učinkovitiji algoritam

 

nparan:xn=x2n/2=xn/2×xn/2=(xn/2)2n/2paran:xn=x22n/4=(xn/4×xn/4)×(xn/4×xn/4)=(xn/4)2×(xn/4)2=((xn/4)2)2n=2k:xn=x2k=((x2)2)2kputaxnneparan:xn=x×(x(n1)/2)2 

složenost algoritma:  O(log2n) množenja/kvadriranja

       
       
8
8
       
81
81
       
-524288
-524288
       
95367431640625
95367431640625
       
4
4
       
4
4

 

... i još neke sitnice

 

n=0

x0:x0=1x=0:nedefinirano

hmm ... prisjetite se napomene u predavanju 11.

 

n<0

n=m  za  m>0,  pa je  xn=xm=1xm=(1x)m

       
       
1
1
       
NaN
NaN
       
1/524288
1/524288
       
1.90734863281250e-6
1.90734863281250e-6
       
1/95367431640625
1/95367431640625
       
1.04857600000000e-14
1.04857600000000e-14