Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


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


Metoda divide et impera (divide si stapaneste)

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
ARBORI - ARBORI PARTIAL ORDONATI. VECTORI HEAP
Operanzi
Adaugarea unui element la sfarsitul listei
Operatori si expresii - Instructiunea de atribuire
Servicii DOS si BIOS
Operatori, operanzi, expresii
Instructiuni si blocuri
Switch
Deplasarea cursorului
Argumentele argc si argv ale functiei main()

TERMENI importanti pentru acest document

Metoda divide et impera (divide si stapaneste)

Aceasta modalitate de elaborare a programelor consta in impartirea repetata a unei probleme de dimensiune mai mare in doua sau mai multe subprobleme de acelasi tip urmata de combinarea solutiilor subproblemelor rezolvate pentru a obtine solutia problemei initiale.




Se da un vector A=(a1,,an) si trebuie efectuata o prelucrare oarecare asupra elementelor sale.

Presupunem ca:

p,qI cu 1 £p < q £ mI a.i. prelucrarea secventei se poate face prelucrand subsecventele:

si si apoi combinand rezultatele pentru a obtine prelucrarea intregii secvente .

Daca se reuseste o astfel de formalizare a problemei atunci ea poate fi rezolvata cu ajutorul acestei metode.

Vom da in continuare o procedura recursiva in pseudocod:

procedure DI (p,q,α)

if q-p £ eps then

call PREL (p,q,α)

else

call IMPARTE (p,q,m) ;

call DI (p,m,β);

call DI (m+1,q,γ);

call COMB (β,γ,α);

endif;

return;

end procedure

Cateva precizari se impun:

procedura trebuie apelata prin call DI (1,n,α) in α obtinandu-se rezultatul final;

eps este lungimea maxim a unei secvene notata prin (p,q) pentru care se face prelucrarea directa fara a mai fi necesara impartirea in subprobleme;

procedura PREL realizeaza prelucrarea directa a secventelor (p,q);

procedura COMB realizeaza combinarea rezultatelor β si γ ale prelucrarii a doua secvente vecine (p,m) si (m+1,q) obtinand rezultatul α al prelucrarii intregii secvente (p,q);

prin procedura IMPARTE se obtine valoarea lui m.

Vom da ca exemplu problema sortarii crescatoare a unui sir de intregi prin interclasare.

deoarece secventele (i,i+1) sunt usor de ordonat acestea vor constitui secventele ce se vor prelucra, deci eps = 1;



m se va calcula ca (p+q)/2, deci nu mai e nevoie de procedura speciala IMPARTE;

procedura COMB va interclasa intotdeauna doua secvente (p,m) si (m+1,q) ordonate crescator;

vom folosi un vector x drept structura globala si vom face toate prelucrarile pe elementele sale nemaiavand nevoie de zonele α,β;

pentru zona γ vom folosi un vector local y in procedura COMB acesta continand elementele corespondente din x dar ordonate crescator; tot in procedura COMB se vor copia apoi elementele lui y din portiunea (p,q) in x;

evident ca procedurile din schema generala a algoritmului sunt functii C cititorul facand analogiile necesare.

#include <stdio.h>

#include <conio.h>

#define nrelem 100

int x[nrelem];

int n;

void PREL (int p, int q)

void COMB (int inf, int mijloc, int sup)

for(l=i; l<=mijloc; y[k++]=x[l++]);

for(l=j; l<=sup; y[k++]=x[l++]);

for(k=inf; k<=sup; x[k++]=y[k]);

void DI (int p, int q)

return;

void main(void)

DI (1,n);

printf('nsirul sortat crescator este:n');

for (i=1; i<=n; i++) printf('x[%d]=%dn',i,x[i]);

getch();






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 515
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 2022 . All rights reserved

Distribuie URL

Adauga cod HTML in site