Metoda Divide – et -Impera

1. Prezentarea generală a metodei

Metoda de programare Divide – et – Impera (dezbină şi stăpâneşte) constă în împărţirea repetată a unei probleme de dimensiuni mari, în două sau mai multe probleme de acelaşi tip dar de dimensiuni mai mici, urmată de rezolvarea fiecăreia dintre aceste probleme pentru obţinerea unui şir de soluţii parţiale care vor fi combinate apoi pentru a obţine soluţia problemei iniţiale.

Dacă fiecare dintre subproblemele obţinute în urma divizării sunt, de asemenea, de dimensiuni mari, algoritmul de divizare continuă pentru fiecare dintre subprobleme în parte.

Se aplică acest procedeu până când se ajunge la o subproblemă de dimensiuni mici care poate fi rezolvată uşor.

Dacă ar fi să exemplificăm metoda Divide - et - Impera într-o situaţie reală, ne putem gândi la un turneu de şah. Într – un astfel de turneu se respect următoarele reguli: se compun echipe de câte 2 jucători din care unul va fi cel victorios. Din jucătorii rămaşi se compun iar echipe de câte 2 jucători din care unul va ieşi victorios. Şi tot asa până când se ajunge la o singură echipă care va avea un singur câştigator. Putem considera că soluţia problemei este acel ultim câştigător cu precizarea că, metoda se aplică exact invers, adică de la o problemă mai mare se fac două mai mici şi fiecare se împarte în alte două mai mici etc.

Datorită modului de funcţionare a metodei, aceasta admite o implementare recursivă.

Presupunem că notăm problema iniţială cu P şi soluţia acesteia cu α iar subproblemele obţinute în urma divizării cu P1, P2, … , Pn cu soluţiile α1, α2, …, αn.

În limbaj natural, metoda Divide – et – Impera ar putea fi descrisă astfel:

algoritm Divide_Impera (P, α)dacă P poate fi rezolvată uşor atunci determină αaltfel

divide P în P1, P2, … , Pn

apelează Divide_Impera (P1, α1)apelează Divide_Impera (P2, α2)……………………………………. apelează Divide_Impera (Pnαn)combina soluţiile α1, α2, …., αn pentru a obţine α

sfârşit algoritm

Observaţie: De obicei, problemele propuse spre rezolvare necesită descompunerea în două subprobleme, nu neapărat de dimensiuni egale.

2. Implementarea metodei Divide – et – Impera

Putem considera problema iniţială ca un şir de elemente xp, xp+1, xp+2, … , xq-1, xq

(p ≤ q) asupra căruia trebuie făcută o prelucrare oarecare.1

Rezolvarea problemei:

(1) Se calculează mijlocul şirului: .

(2) Se aplică algoritmul Divide – et – Impera pentru prima jumătate, adică pentru subşirul xp, xp+1, xp+2, … , xm (p ≤ m).

(3) Se aplică algoritmul Divide – et – Impera pentru a doua jumătate, adică pentru subşirul xm+1, xm+2, … , xq (m < q).Pentru fiecare subşir se va obţine câte o soluţie.

Notă: Se poate opta ca elementul din mijloc (în cazul în care şirul are număr impar de elemente) să fie în primul subşir şi, în consecinţă, se vor lua în considerare subşirurile xp, xp+1, xp+2, … , xm+1 (p< m). xm, xm+1, … , xq (m≤q).

(4) Cele două soluţii se vor combina pentru a obţine soluţia şirului iniţial.

Rezultă următorul algoritm:

algoritm Divide_et_Impera (p, q, α)dacă q – p < d atunci prelucrează (p, q, α)altfel

divide (p, q, m) //pasul (1)apelează Divide_et_Impera (p, m, β) //pasul (2)apelează Divide_et_Impera (m+1, q, γ) //pasul (3)combina (β, γ, α) //pasul (4)

sfârşit algoritm

Observaţie: d = gradul de detaliu pentru care problema poate fi rezolvată uşor (de obicei are

valoarea 1)α = soluţia şirului iniţialβ = soluţia primului subşirγ = soluţia celui de-al doilea subşir

