Algoritmi și tehnici de programare

Divide et impera

? ??

?

Divide et impera

Metodă de rezolvare a unor probleme

Caracteristici probleme pot fi descompuse în probleme cu complexitate mai mică

▪ de același tip / cu soluție cunoscută ▪ descompunerea este finită – problemă primitivă / condiție de terminare▪ cîte probleme?▪ cum se face împărțirea?

rezolvarea noilor probleme este mai ușoară soluțiile combinate soluția problemei inițiale

Descompunere propriu-zisă / reducere

Determinarea elementului maxim dintr-o mulțime

Metoda bisecției

Maxim(a, n)

x = Maxim(a, n-1) max = x>a[n-1] ? x : a[n-1]

Maxim(a, p, u)

x1 = Maxim(a, p, (p+u)/2)x2 = Maxim(a, (p+u)/2+1, u)max = x1>x2 ? x1 : x2

Divide et impera

Algoritm recursiv Implementarea este de obicei recursivă Forma generală

▪ S=▪ determină o modalitate de descompunere a problemei P =>

P1, P2, … Pn▪ pentru fiecare i=1:n

▪ aplică recursiv algoritmul, pentru rezolvarea problemei Pi => Si

▪ S=S Si

Divide et impera

Exemple Probleme de parcurgere Problema turnurilor din Hanoi Problema tăieturilor Probleme de căutare

▪ secvențială / binară

Probleme de sortare▪ prin interclasare▪ prin inserare▪ rapidă (quick sort)▪ metoda micșorării incrementului (Shell sort)

Divide et impera

Probleme de parcurgere

o mulțime a, cu n elemente => P(a, 0, n) P(a, i, n) se descompune în

prelucrare a[i] P(a, i+1, n)

void parcurge(float *v, int i, int n){ if( i!=n ) { printf("%7.2f ",v[i]); parc(v,i+1,n); }}

Divide et impera

Problema turnurilor din Hanoi

H(n, S, D, I) H(n-1, S, I, D) mută un disc de pe S pe D H(n-1, I, D, S)

void hanoi(int n, char s, char d, char i){ if(n>0) { hanoi(n-1,s,i,d); printf("\nMuta un disc de pe %c pe %c",s,d); hanoi(n-1,i,d,s); }}hanoi( 5, ‘a’, ‘b’, ‘c’);

Sursă Destinație Intermediar

Divide et impera

Problema tăieturilor x, y, a, b, c[2,n]

21

3 4

1: x, c[1,i] a, y+b-c[1,i]

2: x, y a, c[1,i]-y

3: x, y c[0,i]-x, b

4: c[0,i], y x+a-c[0,i], b

a

b

xmax, ymaxamax=0, bmax=0

x

y

x+a

y+b

c[0,i]

c[1,i]

void taietura(int **c, int x, int y, int a, int b, int *xm, int *ym, int *am, int *bm){ int i,gasit; for( i=gasit=0; (i<n)&&!gasit; ) if((c[0][i]>x)&&(c[0][i]<x+a) && (c[1][i]>y)&&(c[1][i]<y+b)) gasit=1; else i++; if(gasit) { taietura(c, x,c[1][i], a,b-c[1][i]+y, xm,ym,am,bm); taietura(c, x,y, a,c[1][i]-y, xm,ym,am,bm); taietura(c, x,y, c[0][i]-x,b, xm,ym,am,bm); taietura(c, c[0][i],y, a-c[0][i]+x,b, xm,ym,am,bm); } else if(a*b>(*am)*(*bm)) { *am=a; *bm=b; *xm=x; *ym=y; }}

Divide et impera

Probleme de căutare Secvențială problemă de parcurgere (mulțimi sortate

sau nesortate) Binară (mulțimi sortate)

Nu există riscul să se obțină poziția -1 chiar dacă elementul căutat se află în mulțime, deoarece în momentul găsirii lui, nu se mai face nici un apel recursiv și nu se mai modifică valoarea lui poz

Mulțime nesortată

C(x, a, i, n, poz) dacă i==n poz=-1 altfel

dacă x==a[i] poz=ialtfel C(x, a, i+1, n, poz)

Mulțime sortată

C(x, a, i, n, poz) dacă i==n || a[i]>x poz=-1 altfel

dacă x==a[i] poz=ialtfel C(x, a, i+1, n, poz)

C(x, a, p, u, poz) dacă p>u poz=-1 altfel m=(p+u)/2

dacă x==a[m] poz=maltfel daca x<a[m] C(x, a, p, m-1, poz) altfel C(x, a, m+1, u, poz)

Divide et impera

Sortare prin interclasare

S(a, n) => S(a, 0, n-1)▪ dacă p<u

▪ m=(p+u)/2▪ S(a, p, m)▪ S(a, m+1, u)▪ interclasează a[p:m] cu a[m+1:u]

15 7 13 5 11 3 1 8 14 6 12 4 10 2 9

15 7 13 5 11 3 1 8 14 6 12 4 10 2 9

1 3 5 7 8 11 13 15 2 4 6 9 10 12 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

S(0, 14)

S(0, 7) S(8, 14)

…

Divide et impera

Sortare rapidă

Q(x, p,u)▪ dacă p<u

▪ poziționare(x, p, u, k)▪ Q(x, p, k-1)▪ Q(x, k+1, u)

x[0] x[1] x[2] … x[k-2] x[k-1] x[k] x[k+1] x[k+2] … x[n-1]

x[0] x[1] x[2] … x[k-2] x[k-1] x[k] x[k+1] x[k+2] … x[n-1]

Q(0, n-1)

Q(0, k-1) Q(k+1, n-1)

10 9 19 15 3 17 4 1

0 -11 0

Divide et impera

Sortare prin micșorarea incrementului (Shell sort) generalizare a sortării prin inserție vector k-sortat secvență de pași : valori descrescătoare, ultima este 1

Algoritm

pentru fiecare pas din secvență▪ pentru fiecare i=pas..n-1

▪ j=i-pas▪ cît timp j>0 și v[j]<v[j+pas]

v[j] <->v[j+pas] j-=pas

Divide et impera

Sortare prin micșorarea incrementului (Shell sort)

indici 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14n=15 Initial: 38 13 85 98 5 70 45 44 68 71 40 44 9 10 3Dupa pasul 7: 3 13 71 40 5 9 10 38 68 85 98 44 70 45 44Dupa pasul 3: 3 5 9 10 13 44 40 38 44 70 45 68 85 98 71Dupa pasul 1: 3 5 9 10 13 38 40 44 44 45 68 70 71 85 98

void sort_shell(double v[], int l){ int i,j,inc; double a;  for(inc=l/2; inc>0; inc=inc/2) for(i=inc; i<l; i++) for(j=i-inc; (j>=0)&&(v[j]>v[j+inc]); j=j-inc) { a=v[j]; v[j]=v[j+inc]; v[j+inc]=a; }}

Spor la învăţat!