Scrigroup - Documente si articole

     

 
HomeDocumenteUploadResurseAlte limbi doc
 
AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


METODE DE ELABORARE A ALGORITMILOR. DIVIDE ET IMPERA.

c



+ Font mai mare | - Font mai mic



Metode de elaborare a algoritmilor. Divide et Impera.

Metode Divide et Impera este o metoda de rezolvare a unor probleme si este inspirata de principiul "Imparte si stapaneste". In conformitate cu principiul amintit, o problema de complexitate mare se va imparti in subprobleme de acelasi tip insa de dimensiuni mai mici ale caror rezolvare se va dovedi mai simpla. De asemenea, subproblemele obtinute prin descompunerea problemei pot fi la randul lor impartite in subprobleme mai mici. Etapa de impartirea se considera incheiata cand subproblemele devin elementare - rezolvabile imediat. Solutiile subproblemelor se vor combina pentru a alcatui solutia globala a problemei.



Metoda descrisa poate fi aplicata in conditiile in care problemele admit o impartire in subprobleme de acelasi fel. Putem vorbi de un specific al problemelor rezolvabile cu Divide et Impera. Acest specific este dat de urmatoarele afirmatii:

problema globala se poate imparti in 2 sau mai multe subprobleme asemanatoare de dimensiuni mai mici

subproblemele obtinute prin impartire sunt independente, ceea ce permite ca solutiile partiale ale acestora sa nu depinda unele de altele

contextul problemei ne permite sa identificam conditia ca o subproblema sa fie considerata elementara si sa nu mai fie supusa unei impartiri ulterioare

subproblemele obtinute prin impartire admit aceiasi metoda de rezolvare fiind probleme de acelasi fel.

Exemple de probleme celebre rezolvabile cu metoda Divide et Impera sunt: problema Turnurilor din Hanoi, Sortarea rapida, etc.

Fie P - problema globala, n - dimensiunea ei si S - solutia dorita. Fie n0 - dimensiunea minima a unei probleme pentru care aceasta devine elementara si admite o rezolvare imediata.

Deoarece toate subproblemele sunt tratate prin aplicarea aceluiasi algoritm, diferenta facandu-se doar prin datele de intrare-iesire si dimensiunea subproblemelor, precum si datorita faptului ca solutiile obtinute sunt solutii partiale ale problemei globale, descrierea potrivita a metodei este data printr-un subalgoritm autoapelabil. De altfel, implementarea in limbaj de programare se face prin proceduri (functii) recursive.

Subalgoritm DivideEtImpera (P_formal, n_formal; S_formal) este:

Daca n_formal< n0 atunci

#rezolva imediat subproblema P_formal si obtine solutia S_formal

Altfel

#imparte problema P_formal de dimensiune n_formal in:

# P1 de dimensiunea n1,

# P2 de dimensiune n2,

# Pk de dimensiune nk

Cheama DivideEtImpera(P1,n1,S1)

Cheama DivideEtImpera(P2,n2,S2)

Cheama DivideEtImpera(Pk,nk,Sk)

#combina solutiile partiale S1,S2,,Sk si obtine S_formal

SfDaca

SfSubalgoritm

Propozitiile nestandard din descrierea subalgoritmului nu pot fi detaliate decat in functie de problema rezolvata.

Pentru a rezolva problema globala P, apelul subalgoritmului se va face pentru parametrii actuali P, n si S:

Cheama DivideEtImpera(P,n;S)

Problema 1: Se cere determinarea maximului dintr-un vector de n valori numerice.

Analiza problemei:

Determinarea celui mai mare element dintr-un vector poate fi privita ca o problema de determinare a maximului dintre doua valori intermediare, reprezentand maximele celor doua subsiruri obtinute prin impartirea sirului initial in doua parti egale:

x1 ,x2 ,x3 , ., xk+1 , xk , xk+1 ,.,xn-2 ,xn-1 ,xn

Maxim

x1 ,x2 ,x3 , ., xk+1 , xk

Maxim1

xk+1 ,.,xn-2 ,xn-1 ,xn

Maxim2

Maxim= maxim(Maxim1,Maxim2)

Fiecare subsir din impartirea anterioara se va putea imparti din nou in doua parti de dimensiuni apropiate. Acest proces de impartire se va incheia cand un subsir de elemente nu mai poate fi impartit, respectiv cand dimensiunea acestuia s-a redus la 1. In acest moment, subproblema devine elementara, deoarece maximul elementelor unui vector format dintr-un singur element este insasi elementul respectiv.