Notă: Ceea ce trebuie avut în vedere la metoda Divide – et – Impera (şi acest aspect se va repeta şi la alte metode de programare) este faptul că problema nu trebuie privită în ansamblu, ci impărţită intr-o problemă mai mică şi rezolvată doar privind din perspectiva problemei mici (adică ce se întâmplă în acel moment). Dacă algoritmul este descris corect si recursivitatea merge bine, atunci cu siguranţă şi soluţia problemei mari (iniţială) va fi corectă.

3. Aplicaţii

1) Se citesc de la tastatură două numere naturale n şi k (n >k). Să se calculeze,

utilizând o rezolvare recursivă, , conform formulei de recurenţă:

2

#include <conio.h>#include <stdio.h>

unsigned int comb(unsigned int n, unsigned int k){if ((k==0) || (k==n)) return 1; //condiţii de oprireelse return comb(n-1, k-1)+comb(n-1,k); //apelul recursiv (de 2 ori)}

void main(){unsigned int n, k;printf("n=");scanf("%u",&n);do{printf("k=");scanf("%u",&k);}while (k>n);printf("%u",comb(n,k)); //apelarea funcţiei recursivegetch();}

Deoarece Divide – et – Impera înseamnă, implicit, recursivitate, se observă cu uşurinţă condiţiile de oprire, care sunt de fapt, cazurile particulare de la formula de calcul a combinărilor (k=1 şi k=n). Se consideră ca şi aplicaţie a acestei metode datorită celor două apeluri pentru valori modificate ale lui k şi n. Se observă că la acest exemplu, problema iniţială nu s-a descompus în două subprobleme mai mici dar de aceeaşi dimensiune. Conform formulei, se consideră că s-a descompus într-o subproblemă de dimensiune 1 şi o subproblemă de dimensiune n-1.

Ca şi în cazul şirului lui Fibonacci, implementarea recursivă a acestei probleme este utilă doar pentru a arăta adâncimea recursivităţii deoarece varianta iterativă este mult mai eficientă decât cea recursivă.

n=6k=2comb(6,2)=comb(5,1)=5 +comb(5,2)*=10 / 1 comb(4,0)+comb(4,1) / 1 comb(3,0)+comb(3,1) / 1 comb(2,0)+comb(2,1) / comb(1,0)+comb(1,1)=1+1=2comb(5,2)* =comb(4,1)+ comb(4,2)=6

3

/ \ comb(3,0)+comb(3,1)=4 comb(3,1)=3 +comb(3,2) / comb(2,1)+comb(2,2)=3

2) Se citeşte de la tastatură un număr natural n şi un şir de n numere naturale. Să se calculeze, utilizând o rezolvare recursivă, suma numerelor citite.

#include <conio.h>#include <stdio.h>int v[50];

void citire(int v[50], unsigned int &n){unsigned int i;do{printf("n=");scanf("%d",&n);}while (n>=50);for (i=0; i<n; i++)

{printf("v[%u]=",i);scanf("%d",&v[i]);}

}int suma(unsigned int i, unsigned int j){unsigned int m;int a, b;if (i>j) return 0;else if (i==j) return v[i]; else {

m=(i+j)/2; a=suma(i, m); b=suma(m+1,j); return a+b; }

}

void main(){unsigned int n;citire(v,n);printf("%d",suma(0,n-1));

4

getch();}

Pentru a calcula suma elementelor dintr-un vector utilizând metoda Divide – et – Impera se împarte (vectorul delimitat de capetele i şi j) in 2 subvectori de dimensiuni aproximativ egale (în cazul în care vectorul iniţial are număr impar de elemente, atunci cel de-al doilea subvector va avea cu un element in plus), delimitaţi de capetele i, m şi j, se calculează pentru fiecare dintre aceşti doi subvectori suma elementelor, se obţin 2 sume care se adună pentru a obţine suma finală (a tuturor elementelor).

În cazul în care subvectorul are un singur element, atunci suma va fi egală cu valoarea acelui element (condiţia de oprire).

Trebuie acordată o mare atenţie variabilelor locale din funcţie deoarece acestea se restaurează din stivă de fiecare dată când se revine din apelul recursiv. Dacă aceste variabile ar fi globale atunci nu s-ar mai calcula corect soluţia problemei.

Exemplu

3) Se citeşte de la tastatură un număr natural n şi un şir de n numere naturale. Să se calculeze, utilizând o rezolvare recursivă, cel mai mare divizor comun al numerelor citite.

