METODA DIVIDE ET IMPERA

==========METODA DIVIDE ET IMPERA=============
Aceasta metoda consta in doua etape,divide si impera.Divide :problea data este impartita in doua sau mai multe subproblemede acelasi tip,dar de dimensiuni mai mici.Subproblemele se rezolva direct,daca dimensiunea lor permite aceasta,sau,fiind de acelasi tip,se rezolva in mod recursive prin acelasi procedeu.
Impera:se combina solutiile subproblemelor pentru a obtine solutia problemei initiale.
Metoda pare destul de complicata dar in realitate este mult mai simplu.In cele mai multe situatii ,problema se imparte in doua subprobleme de dimensiuni aproximativ egale.
DECI · Descompunerea cazului ce trebuie rezolvat intr-un numar de subcazuri mai mici ale aceleiasi probleme.
·Rezolvarea succesiva si independenta a fiecaruia din aceste subcazuri.
· Recompunerea subsolutiilor astfel obtinute pentru a gasi solutia cazului initial.


*Am sa va prezint in randurile urmatoare o rezolvare a problemei Turnurie din Hanoi.
Aceasta problema a fost propusa la sfarsitul secolului trecut de catre matematicianul francez Eduard Lucas,care a comercializat-o sub forma unui joc de opt discuri si trei baghete,numit ‘turnurile din Hanoi’.

*Jocul este inspirat dintr-o straveche legenda hindusa ,in care se povesteste ca zeul Brahma ar fi fixat pe o masa a templului sau din Benares trei baghete verticale de diamant,pe una dintre ele plasand 64 de discuri de aur in ordinea descrescatoare a diametrelor.Xi si noapte calugarii templului mutau discuri de pe tija 1 pe tija 2,folosind ca tija de manevra tija 3,respectand ordinea descrescatoare a diametrelor.Legenda spune ca atunci cand toate discurile vor fi mutate va fi sfarsitul lumii.


*Da frumos ,dar acum sa revenim pe planeta noastra,sa lasam povestile si aburerile la o parte si sa ne apucam sa rezolvam matematic si apoi informatic sau algorithmic cum vreti sa-I spuneti problema.


*Avem la dispozitie trei tije numerotate 1,2,3 si n discuri de diameter diferite.Initial toate discurile sunt plasate pe tija 1in ordinea descrescatoare a diametrelor,considerand sensul de la baza la varf.
Problema consta in a muta discurile de pe tija 1 pe tija 2,folosind ca tija de manevra tija 3,respectand urmatoarele reguli.
-la fiecare pas se muta un singur disc;
-orice disc poate fi asezat doar peste un disc cu diametru mai mare.
Acum cum rezolvam aceasta problema mai ales ca trebuie sa explicam metoda divide et impera.


*Vom nota o mutare sub forma Iŕj,unde j(1,2,3),I diferit de j,cu semnificatia se muta un disc de pe tija I pe tija j.
Daca n=1,problemase reduce la a muta un singur disc,ceea ce se poate face direct.
Daca n>1,pentru a muta discul de pe diametrul maxim de pe tija I pe j trebuie sa il eliberam ,adica sa plasma cele n-1 discuri de deasupra sa pe tija de manevra.Cele 3 tije fiind numerotate distinct cu valori din multimea {1,2,3},suma numerelortijeloreste 6,deci tija de manevra este numerotata 6-I-j.Discul de diametrul maxim fiind eliberat ,poate fi mutat pe tija j,dupa care cele n-1 discuri de pe tija 6-I-j pot fi mutate pe tija j,folosind de data asta aceasta tija I,care este goala,ca tijade manevra.
Cam atat ,o sa prezint si rezolvarea propriu-zisa daca vreti dar la clasa inca nu am ajuns cu idiotul meu de prof la aceasta metoda si de aia imi vine oarecum mai greu.

#include
ofstream f(“Hanoi.out”);
ifstream g(“Hanoi.in”);
void muta(int x,int I,int j)
{ //deci aceasta functie muta x discuri de pe tija I pe tija j ;
if(x>1)
{ muta(x-1,I,6-I-j); //tija de manevra;
f< “< muta(x-1, 6-I-j , j);
}
void main()
{ g>>n; muta(n,1,2); f.close(); g.close(); }
flo_flow © 2006