Am identificat in problema data initial o problema rezolvabila prin Divide Et Impera. Dimensiunea unei subprobleme este data de numarul elementelor din subsirul manevrat si dimensiunea unei subprobleme elementare este 1. Combinarea solutiilor partiale se face printr-o comparatie simpla.

Subalgoritmul DivideEtImpera devine in acest caz:

Subalgoritm DivideEtImpera _Maxim(xinf , ., xsup ;Maxim_formal) este:

Daca sup-inf <= 0 atunci

Maxim_formal= xinf

Altfel

mij= (sup+inf)/2

Cheama DivideEtImpera_Maxim(xinf , ., xmij;Maxim1)

Cheama DivideEtImpera_Maxim(xmij+1 , ., xsup,Maxim2)

Daca Maxim1>Maxim2 atunci

Maxim_formal=Maxim1

Altfel

Maxim_formal=Maxim2

SfDaca

SfDaca

SfSubalgoritm

Pentru rezolvarea problemei complete apelul subalgoritmului devine:

Cheama DivideEtImpera(x1 , . ,xn ;Maxim)

Program:

#include <stdio.h>

#define NMAX 20

void citire (int t[NMAX],int *n)

int maxim(int t[NMAX], int inf,int sup)

void main()

Problema 2: Problema turnurilor din Hanoi. Se dau 3 tije simbolizate prin A,B,C. Pe tija A se gasesc n discuri de diametre diferite, asezate de jos in sus in ordine crescatoare a diametrelor. Se cere sa se mute toate discurile de pe tija A pe tija B, utilizand ca tija intermediara tija C, respectand urmatoarele reguli:

- la 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.

A

B

C

Analiza problemei:

Cazul elementar al problemei consta in existenta unui singur disc pe tija A, ceea ce reduce rezolvarea la o mutare a discului de pe tija A pe tija B.

Pentru n=2 (doua discuri), rezolvarea problemei consta in 3 mutari, folosind tija intermediara C:

muta discul mai mic de pe tija A pe tija C

muta discul mai mare de pe tija A pe tija B

muta discul mic de pe tija C pe tija B

Generalizand, pentru un numar oarecare n de discuri situate pe tija A, rezolvarea problemei se reduce la parcurgerea urmatoarelor etape:

muta primele n-1 discuri de pe A pe C, utilizand tija B ca intermediara

muta discul ramas de pe tija A pe tija B

muta cele n-1 discuri de pe C pe B, utilizand tija A ca intermediara

Observam ca problema s-a redus la doua probleme de dimensiuni mai mici, respectiv, de a efectua mutarea a n-1 discuri. Aceiasi maniera de abordare a problemei de dimensiune n-1 va reduce problema la mutarea a n-2 discuri, s.a.m.d. In cele din urma, pentru cazul elementar al unui singur disc ce trebuie mutat, se va aplica rezolvarea directa.

Subalgoritmul Hanoi va trata problema transferului a k discuri de pe tija X, pe tija Y, folosind tija ramasa Z ca intermediara:

Subalgoritm Hanoi (k,X,Y,Z) este:

Daca k=1 atunci

Muta discul de pe tija X pe tija Y //rezolvare directa, problema elementara

Altfel

Cheama Hanoi(k-1,X,Z,Y)

Muta discul ramas de pe X pe Y //problema elementara

Cheama Hanoi(k-1,Z,Y,X)

SfDaca

SfSubalgoritm

Apelul subalgoritmului pentru rezolvarea problemei globale este:

Cheama Hanoi(n,A,B,C)

Program:

#include <stdio.h>

void Hanoi (int n, int A, int B, int C)

}//sfarsit Hanoi

void main ()

Problema 3: Cautare Binara. Fiind dat un vector ordonat de n valori numerice, sa se determine pozitia pe care se regaseste o valoare data cheie.

Analiza problemei:

Cautarea unei valori cheie intr-un vector ordonat de n valori se poate reduce la o problema mai simpla (de dimensiune mai mica) daca ne folosim de informatia ca vectorul este ordonat. Acest lucru ne permite sa impartim vectorul in doua parti relativ egale, sa comparam cheia cu valoarea elementului de pe pozitia taieturii si sa decidem continuarea cautarii intr-unul dintre subvectorii rezultati, ignorand acea parte care nu poate contine cheia cautata. Subvectorul in care se continua cautarea poate fi la randul sau impartit in doua parti pentru a obtine probleme mai mici. Impartirea se termina in conditiile in care cheia a fost gasita sau subvectorul pe care il manevram nu poate fi impartit (este format din maxim un element).

Decizia continuarii cautarii intr-unui dintre subvectorii rezultati printr-o impartire precedenta se face pe baza unei comparatii simple a elementului de pe pozitia taieturii, notat xmij, cu cheia cautata. Rezultatul comparatiei poate fi urmatorul:

