...oua sau mai multe subprobleme, pentru fiecare din ele reapelam functia, combinam rezultatele si revnim din apel.AplicatiiMaximul dintr-un vectorSe citeste un vector cu n componente, numere naturale. Se cere sa se tipareasca valoare maxima.Trebuie tiparita valoarea maxima dintre numerele retinute in vector de la i la jinitial i 1, jn. Pentru aceasta procedam astfel daca ij, valoare maxima va fi viis contrar vom imparti vectorul in doi vectori primul vector va contine componentele de la i la ij div 2, al doilea va contine componentele de la ij div 2 1 la j , rezolvam subproblemele aflam maximul pentru fiecare din ele iar solutia problemei va fi data de valoarea maxima dintre rezultatele celor doua subprobleme.includeiostream.hint vi10s,nint maxint i ,int jI int a,b if ij return viis else I amaxi, ij2 bmaxij21,j if ab return a else return b SSmain I coutncinn for int i1ini Icoutviiscinviis S coutmaxmax1,nSCautare binaraSe citeste un vector cu n componente numere intregi, unde nemerele se presupun ordonate crescator si o valoare intreaga nr. Sa se decida daca nr se gaseste sau nu printre numerele citite, iar in caz afirmativ sa se tipareasca indicele componentei care contine acea valoare .O rezolvare in care nr se compara pe rand cu cele n valori, este lipsita de valoare nu exploateaza faptul ca cele n valori sunt in secventa crescatoare. Algoritmul care va fi propus este mult mai performant si face parte, asa cum am invatat, dintre algoritmii clasici.Problema este de a decide daca valoarea cautata se gaseste printre numerele de indice cuprins intre i si j intial i1, jn . Pentru aceasta vom proceda astfeldaca nr coincide cu vloarea de indice ij2 valoarea de la mijloc , se tipaeste indicele si se revine din apel problema a fost rezolvata.Contrar, daca ij nu s-a cautat peste tot problema se descompune astfeldaca numaul este mai mic decat valoarea testata din mijloc, inseamna ca avem sanse sa-l gasim intre componentele cu indicele intre i si ij2-1 , caz in care reapelam functia cu acesti parametridaca numarul este mai mare decat valoarea testata din mijloc, inseamna ca avem sanse sa-l gasim intre componentele cu indicele intre i j21 si j , caz in care reapelam functia cu acesti parametri.Problema nu se descompune in altele care se rezolva, dupa care nu se compara solutia, ci se reduce la o subproblema. In linii mari , acest rationament este de tip Divide et impera.includeiostream.hint vi100s,n,nrvoid cautint i, int jI if nrviij2scoutgasit indiceij2 else if ij if nrviij2scaut i , ij2-1 else caut ij21,jSmain I coutncinn for int i1ini I coutviiscinviisScoutnrcinnrcaut 1,nSSortarea prin interclasare Se considera vectorul a cu n componente numere intregi sau reale . Sa se sorteze crescator, utilizand sortarea prin interclasare.Daca dispunem de doua siruri de valori, primul cu m elemente, al diolea cu n elemente, ambele sortate, atunci se poate obtine un vector care contine toate valorile soratate. Algoritmul de interclasare este performant, pentru ca efectueaza cel mult mn-1 comparatii.Algoritmul de sortare prin interclasare se bazeaza pe urmatoarea idee pentru a sorta un vector cu n elemente il impatim in doi vectori care, odata sortati, se interclaseaza.Conform strategiei Divide et impera, problema este descompusa in alte doua subprobleme de acelasi tip si, dupa rezolvarea lor, rezultatele se combina in particular se interclaseaza. Descompunerea unui vector in alti doi vectori care urmeaza a fi sortati are loc pana cand avem de sortat vectori de una sau doua componente.In aplicatie, functia sort sorteaza un vector cu maximum doua elemente interc interclaseaza rezultatele divimp implementeaza strategia generala a metodei studiate.includeiostream.hint ai10s,nvoid sort int p,int q, int ai10s I int m if aipsaiqs I maips aipsaiqs aiqsmSSvoid interc int p,int q, int m, int ai10sI int bi10s,i,j,kip jm1 k1hile im jq if aiisbijs ciksaiis else ciksbijsif im for j1jmj ciksaijselse for ijiqi ciksbiisvoid divimp int p, int q, int ai10sI int m if q-p1 sort p,q,a else I mpq2 divimpp,m,a divimpm1,q,a intercp,q,m,a SSmai I int i coutncinn for i1ini I coutaiiscinaiisS divimp1,n,a for i1ini coutaiis STurnurile din HanoiSe dau 3 tije simbolizate prin a,b,c. Pe tija a se gasesc discuri de diametre diferite, asezate in ordine descrescatoare a diametrelor privite de jos in sus. Se cere sa se mute de pe tija a pe b, utilizand ca tija intermediara tija c, respectand urmatoarele regulila fiecare pas se muta un singur disc nu este permis sa se aseze un disc cu diametrul mai mare peste un disc cu diametrul mai mic.RezolvareDaca n1 se face mutarea ab, adica se muta discul de pe tija a pe tija b.Daca n2 se fac mutarile ac,ab,cb.In cazul in care n2 problema se complica. Notam cu Hn,a,b,c sirul mutarilor celor n discuri de pe tija a pe tija b , utilizand ca tija intermediara, tija c.Conform strategiei Divide et impera incercam sa descompunem problema in alte doua subprobleme de acelasi tip, urmand apoi combinarea solutiilor. In acest sens, observam ca mutarea celor n discuri de pe tija a pe tija b,utilizand ca tija intermediara tija c, este echivalenta cumuatrea a n-1 discuri de pe tija a pe tija c , utilizand ca tija intermediara tija bmutarea discului ramas pe tija bmutarea a n-1 discuri de pe tija c pe tija b , utilizand ca tija intermediara tija a.Parcurgerea celor trei etape permite definirea recursiva a sirului Hn,a,b,c astfel Hn,a,b,c I a,b daca n1 Hn-1,a,c,b,ab,Hn-1,c,b,a, daca n1ExemplePentru n2 avem H2,a,b,cH1,a,c,b,ab,H1,c,b,aac,ab,cb.Pentru n3 avem H3,a,b,cH2,a,c,b,ab,H2,c,b,aH1,a,b,c,ac,H1,b,c,a,a
b,H1,c,a,b,cb,H1,a,b,cab,ac,bc,ab,ca,cb,ab.include iostream.hchar a,b,cint nvoid han int n, char a, char b, char cI if n1 coutabendl elseI hann-1,a,c,b coutabendl hann-1,c,b,a SSmain I coutncinn aa bb cc hann,a,b,cS Mircea Alexandrut45Meg9SXi,.itsàaIBNKirsGHsaiiaiiiiiiiii
iiiaiiiiiiiiiiiiiiiiiiiiààààààa6a55CJ5CJ 6CJCJ5CJ5CJ 5CJXsti45M4Z...
Download