#include <conio.h>#include <stdio.h>unsigned int v[50];

void citire(unsigned int v[50], unsigned int &n){unsigned int i;do{printf("n=");scanf("%d",&n);}while (n>=50);for (i=0; i<n; i++)

{printf("v[%u]=",i);scanf("%u",&v[i]);}

}unsigned int cmmdc(unsigned int i, unsigned int j){unsigned int m, a, b;if (i==j) return v[i]; else {

m=(i+j)/2; a=cmmdc(i, m); b=cmmdc(m+1,j);

5

while (a!=b)if (a>b) a-=b;else b-=a;

return a; }

}

void main(){unsigned int n;citire(v,n);printf("%u", cmmdc(0,n-1));getch();}

La fel ca la problema anterioară, se împarte vectorul in 2 subvectori de dimensiuni aproximativ egale, se calculează pentru fiecare dintre aceşti doi subvectori cel mai mare divizor comun al lor, se obţin 2 valori pentru care se poate aplica un algoritm standard de calcul al c.m.m.d.c. – ului cu scopul de a obţine soluţia problemei date.

În cazul în care subvectorul are un singur element, se consideră acela ca fiind c.m.m.d.c.

Exemplu

4) Se citeşte de la tastatură un număr natural n şi un şir de n numere naturale. Să se determine, utilizând o rezolvare recursivă, cel mai mare număr dintre cele citite.

#include <conio.h>#include <stdio.h>int v[50];

void citire(int v[50], unsigned int &n){unsigned int i;do{printf("n=");scanf("%d",&n);}while (n>=50);for (i=0; i<n; i++)

{printf("v[%u]=",i);scanf("%d",&v[i]);

6

}}int max(unsigned int i, unsigned int j){unsigned int m, a, b;if (i==j) return v[i]; else {

m=(i+j)/2; a=max(i, m); b=max(m+1,j); if (a>b) return a; else return b; }

}

void main(){unsigned int n;citire(v,n);printf("%d", max(0,n-1));getch();}

Aceeaşi idee de rezolvare ca la suma elementelor dintr-un vector şi determinarea celui mai mare divizor comun al elementelor dintr-un vector.

5) Problema Turnurilor din Hanoi1: Se dau trei tije numerotate a, b şi c şi n discuri perforate de diametre diferite. Iniţial, toate discurile se află pe tija a, în ordinea crescătoare a diametrelor lor, de la baza tijei către vârf. Problema cere să se mute toate discurile de pe tija a pe tija b, utilizând ca intermediară tija c şi respectând următoarele reguli: La fiecare pas se mută un singur disc; Nu este permisă aşezarea unui disc de diametru mai mare peste un disc

de diametru mai mic;

#include <conio.h>#include <stdio.h>

1 Acest "joc" a fost inventat de matematicianul francez Edouard Lucas, în 1883. Există totuşi o legendă străveche care aminteşte de un joc similar, ce se desfăşura într-o cameră dintr-un templu indian, unde potrivit legendei, se găseau 64 de discuri de aur, care erau mutate de preoţii templului, adepţi ai lui Brahma, în jurul a 3 stâlpi. Se pare că aceştia îndeplineau astfel o porunca divină, crezând că finalizarea jocului va coincide cu sfârşitul lumii - http://turnuriledinhanoi.blogspot.com/

7

void Hanoi (unsigned int n, char a, char b, char c){if (n==1) printf("%c --> %c\n", a,b); else {

Hanoi(n-1,a,c,b); printf("%c --> %c\n", a,b); Hanoi(n-1,c,b,a); }

}

void main(){unsigned int n;char a='a', b='b', c='c';printf("n=");scanf("%u",&n);Hanoi(n,a,b,c);getch();}

