Cursul 2 Ppt

7/24/2019 Cursul 2 Ppt

1/40

Algoritmi si structuri de date - Curs 2

(2015)

1

CURS 2:Descrierea algoritmilor n pseudocod

=Exemple=


2/40

Algoritmi si structuri de date - Curs 2(2015)

2

Structura

Descrierea unor algoritmi simpli

Specificarea i utilizarea subalgoritmilor


3/40


3

Exemplu 1Considerm un tabel cu informaii despre studeni

Nr. Nume Note Credite Stare Medie

1 A 8 6 7 60

2 B 10 10 10 60

3 C - 7 5 40

4 D 6 - - 20

5 E 8 7 9 60

Problema: sse completeze coloanele stare i mediefolosind regulilestare = 1 dacCredite=60 (obs:1 credit=30 ore de activitate)

stare= 2 dacCredite este in [30,60)

stare= 3 dacCredite


4/40


4

Exemplu 1Dupcompletare tabelul va arta astfel:


1 A 8 6 7 60 1 7

2 B 10 10 10 60 1 10

3 C - 7 5 40 2 -

4 D 6 - - 20 3 -

5 E 8 7 9 60 1 8

stare = 1 dacCredite=60

stare= 2 dacCredite este in [30,60)

stare= 3 dacCredite


5/40


5

Exemplu 1Ce fel de date vor fi prelucrate?


1 A 8 6 7 60

2 B 10 10 10 60

3 C - 7 5 40

4 D 6 - - 20

5 E 8 7 9 60

Date de intrare: Notesi Credite

note[1..5,1..3] : tablou bidimensional (matrice) cu 5 linii i 3coloane

Descriere n pseudocod: int note[1..5,1..3]


6/40


6



1 A 8 6 7 60

2 B 10 10 10 60

3 C - 7 5 40

4 D 6 - - 20

5 E 8 7 9 60

Date de intrare: Note i Credite

credite[1..5] : tablou unidimensional cu 5 elemente

Descriere in pseudocod: int credite[1..5]


7/40


7



1 A 8 6 7 60

2 B 10 10 10 60

3 C - 7 5 40

4 D 6 - - 20

5 E 8 7 9 60

Date de ieire: Stare si Mediestare[1..5], medie[1..5] : tablouri unidimensionale cu 5 elemente

Descriere pseudocod: int stare[1..5]

real medie[1..5]


8/40


8

Exemplu 1Regula pt.determinarea strii

asociate unui student

stare = 1 dac credite=60

stare= 2 daccredite in [30,60)

stare= 3 daccredite =30 then stare = 2

else stare = 3endif

endif

stare 1

da

credite>=30

stare 2 stare 3

nu

nuda Descriere in Python

if credite==60:stare=1

elif credite>=30:stare=2

else:

stare=3


9/40

Exemplu 1Completarea strii pentru toi studenii

Obs:Numrul studenilor este notat cu n (nexemplul analizat n=5)

Pas 1: se pornete de la prima linie din tabel(i 1)