cheie egala cu valoarea elementului xmij - rezulta ca am gasit pozitia mij a cheii

cheie mai mica decat xmij - rezulta ca vom continua cautarea in prima parte a vectorului, intre elementele situate la stanga pozitiei mij

cheie mai mare decat xmij - rezulta ca vom continua cautarea intre elementele din dreapta pozitiei mij

Subalgoritmul de rezolvare a problemei de cautare binara se descrie astfel:

Subalgoritm CautareBinara(xinf , ., xsup ,cheie;poz) este:

Daca sup-inf <= 0 atunci

// vectorul curent contine un singur element

Daca xinf= cheie atunci

poz=inf

Altfel

poz= -1 // semnificatia faptului ca nu s-a gasit cheia

SfDaca

Altfel

// vectorul curent contine mai mult de un element

mij= (sup+inf)/2

Daca cheie=xmij atunci

poz=mij //am gasit pozitia cheii

Altfel

Daca cheie<xmij atunci

Cheama CautareBinara(xinf , ., xmij ,cheie;poz)

Altfel

Cheama CautareBinara(xmij+1 , ., xsup ,cheie;poz)

SfDaca

SfDaca

SfSubalgoritm

Apelul Cheama CautareBinara(x1 , ., xn ,cheie;poz) rezolva problema globala. Daca valoarea poz este egala cu -1 la terminarea apelului, cheia nu a fost gasita in vectorul dat, in caz contrar, valoarea poz reprezinta pozitia pe care a fost gasita cheia cautata.

Problema 4. Sortare rapida (QuickSort). Algoritmul de sortare rapida este un exemplu tipic de algoritm Divide et Impera. Fiind dat un vector oarecare de n elemente se cere ordonarea crescatoare a vectorului dupa valorile elementelor.

Ideea de baza a sortarii rapide consta in impartirea vectorului in doi subvectori cu proprietatea ca toate elementele primului sunt mai mici decat un element pivot si elementele celui de-al doilea subvector sunt mai mari decat pivotul. Alegerea pivotului ramane in sarcina programatorului, existand trei variante plauzibile: pivotul este elementul median al subvectorului manevrat, pivotul este elementul de pe prima pozitie, respectiv, pivotul este ales ca elementul de pe ultima pozitie din subvector. In descrierea urmatoare, pivotul este ales ca fiind elementul de pe pozitia mediana.

Impartirea vectorului in doua parti care verifica proprietatea enuntata necesita operatii de interschimbare a valorilor elementelor de pe pozitii diferite. Odata ce etapa de impartire a fost parcursa, cei doi subvectori rezultati vor fi supusi aceluiasi procedeu de impartire. Problema devine elementara implicit daca subvectorul corespunzator are dimensiunea 1, fiind considerat ordonat. Combinarea solutiilor nu necesita o etapa distincta, facandu-se in mod implicit, prin interschimbarile elementelor vectorului dat in apelurile recursive ale subalgoritmului.

Impartirea unui sir de elemente xinf, .,xsup se face parcurgand pasii:

  1. initializeaza doi indici de parcurgere a subsirului in doua sensuri: i -indicele de parcurgere a sirului de la stanga la dreapta, respectiv, j - indicele de parcurgere de la dreapta la stanga; initial, i=inf, j=sup.
  2. stabileste pivotul (elementul de pe pozitie mediana din sir)
  3. cattimp pivotul este mai mare decat elementele de pe pozitiile parcurse de la stanga la dreapta, efectueaza avans la dreapta al indicelui i
  4. cat timp pivotul este mai mare decat elementele de pe pozitiile parcurse de la stanga la dreapta, efectueaza avans la dreapta al indicelui i
  5. daca i<j interschimba valorile de pe pozitiile i si j si actualizeaza indicii prin avans la dreapta, respectiv la stanga
  6. repeta pasii 3, 4 si 5 pana cand valoarea indicelui i devine mai mare decat valoarea lui j

Dupa parcurgerea pasilor 1-6 se considera subsirul xinf, .,xsup impartit in doua subsiruri: xi, .,xsup si xinf, .,xj. Daca subsirurile obtinute contin mai mult de 1 element, acestea se vor supune aceluiasi procedeu descris.

Subalgoritmul     corespunzator metodei descrise anterior este urmatorul:

Subalgoritm QuickSort(xinf, .,xsup)este:

Fie i=inf si j=sup

mij=(inf+sup)/2 //mij - reprezinta pozitia pivotului xmij

Repeta

Cattimp ( i<sup si xi<xmij)

//avans la dreapta

i=i+1

SfCattimp

Cattimp ( j>inf si xj>xmij)