Pentru a muta n discuri de pe tija a pe tija b (indiferent cât este n) trebuie: să se mute n-1 discuri de pe tija a pe c (pentru a lăsa un singur disc pe

tija a – cel mai mare iar tija b să fie goală); să se mute acel unic disc rămas de pe tija a pe tija b; sa se mute cele n-1 discuri de pe tija c pe tija b;

Cum se vor muta cele n – 1 discuri de pe o tijă pe cealaltă nu trebuie să ne preocupe foarte mult deoarece stiva folosită de recursivitate îşi joacă rolul foarte bine aici. Ceea ce trebuie însă să ne preocupe este ca acei 3 paşi enunţaţi mai sus să fie făcuţi corect.

Evident că dacă n=1 (caz particular) atunci se opreşte şirul apelurilor recursive.

Exemplu: n=3

se mută un disc (diametrul cel mai mic) de pe tija a pe tija b

8

Tija b Tija cTija a

Tija b Tija cTija a

se mută un disc (diametrul mijlociu ) de pe tija a pe tija b

se mută un disc (diametrul cel mai mic) de pe tija b pe tija c. În acest fel s-a eliberat tija b iar cele 2 discuri de pe tija c sunt aşezate corect.

se mută discul rămas pe tija a (diametrul cel mai mare) pe tija b. În acest fel s-a eliberat tija a şi poate fi utilizată pentru a manevra cele 2 discuri de pe tija c.

se mută primul disc (diametrul cel mai mic) pe tija c pe tija a. În acest fel s-a eliberat discul cu diametrul mijlociu şi poate fi mutat la locul lui final.

9

Tija b Tija cTija a

Tija b Tija cTija a

Tija b Tija cTija a

Tija b Tija cTija a

se mută discul cu diiametrul cel mai mic pe tija a pe tija b.

se încheie şirul mutărilor discurilor.

Se procedează în acelaşi mod şi pentru valori mai mari ale lui n, doar că numărul de mutări va fi mult mai mare.

6) Problema tăieturilor2: Se dă o bucată dreptunghiulară de tablă cu lungimea L şi înălţimea H (L şi H fiind două numere naturale citite de la tastatură), pe care ne-o imaginăm aşezată în cadranul I al unui sistem cartezian de coordonate, cu un colţ al bucăţii de tablă în originea O. Bucata de tablă are pe suprafaţa ei n găuri de coordonate numere naturale (valori citite dintr-un fişier text). Se cere să se decupeze din tablă o bucată dreptunghiulară de arie maximă care nu conţine găuri. Precizăm ca diametrul unei găuri oarecare este suficient de mic astfel încât în urma unei tăieturi pe o direcţie care conţine o gaură se obţin margini drepte, nu ondulate.

#include <conio.h>#include <stdio.h>#include <string.h>#include <stdlib.h>

int x[50],y[50],n,H,L;int aria_max=0,x_max,y_max,h_max,l_max;

void citire(){

2 “Tehnici de programare (aplicaţii de laborator)”, Cornelia Ivaşc şi Mona Prună, Ed. Petrion, Bucureşti, 199910

Tija b Tija cTija a

Tija b Tija cTija a

unsigned int i;FILE *f;

f=fopen("pliere.txt","r");if (f!= NULL)

{fscanf(f,"%d%d",&H,&L);fscanf(f,"%d",&n);for(i=0;i<n;i++) fscanf(f,"%d%d",&x[i],&y[i]);}

fclose(f);}

int gasit (int i,int xp,int yp,int hp,int lp){if ((x[i]>xp) && (x[i]<xp+lp) && (y[i]>yp) && (y[i]<yp+hp)) return 1;else return 0;}

void taie (int xp,int yp,int lp, int hp){unsigned int i;i=0;while ((i<n) && (!gasit(i,xp,yp,hp,lp))) i++;if (i<n)

{taie(xp, yp, lp, y[i]-yp);taie(xp, y[i],lp, yp+hp-y[i]);taie(xp, yp, x[i]-xp, hp);taie(x[i],yp, xp+lp-x[i], hp);}

else if (aria_max<lp*hp){aria_max=lp*hp;x_max=xp;y_max=yp;l_max=lp;h_max=hp;}

}void main(){citire();taie(0,0,H,L);printf("\nPlaca obtinuta are aria maxima %d\n",aria_max);printf("si are coordonatele %d, %d\n",x_max, y_max);printf("cu inaltimea %d si latimea %d",h_max, l_max);

11

getch();}

