Divide et impera

Algoritmi i tehnici de programareMetoda divide et impera????

Divide et imperaMetod de rezolvare a unor probleme complexe

Caracteristici problemepot fi descompuse n probleme cu complexitate mai micde acelai tip / cu soluie cunoscut (probleme primitive)descompunerea este finit problem primitiv / condiie de terminarecte probleme?cum se face mprirea?rezolvarea noilor probleme este mai uoarsoluiile combinate soluia problemei iniiale

Descompunere propriu-zis / reducereDeterminarea elementului maxim dintr-o mulime

Metoda biseciei

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

Divide et imperaExempleProbleme de parcurgereProblema turnurilor din HanoiProblema tieturilorProbleme de cutaresecvenial / binarProbleme de sortareprin interclasareprin inserarerapid (quick sort)metoda micorrii incrementului (Shell sort)

Divide et imperaProbleme de parcurgere

o mulime a, cu n elemente => P(a, 0, n)Problema primitiv: i==nP(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]); //prelucrare v[i] parc(v,i+1,n); }}

Divide et imperaProblema turnurilor din Hanoi

H(n, S, D, I)H(n-1, S, I, D)mut un disc de pe S pe DH(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);

SursDestinaieIntermediar

Divide et imperaProblema tieturilor x, y, a, b

, c[2,n]21341: x, c[1,i] a, y+b-c[1,i]2: x, y a, c[1,i]-y3: x, y c[0,i]-x, b4: c[0,i], y x+a-c[0,i], babxmax, ymaxamax=0, bmax=0xyx+ay+bc[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; (ix)&&(c[0][i]y)&&(c[1][i](*am)*(*bm)) { *am=a; *bm=b; *xm=x; *ym=y; }}

Divide et imperaProbleme de cutareSecvenial problem de parcurgere (mulimi sortate sau nesortate)Binar (mulimi sortate)

Nu exist riscul s se obin poziia -1 chiar dac elementul cutat se afl n mulime, deoarece n momentul gsirii lui, nu se mai face nici un apel recursiv i nu se mai modific valoarea lui pozMulime 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)

Mulime 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)/2dac x==a[m] poz=maltfel daca x S(a, 0, n-1)dac pv[j+pas]v[j] v[j+pas]j-=pas

Divide et imperaSortare prin micorarea 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=0)&&(v[j]>v[j+inc]); j=j-inc) { a=v[j]; v[j]=v[j+inc]; v[j+inc]=a; }}

Spor la nvat!