Pas 2: se verificdacmai sunt linii deprelucrat (i


10/40


Exemplu 1Completarea strii pentru toi

studenii Pseudocod:int credite[1..n], stare[1..n], i

i =1

while i=30 then stare[i]=2

else stare[i] = 3

endif

endif

i = i+1

endwhile

10

calcul stare[i]

i 1

i


11/40


Exemplu 1Simplificarea descrierii algoritmuluiprin gruparea unor prelucrri in

cadrul unui subalgoritm

Pseudocod:

int credite[1..n], stare[1..n], i

i = 1

while i=30 then stare = 2

else stare = 3

endif

endifreturn stare

Obs:un subalgoritm descrie un calculafectuat asupra unor date genericenumite parametri

11


12/40


Utilizarea subalgoritmilorIdei de baz:

Problema iniialse descompune n subprobleme

Pentru fiecare subproblemse proiecteazun algoritm (numitsubalgoritm sau modul saufuncie sau procedur)

Prelucrrile din cadrul subalgoritmului se aplicunor date generice(numite parametri) i eventual unor date ajuttoare (numitevariabilelocale)

Prelucrrile specificate n cadrul subalgoritmului sunt executate nmomentul apeluluiacestuia (cnd parametrii generici sunt inlocuii cuvalori concrete)

Efectul unui subalgoritm constn :

Returnarea unuia sau a mai multor rezultate

Modificarea valorilor unor parametri (sau a unor variabile globale)

12


13/40

Utilizarea subalgoritmilorMecanismul de comunicare intre algoritm si subalgoritmi:

- parametri i valori returnate

Algoritm

Variabile (globale)

Calcule locale.Apel subalgoritm

..Calcule locale

Variable locale

Calcule asupra variabilelorlocale si parametrilor

Returnarea rezultatelor

Parametri:- intrare

- iesire

Subalgoritm

Date intrare

Date iesire


13


14/40


Utilizarea subalgoritmilorMecanismul de comunicare intre algoritm si subalgoritmi:

- parametri si valori returnate

Algoritm

int credite[1..n], stare[1..n], ii 1

while i=30

then stare 2

else stare 3

endifendif

return stare

Subalgoritm

Date intrare

Date iesire

Param. intrare

Var.

locala

Rezultat dereturnat

14


15/40

Utilizarea subalgoritmilor Structura unui subalgoritm:

()

< declaraii ale variabilelor locale >

< prelucrri >

RETURN

Apelul unui subalgoritm:

()


15


16/40

napoi la Exemplul 1

Pseudocod:int credite[1..n], stare[1..n], i

i = 1

while i=30 then stare = 2

else stare = 3

endif

endif

return stare


16


17/40

napoi la Exemplul 1

Python:credite=[60,60,40,20,60]stare=[0]*5

n=5

i=0

while i=30:stare=2

else:

stare=3

return stare

Obs: indentarea liniilor este foarteimportantn Python


17


18/40

napoi la Exemplul 1

Calcul medie: pentru studenii avndstarea=1

trebuie calculat mediaaritmetic a notelor

Notele studentului ise afl pe linia ia matricii note(se pot specifica prinnote[i,1..m])


1 A 8 6 7 60 1

2 B 10 10 10 60 1

3 C - 7 5 40 2

4 D 6 - - 20 3

5 E 8 7 9 60 1

18Algoritmi si structuri de date - Curs 2(2015)


19/40

napoi la Exemplul 1

Calculul mediei

int note[1..n,1..m], stare[1..n]

real medie[1..n]

for i = 1,n do

if stare[i]==1

medie[i] = calculMedie(note[i,1..m])

endif

endfor

Funcie pt calcul medie

calculMedie(int v[1..m])

real suma

int i

suma = 0

for i = 1,m do

suma = suma+v[i]

endfor

suma = suma/mreturn suma


Linia i a matricii =tablou uni-dimensional


20/40

napoi la Exemplul 1

Calculul mediei (exemplu Python)note=[[8,6,7],[10,10,10],[0,7,5],[6,0,0],[8,7,9]]stare=[1,1,2,3,1]

medie=[0]*5

for i in range(5):

if stare[i]==1:medie[i]=calculMedie(note[i])

print medie

Obs: range(5) = [0,1,2,3,4]

In Python indicii tablourilor ncep de la 0

Functie pt. calculul mediei(Python)

def calculMedie(note):

m=len(note)

suma=0

for i in range(m):

suma = suma+note[i]

suma=suma/m

return suma



21/40

Pauz ... de ciocolat

Am o tablet de ciocolat pe care doresc s o rup nbucele (n cazul unei tablete 4x6 sunt 24 astfelde bucele). Care este numrul de micri derupere necesare pentru a separa cele 24 debucele ? (la fiecare micare pot rupe o bucat

n alte dou buci doar de-a lungul uneia dinliniile separatoare ale tabletei)



22/40


Am o tablet de ciocolat pe care doresc s o rup nbucele (n cazul unei tablete 4x6 sunt 24 astfelde bucele). Care este numrul de micri derupere necesare pentru a separa cele 24 debucele ? (la fiecare micare pot rupe o bucat n

alte dou buci doar de-a lungul uneia din liniileseparatoare ale tabletei)

Rspuns: 23 (n cazul unei tablete de mxn numrulde micri este mxn-1)

Cum putem demonstra ?



23/40


Prin inducie matematic (pentru o tablet cu N=nxmbucele)

Caz particular: bucata ntreag (1) nu necesit nici o

rupere (0)Ipotez: Prespunem c pentru orice K


24/40


24

Exemplu 2 cel mai mare divizorcomun

Problema: Fie a i b dounumere reale. Sse determine cel maimare divizor al lui a i b: cmmdc(a,b)

Metoda lui Euclid (varianta bazat pe mpriri):

Se calculeazrestul r al mpririi lui a (demprit) la b(mpritor)

Inlocuiete valoarea deimpritului (a)cu valoareampritorului (b),

valoareampritorului(b)cu valoarea restului r icalculeazdin nou restulmpririi luia lab

Procesul continupnse obine un rest egal cu 0

Restul anterior (care este evident diferit de 0) va fi cmmdc(a,b).


25/40


25


Cum funcioneazmetoda?

1: a=bq1+r1, 0


26/40


26


Cum funcioneazmetoda?

1: a=bq1+r1, 0


27/40


27


Algoritm

(varianta WHILE ):

cmmdc(int a,b)int d,i,rd = a

i = br = d MOD iwhile r!=0 do

d = ii = r

r = d MOD iendwhilereturn i

Algoritm :

(varianta REPEAT )

cmmdc(int a,b)

int d,i,r

d = a

i = brepeat

r = d MOD i

d = i

i = runtil r=0

return d

E l 2 d l i


28/40


28

Exemplu 2 cmmdc al unei secvenede valori

Problema: sse determine cmmdc al unei secvene de numere

naturale nenule

Exemplu:cmmdc(12,8,10)=cmmdc(cmmdc(12,8),10)=cmmdc(4,10)=2

Date de intrare: secvena de valori (a1,a2,..., an) Date de ieire (rezultat): cmmdc (a1,a2,..., an)

Idee:

Se calculeazcmmdc al primelor douelemente, dupcare secalculeazcmmdc pentru rezultatul anterior i noua valoare

e natural sse utilizeze un subalgoritm care calculeazcmmdc


29/40

Algoritmi si structuri de date - Curs 2(2015) 29

Exemplu 2 cmmdc al unei secvenede valori

Structura algoritmului:

cmmdcSecventa(int a[1..n])

int d,i

d = cmmdc(a[1],a[2])

for i = 3,n dod = cmmdc(d,a[i])

endfor

return d

cmmdc (int a,b)

int d,i,r

d = a

i = br = d MOD i

while r0 do

d = i

i = rr = d MOD i

endwhile

return i


30/40

Algoritmi si structuri de date - Curs 2(2015) 30

Exemplu 3: problema succesorului

Se considerun numr constituit din 10 cifre distincte. Ssedetermine elementul urmtor din secvena cresctoare anumerelor naturale constituite din 10 cifre distincte.

Exemplu:x= 6309487521

Data de intrare: tablou unidimensional cu 10 elemente ce coninecifrele numrului: [6,3,0,9,4,8,7,5,2,1]

Care este urmtorul numr (n ordine cresctoare) ce conine 10

cifre distincte?

Rspuns:

6309512478


31/40

Algoritmi si structuri de date -Curs 2 (2015) 31

Exemplu 3: problemasuccesorului

Pas 1.Determincel mai mare indice i avnd proprietatea cx[i-1]


32/40


Exemplu 3: problema succesoruluiSubprobleme / subalgoritmi:

Identifica:Identificpoziia ia celui mai din dreapta element x[i],care este mai mare dect vecinul su stng (x[i-1])

Input:x[1..n]

Output:i

Minim:determinindicele celui mai mic element din subtabloulx[i..n] care este mai mare decat x[i-1]Input:x[i-1..n]Output:k

Inversare:inverseazordinea elementelor din x[i..n]Input:x[i..n]Output:x[i..n]


33/40



Structura generala a algoritmului:

Succesor(int x[1..n])int i, ki = Identifica(x[1..n])

if i==1then write nu exista succesor !"else

k = Minim(x[i-1..n])x[i-1]x[k]

x[i..n] = Inversare(x[i..n])write x[1..n]

endif

Observaie: In generalinterschimbarea valorilor a douvariabile necesit 3 atribuiri iutilizarea unei variabile auxiliare(la fel cum schimbareaconinutului lichid a dou

pahare necesit utilizarea unuialt pahar)

a beste echivalent cu

aux = aa = bb = aux


34/40



Identifica(int x[1..n])int ii = nwhile (i>1) and (x[i]


35/40



inversare(int x[left..right])int i,ji = leftj = right

while i


36/40


Exemplu 3: implementare Pythondef identifica(x):

n=len(x)

i=n-1

while(i>0)and(x[i-1]>x[i]):

i=i-1

return i

defminim(x,i):

n=len(x)

k=i

forj inrange(i+1,n):

if(x[j]x[i-1]):

k=j

returnk

def inversare(x,left,right):

i=left

j=right

while i


37/40


Exemplu 3: implementare Python

# apelul functiilor definite anteriorx=[6,3,0,9,4,8,7,5,2,1]print "secventa cifrelor din numarul initial:",x

i=identifica(x)

print "i=",i

k=minim(x,i)

print "k=",k

x[i-1],x[k]=x[k],x[i-1]

print "secventa dupa interschimbare:",xx=inversare(x,i,len(x)-1)

print "secventa dupa inversare:",x


38/40


Sumar

Problemele se descompun in subprobleme crora li se asociazsubalgoritmi

Un subalgoritmeste caracterizat prin:

Nume

Parametri

Valori returnate

Variabile locale

Prelucrri

Apelul unui subalgoritm:

Parametrii sunt nlocuii cu valori concrete Prelucrrile din algoritm sunt executate


39/40


Cursul urmtor

Cum se poate verifica corectitudinea algoritmilor

Introducere in verificarea formala corectitudinii algoritmilor


40/40

40

Intrebare de final

x = 7

y = 5

while y>0 do

x = x+1y = y-1

endwhile

Ce valoare va avea variabila xdup execuia algoritmului demai sus ?

Variante de rspuns:

a) 8

b) 6

c) 12d) 11

e) 5

Cursul 2 Ppt

Documents

Transcript of Cursul 2 Ppt