Placa inţială are colţul din stânga jos în punctul de coordonate (0, 0), lungimea L şi înălţimea H, conform desenului de mai jos. Pe această placă se găsesc n găuri ale căror coordonate sunt păstrate în vectorii x (coodonata x) şi y (coordonata y).

Să presupunem că în urma divizării plăcii iniţiale, conform algoritmului Divide – et – Impera s-a obţinut o placă având colţul stânga – jos în punctul de coordonate (xp, yp) şi care are lungimea lp şi înălţimea hp. Această bucată de placă ar putea conţine şi ea, la rândul ei, găuri. Se caută prima gaură din această placă, cu ajutorul funcţiei găsit. Această funcţie verifică daca un anumit punct, de coordonate (x[i], y[i]), se încadrează în grafic între limitele plăcii curente.

Parcurgerea găurilor din placă se face în cadrul funcţiei taie (funcţia care implementează algoritmul de divizare). În cazul în care nu se mai găseşte nici o gaură în placă atunci se consideră şirul apelurilor recursive încheiat, s-a ajuns la o placa fără găuri, i se calculează acesteia aria şi în cazul în care aria acestei bucăţi de placă este mai mare decât cea presupusă maximă se actualizează variabilele pentru aria maximă, coordonatele colţului stânga-jos al plăcii finale, lăţimea şi înălţimea acesteia.

Să presupunem că pe placă se găseşte o gaură de coordonate (x[i], y[i]), conform desenului de mai jos.

12

(0, 0) X

Y

L

H

(0, 0)

Y

xp+lp

yp+hp

x[i]xp

y[i]

yp

Astfel, placa poate fi tăiată în două moduri: printr-o linie orizontală şi printr-o linie vertical. Pentru a găsi porţiunea din placă de arie cea mai mare vor trebui luate în considerare toate modalităţile de tăiere. În urma fiecărei tăieri se obţin câte 2 plăci mai mici, deci, în final vor fi 4 variante.Dacă se taie placa printr-o linie orizontală se obţin, co

13

X

(0, 0)

Y

xp+lp

yp+hp

x[i]xp

y[i]

yp

(0, 0)

Y

xp+lp

yp+hp

x[i]xp

y[i]

yp

7) Problema plierilor3: Se consideră un vector de lungime n. Definim plierea vectorului prin suprapunerea unei jumătăţi, numită donatoare, peste cealaltă jumătate, numită receptoare, cu precizarea că dacă numărul de elemente este impar, elemental din mijloc este eliminat. Prin pliere, elementele subvectorului obţinut vor avea numerotarea jumătăţii receptoare. Plierea se poate aplica în mod repetat, până când se ajunge la un subvector format dintr-un singur element, numit element final. Scrieţi un program care să afişeze toate elementele finale posibile şi să se figureze pe ecran pentru fiecare element final o succesiune de plieri.

#include <conio.h>#include <stdio.h>#include <string.h>#include <stdlib.h>int v[50];

void pliere (int i, int j, char *s){int ms,md;char *sir3="";if (i==j) {printf("%d: ",v[i]);

puts(s); }else { if ((j-i+1)%2!=0) ms=(i+j)/2-1; else ms=(i+j)/2; md=(i+j)/2+1; itoa(ms,sir3,10); strcat(sir3," " ); strcat(strcat(s,"S"),sir3);

pliere(i,ms,s); s[strlen(s)-3]=NULL;

itoa(md,sir3,10); strcat(sir3," " ); strcat(strcat(s,"D"),sir3);

pliere(md,j,s); s[strlen(s)-3]=NULL; }}void main()

3 Olimpiada nationala, Arad, 1992 - text modificat. Sursa: “Informatica, manual pentru clasa aX-a”, Emanuela Cherchez, Mainel Şerban Ed. Polirom, Iaşi, 2000

14

{int n,i;char *s="";

do{printf("n=");scanf("%d",&n);}while ((n<=0)||(n>=50));for (i=1; i<=n; i++)

{printf("v[%u]=",i);scanf("%d",&v[i]);}

pliere(1,n,s);getch();}

8) Fractali4. Definiţia fractalului ar fi “o figură geometrică fragmentată care poate fi subdivizată în părţi care sunt (măcar aproximativ) o copie la scarăredusă a întregii figure”.

Fractalul, ca obiect geometric, are în general următoarele caracteristici: Are o structură fină la scări arbitrar de mici. Este prea neregulat pentru a fi descris în limbaj geometric euclidian

tradiţional. Este autosimilar (măcar aproximativ sau stochastic). Are o definiţie simplă şi recursivă. Dimensiunea geometrică a unui fractal se bazează pe dimensiunea

Hausdorff, care este o extensie a dimensiunii euclidiene. Dacă în geometria euclidiana un obiect nu are decât o dimensiune întreagă, în geometria fractală dimensiunile sunt, în general, numere reale neîntregi pozitive.

Geometria fractalilor nu recunoaşte linia, suprafaţa, volumul. Sunt caracterizati de dimensiunea fractalã - "un număr care cuantifică

gradul de neregularitate şi de fragmentare al unei structuri geometrice sau al unui obiect din natură"

Deoarece par identici la orice nivel de magnificare, fractalii sunt de obicei consideraţi ca fiind infinit complecşi (în termeni informali).

Printre obiectele naturale care aproximează fractalii până la un anumit nivel se numără norii, lanţurile montane, arcele de fulger, liniile de coastă şi fulgii de zăpadă.

Totuşi, nu toate obiectele autosimilare sunt fractali – de exemplu, linia reală (o linie dreaptă Euclidiană) este autosimilară, dar nu îndeplineşte celelalte caracteristici.

Domenii de aplicabilitate a fractalilor:• Medicina, climatologia, geologia, seismica şi chiar marketingul şi economia,

utilizează programele de simulare fractală.

4 Termenul fractal provine din latinescul fractus, care înseamnă "spart“, "fracturat" (termen introdus de Benoît Mandelbrot, în 1975) – sursa Wikipedia

15

• Seismologii vorbesc de valuri fractale ce străbat scoarţa pământului.• Psihologii vorbesc de aşa numitele boli dinamice ce apar în momentul

desincronizării fractalilor, sau cum ar spune medicina indiană – atunci când omul iese din armonia Universului.

• Cu ajutorul simulărilor fractale (sau fractaliere) ale lui Mandelbrot a fost posibilă prezicerea cu mare exactitate a variaţiei preţului de bursă al bumbacului.

• Geneticienii sunt convinşi că molecula ADN/DNA este unul dintre cele mai complicate modele fractale existente în natură şi reprezintă prin excelenţă acea “similaritate cu sinele cât şi principiul “părţii asemănătoare cu întregul”.

• Fractalii sunt de asemenea predominanţi în arta şi arhitectura africană. Casele circulare apar în cercuri de cercuri, casele dreptunghiulare în dreptunghiuri de dreptunghiuri şi aşa mai departe. Astfel de tipare se găsesc şi în textile şi sculpturile africane, precum şi în părul împletit în codiţe

#include <graphics.h>#include <stdlib.h>#include <stdio.h>#include <conio.h>#include <math.h>#include <dos.h>

void patrat(int x,int y,int l){int l2;l2=l/2;rectangle(x-l2,y-l2,x+l2,y+l2);

16

delay(500);}

void cerc (int x,int y,int r){circle(x,y,r);delay(500);}

void diamant(int x,int y,int l,int x1,int y1,int r){const c=3.3;int l2,l3;if (l>0){

patrat(x,y,l);cerc(x1,y1,r);l2=l/2;l3=floor(l/c);r=r/2;diamant(x-l2,y,l3,x1-l2,y1-l2,r);diamant(x, y-l2, l3, x1-l2, y1+l2,r);diamant (x+l2,y,l3, x1+l2,y1-l2,r);diamant (x, y+l2,l3,x1+l2,y1+l2,r);}

}