//avans la stanga

j=j-1

SfCattimp

Daca i<j atunci

Cheama Interschimbare(xi,xj)

SfDaca

Panacand (i>j)

Daca (i<sup) atunci

Cheama QuickSort(xi, .,xsup)

SfDaca

Daca (j>inf)

Cheama QuickSort(xinf, .,xj)

SfDaca

SfSubalgoritm

Pentru rezolvare problemei globale se va efectua apelul:

Cheama QuickSort (x1, .,xn)

Program C:

#include <stdio.h>

void citireSir(int x[10],int *n)

void tiparireSir(int x[10],int n)

void SQuick(int x[10],int st, int dr)

if (i<=j)

}while(i<=j);

if (i<dr) SQuick(x,i,dr); //daca subsirul 1 mai are cel putin 1 elem ..

if (j>st) SQuick(x,st,j); //daca subsirul 2 mai are cel putin 1 elem ..

void main()

Problema 4. Sortarea prin interclasare este o tehnica de ordonare a unui vector. Principiul de baza este acela al impartirii vectorului initial in doua parti egale (subvectori), prin sortarea partilor rezultate si ulterior interclasarea celor doi subvectori ordonati, rezultand vectorul global ordonat. Fiecare dintre cei doi subvectori obtinuti la o impartire precedenta, la randul lor pot fi impartiti fiecare in doua parti, urmand ca subvectorii de dimensiune mai mica sa fie supusi aceluiasi mecanism de ordonare prin interclasarea si sa obtinem subvectori ordonati, de dimensiuni mai mari.

Operatia de interclasare a doi vectori a fost discutata intr-un capitol precedent. Aceasta operatie presupune parcurgerea secventiala a celor doi vectori ordonati si construirea celui de-al treilea vector prin copierea elementelor din cei doi vectori cu restrictia de a pastra relatia de ordine intre elementele vectorului rezultat. In algoritmul de sortare prin interclasare, vectorii ce vor fi interclasati sunt de fapt subvectori ai aceluiasi vector, ceea ce conduce la o procedura de interclasare usor diferita fata de cea prezentata in capitolul 0.

Observam ca problema generala permite o impartire in subprobleme independente mai mici rezolvabile prin aceiasi tehnica, ceea ce ne permite o abordare prin metoda Divide et Impera. Subproblemele se considera elementare daca dimensiunea subvectorilor devine 1, ceea ce este echivalent afirmatiei "subvector ordonat".

Subalgoritmul prin care se realizeaza sortarea prin interclasare este descris in continuare:

Subalgoritm MergeSort(xinf , ., xsup) este:

Daca sup-inf<1 atunci

// nu se efectueaza nimic, se revine din apelul subalgoritmului (conditia

// de terminare a recursivitatii), considerand ca subvectorul curent de

// dimensiune 1 este ordonat

Altfel

Fie mij=(inf+sup)/2

Cheama MergeSort(xinf , ., xmij)

Cheama MergeSort(xmij+1 , ., xsup)

//interclasarea subvectorilor xinf , ., xmij si xmij+1 , ., xsup

i=inf // i - indicele de parcurgere a subvectorului xinf , ., xmij

j=mij+1 // j - indicele de parcurgere a subvectorului xmij+1 , ., xsup

k=1 // k -parcurgerea vectorului rezultat y1 ,., ydim Cattimp (i<=mij si j<=sup)

Daca (xi<xj) atunci

yk=xi // se copiaza din primul subvector

i=i+1

k=k+1

Altfel

Interclasare
 
yk=xj // se copiaza din al doilea subvector

j=j+1

k=k+1

SfDaca

SfCattimp

Cattimp (i<=mij) //au mai ramas elemente in primul subcvector

yk=xi // se copiaza din primul subvector

i=i+1

k=k+1

SfCattimp

Cattimp (j<=sup) //au mai ramas elemente in primul subcvector

yk=xj // se copiaza din al doilea subvector

j=j+1

k=k+1

SfCattimp

// copierea vectorului y in vectorul xinf , ., xsup

Pentru i de la 1 la k-1

xi+inf-1=yi

SfPentru

SfDaca

SfSubalgoritm

Apelul Cheama MergeSort(x1 , ., xn) va produce ordonarea vectorului global

Program C: Ordonarea unui vector prin metoda sortarii prin interclasare.

#include <stdio.h>

void citireSir(int x[10],int *n)

void tiparireSir(int x[10],int n)

void MergeSort(int x[], int inf, int sup)

else

}

while(i<=mij)

while(j<=sup)

for(i=inf;i<k;i++)

x[i]=y[i];

}}

void main(void)


Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1177
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved