...lemele se pot descompune daca este necesar in alte subprobleme mai simple aceste subprobleme simple se pot solutiona imediat prin algoritmul simplificat. Deoarece putine probleme indeplinesc conditiile de mai sus ,aplicarea metodei este destul de rara. Dupa cum sugereaza si numele desparte si stapaneste etapele rezolvarii unei probleme numita problema initiala in DIVIDE ET IMPERA sunt - descompunerea problemei initiale in subprobleme independente ,smilare problemei de baza ,de dimensiuni mai mici descompunerea treptata a subproblemelor in alte subprobleme din ce in ce mai simple ,pana cand se pot rezolva imediata ,prin algoritmul simplificat rezolvarea subproblemelor simple combinarea solutiilor gasite pentru construirea solutiilor subproblemelor de dimensiuni din ce in ce mai mari combinarea ultimelor solutii determina obtinerea solutiei problemei initiale . Metoda DIVIDE ET IMPERA admite o implementare recursiva ,deorece subproblemele sunt similare problemei initiale, dar de dimensiuni mai mici . Principiul fundamental al recursivitatii este autoapelarea unui subprogram cand acesta este activceea ce se intampla la un nivel ,se intampla la orice nivel ,avand grija sa asiguram conditia de terminare ale apelurilor repetate .Asemanator se intampla si in cazul metodei DIVITE ET IMPERA la un anumit nivel sunt doua posibilitati s-a ajuns la o subproblema simpla ce admite o rezolvare imediata caz in care se rezolva subproblema si se revine din apel la subproblema anterioara,de dimensiuni mai maris-a ajuns la o subproblema care nu admite o rezolvare imediata ,caz in care o descompunem in doua sau mai multe subprobleme si pentru fiecare din ele se continua apelurile recursiveale procedurii sau functiei. In etapa finala a metodei DIVIDE ET IMPERA se produce combinarea subproblemelor rezolvate deja prin secventele de revenire din apelurile recursive. Etapele metodei DIVIDE ET IMPERA prezentate anteriorse pot reprezenta prin urmatorul subprogram general procedura sau functie recursiv exprimat in limbaj natural Subprogram DIVIMP PROB Daca PROBLEMA PROB este simpla Atunci se rezolva si se obtine solutia SOL Altfel pentru i1,k executa DIVIMPPROB si se obtine SOL1 Se combina solutiile SOL 1,... ,SOL K si se obtine SOL Sfarsit ssubprogram Deci ,subprogramul DIVIMP se apeleaza pentru problema initiala PROBaceasta admite descompunerea in K subprobleme simple pentru acestea se reapeleaza recursiv subprogramul in final se combina solutiile acestor K subprobleme. De obicei problema initiala se descompune in doua subprobleme mai simple in acest caz etapele generale ale metodei DIVIDE ET IMPERA se pot reprezenta concret,in limbaj pseudocod ,printr-o procedura recursiva astfel Procedura DIVIMPli,ls,sol Daca ls-lieps Atunci REZOLVA li,ls,sol Altfel DIVIDE li,m,ls DIVIMPli,msol1 DIVIMPm,ls,sol2 COMBINAsol1,sol2,sol Sfarsits procedura Procedura DIVIMP se apeleaza pentru problema initiala care are dimensiunea intre limita inferioara li si limita inferioaralsdaca subproblema este simpla ls-lieps,atunci procedura REZOLVA ii afla solutia imediat si se produce intoarcerea din apelul recursivdaca subproblema este inca complexa ,atunci procedura DIVIDE o imparte in doua subprobleme ,alegand pozitia m intre limitele li si ls pentru fiecare din cele doua subprobleme se reapeleaza recursiv procedura DIVIMP in final ,la intoarcerile din apeluri se produce combinarea celor doua soluitii sol1 si sol2 prin apelul procedurii COMBINA.PROBLEMA TURNURILOR DIN HANOIPrezentarea algoritmului rezolvarii Fie trei tije verticale notate A,B,C .Pe tija A se gasesc asezate n discuri de diametre diferite ,in ordinea crescatoare a diametrelor,privind de sus in jos . Initial ,tijele B si C sunt goale .Sa se afiseze toate mutarile prin care discurile de pe tija A se muta pe tija B , in aceeasi ordine ,folosind ca tija de manevra C si resspectand urmatoarele reguli la fiecare pas se muta un singur disc un disc se poate aseza numai peste un disc cu diametrul mai mare . Rezolvarea acestei probleme se bazeaza pe urmatoarele considerente logice -daca n1 ,atunci mutarea este immediata ABmut discul de pe A pe B daca n2,atunci sirul mutarilor este AC,AB,CB daca n2 procedam astfel -mut n-1discuri AC -mut un disc AB -mut cele n-1discuri CB. Observam ca problema initiala se descompune in trei subprobleme mai simple ,similare problemei initiale mut n-1discuri AC ,mut ultimul disc pe B ,mut cele n-1discuri C--B.Dimensiunile acestor subprobleme sunt n-1,1,n-1.Aceste subprobleme sunt independente ,deoarece tijele initial pe care sunt dispuse discurile ,tijele finale si tijele intermediare sunt diferite.Notam Hn,A,B,Csirul mutarilor a n discuri de pe A pe B, folosind C. PENTRU n1 AB n1 Hn,A,B,C Hn-1,A,C,B,AB, Hn-1,C,B,A program turnurile shanoi var nbyte procedure hanoinbytea,b,cchar begin if n1 then ritelna,,b else begin hanoin-1,a,c,b ritelna,,b hanoin-1,c,b,a end end begin ritenr discuri pe tija A readlnn ritelnmutarile sunt urmatoarele hanoin,A,B,C readlnreadln end.Sortare rapidaquicksort Un tablou V se completeaza cu n elemente numere reale .Sa se ordoneze crescator folosind metoda de sortare rapida . Solutia problemei se bazeaza pe urmatoarele etape implementate in programul principal se apeleaza procedura quick cu limita inferioara li1 si limita superioara lsn functiapoz realizeaza mutarea elementului viis exact pe pozitia ce o va ocupa acesta in vectorul final ordonat functiapoz intoarce in k pozitia ocupata de acest element in acest fel ,vectorul V se imparte in doua parti li k-1 si k1ls pentru fiecare din aceste parti se reapeleaza proceduraquick,cu limitele modificate corespunzator in acest fel ,primul element din fiecare parte va fi pozitionat exact pe pozitia finala ce o va ocupa in vectorul final ordonat functiapoz fiecare din cele doua parti va fi ,astfel ,inpartita in alt...
Download