int main(void){ int gdriver = DETECT, gmode, errorcode;

initgraph(&gdriver, &gmode, ""); errorcode = graphresult();

if (errorcode != grOk) { printf("Graphics error: %s\n", grapherrormsg(errorcode)); printf("Press any key to halt:"); getch(); exit(1); }

diamant(getmaxx()/2, getmaxy()/2, getmaxy()/2, getmaxx()/2, getmaxy()/2, getmaxy()/5); getch();

17

closegraph(); return 0;}

4. Algoritmi de căutare.Căutarea binară

EnunţFie un şir de n numere intregi (n≥1) cu proprietatea că sunt ordonate crescător şi o valoare întreagă x. Să se verifice dacă valoarea x se află printre elementele vectorului, afişându-se pe ecran un mesaj corespunzător.

Soluţie#include <conio.h>#include <stdio.h>#include <string.h>#include <stdlib.h>

int v[50], n,x;

void citire(){unsigned int i;FILE *f;

f=fopen("cautare.txt","r");if (f!= NULL)

{fscanf(f,"%d",&n);for(i=0;i<n;i++) fscanf(f,"%d",&v[i]);fscanf(f,"%d",&x);}

fclose(f);}

int cautare(int i, int j){int m;if (i>j) return 0;else { m=(i+j)/2; if (v[m]==x) return m; else if (x<v[m]) return cautare(i,m-1);

else return cautare(m+1,j); }}void main()

18

{int p;citire();p=cautare(0,n-1);if (p) printf("Numarul %d se afla pe pozitia %d",x,p);else printf("Numarul %d nu se afla printre elementele vectorului",x);getch();}

5. Sortarea prin interclasare

EnunţFie un şir de n numere intregi (n≥1). Să se ordoneze crescător numerele citite folosind metoda de sortare prin interclasare (Merge Sort).

Soluţie

#include <conio.h>#include <stdio.h>#include <string.h>#include <stdlib.h>

int v[50], n,x;

void citire(){int i;FILE *f;

f=fopen("intercl.txt","r");if (f!= NULL)

{fscanf(f,"%d",&n);for(i=0;i<n;i++) fscanf(f,"%d",&v[i]);}

fclose(f);}

void afisare(){int i;for (i=0; i<n; i++)

printf("%d ",v[i]);printf("\n");}

void Interclaseaza (int ls, int m, int ld)

19

{int i,j,k, aux[50];i=ls;j=m+1;k=ls;while ((i<=m) && (j<=ld))

if (v[i]<v[j])aux[k++]=v[i++];

else aux[k++]=v[j++];while (i<=m) aux[k++]=v[i++];while (j<=ld) aux[k++]=v[j++];for (k=ls;k<=ld;k++)

v[k]=aux[k];

}

void MergeSort(int i, int j){int m;if (i<j)

{m=(i+j)/2;MergeSort(i,m);MergeSort(m+1,j);Interclaseaza(i,m,j);}

}

void main(){int p;citire();afisare();MergeSort(0,n-1);afisare();getch();}

6. Sortarea rapidă (Quick Sort)

EnunţFie un şir de n numere intregi (n≥1). Să se ordoneze crescător numerele citite folosind metoda sortării rapide (Quick Sort).

Soluţie#include <conio.h>#include <stdio.h>

20

#include <string.h>#include <stdlib.h>

int v[50], n,x;

void citire(){int i;FILE *f;

f=fopen("quick.txt","r");if (f!= NULL)

{fscanf(f,"%d",&n);for(i=0;i<n;i++) fscanf(f,"%d",&v[i]);}

fclose(f);}

void afisare(){int i;for (i=0; i<n; i++)

printf("%d ",v[i]);printf("\n");}

int pivot (int ls, int ld){int i,j,t,aux;i=ls;j=ld;t=1;while (i<j)

{if (v[i]>v[j])

{aux=v[i];v[i]=v[j];v[j]=aux;t=abs(1-t);}

if (t) j--;else i++;}

return i;}

21

void QuickSort(int i, int j){int p;if (i<j)

{p=pivot(i,j);QuickSort(i,p);QuickSort(p+1,j);}

}

void main(){int p;citire();afisare();QuickSort(0,n-1);afisare();getch();}

22