Desparte Si Stapineste

7/24/2019 Desparte Si Stapineste

1/25

Silviu GNCU

Programarea Calculatoarelor

Tehnici de programare

Grupele anului II Informatica

ProfesorSilviu Gncu


2/25

Silviu GNCU

Rezolvarea unei probleme prin intermediul acestei metodepresupune:

1. mp#r&irea repetat# a unei probleme de dimensiuni mari )n dou#sau mai multe subprobleme de acela+i tip, dar de dimensiuni maimici.

2. Rezolvarea subproblemelor)n mod direct, dac# dimensiunea lorpermite aceasta, sau )mp#r&irea lor )n alte subprobleme dedimensiuni +i mai mici.

3. Combinarea solu&iilor subproblemelor rezolvate pentru a ob&inesolu&ia problemei ini&iale.

Metoda despartei s t#p&nete


3/25

Silviu GNCU

Descrierea metodei

1. Mul&imea supus#prelucr#rii la un anumit pas al algoritmului:},,,{ 1 jii aaaA K+=

2. mp#r&im mul&imeaA )n dou# submul&imi care vor fi prelucrateseparat:

};,,,{ 11 miii aaaA ++= K

;2)( divijm =

}.,,,{ 212 jmimi aaaA K++++=

3. n continuare, mul&imile A1 +i A2 se )mpart din nou )n c)te dou#submul&imi;

4. Procesul continu#p-n# c-nd solu&iile ce corespund submul&imilorcurente vor putea fi calculate )n mod direct.

5. Combin#m solu&iile ce corespund submul&imilor curente.


4/25

Silviu GNCU

Descompunerea mulimii A #n submulimi

a a a a a a a=( , , , , , , )1 2 3 4 5 6 7

A a a a a1 1 2 3 4=( , , , )

a2-2 7=( )A a a1-1 1 2=( , ) A a a1-2 3 4=( , ) a a2-1 5 6=( , )

A a a a2 5 6 7=( , , )


5/25

Silviu GNCU

Schema general#a algoritmului bazat pe

metoda desparte i s t#p&nete

voidDesparteSiStapineste(inti,intj,tip&x){

intm;

tipx1,x2;

if(SolutieDirecta(i,j)) Prelucrare(i,j,x)else{

m=(j-i)/2;

DesparteSiStapineste(i,i+m,x1);

DesparteSiStapineste(i+m+1,j,x2);

Combina(x1,x2,x);}

}


6/25

Silviu GNCU

Exemplul 1. Suma elementelor unui vector

Fie dat un vector cu urm#toarele elemente:

Modalitatea de determinare a sumei:

Apoi:


7/25

Silviu GNCU

Deoarece s-au ob&inut secven&e de vector de lungime 1, nu se mairealizeaz# descompunerea. Se compun solu&iile subsecven&elor+i sedetermin# solu&iile corespunzatoare


8/25

Silviu GNCU

O soluie de implementare:#include

#include

intv[1000],n;intdivide(intli,intls){

/ / func.ia prime/te ca parametri extremit#.ile din vectorintmij, d1 ,d2;

//mijlocul, d1 /i d2 re.in sumele pe extr. st-ng# respectiv dreapt#if(li!=ls) {

//algoritmul se autoapeleaz# dac# secven.ele au lungime mai mare de 1mij=(li+ls)/2; d1=divide(li,mij); d2=divide(mij+1,ls);returnd1+d2;

}else returnv[li];

}

main(){

coutn;for(inti=0;i


9/25

Silviu GNCU

Poziia final#Poziia iniial#

Toate discurile de pe primul necesit# a fi mutate pe ultimulax, astfel )nc-t num#rul de mut#ri s# fie minim.Exemplu pentru un turn format din 4 discuri.

Exemplul 2. Problema turnurilor din Hanoi


10/25

Silviu GNCU

Regulile jocului

1. La o mutare se deplaseaz#un singur disc.

2. Un disc mai mare nu poate fi pus pesteun disc mai mic.


11/25

Silviu GNCU

Un disc Dou#discuri

O mutare

Trei mut#ri


12/25

Silviu GNCU

&apte mut#ri

Trei discuri


13/25

Silviu GNCU

Numrul

discurilorNumrul minim de mutri

1 1

2 21 + 1 = 3, adic#22 - 1 = 4 - 1 = 3

3 23 + 1 = 7, adic#23 - 1 = 8 - 1 = 7

4 27 + 1 = 15, adic#24 1 = 16 1 = 15

5 215 + 1 = 31, adic#25 1 = 32 1 = 31

6 231 + 1 = 63, adic#26 1 = 64 1 = 63

72

63 + 1 = 127, adic#2

7

1 = 128 1 = 127... ...

64 264 1 = 18.446.744.073.709.551.615 care se cite'te:18 trilioane, 446 biliarde, 744 bilioane, 73 miliarde, 709 milioane, 551 mii, 615.

Tabelul conine num#rul minim de mut#ri necesare:


14/25

Silviu GNCU

Rezolvarea problemei

#include#include

charx,y,z;

intn;

voidhanoi(intn, charx,chary,charz){

if(n==1) cout


15/25

Silviu GNCU

Exemplul 3. T#ierea unei pl#ci de arie maxim#

Se consider# o plac# dreptunghiular# de dimensiunileLH. Placa

aren g#uri punctiforme, fiecare gaur# fiind definit#prin coordonatele (xi,yi). Elabora&i un program care decupeaz# din plac# o bucat# de ariemaxim#, dreptunghiular# +i f#r# g#uri. Sunt admise doar t#ieturi de la omargine la alta pe direc&ii paralele cu laturile pl#cii - verticale sauorizontale.

Placa ini&ial#

),,0,0( HLP=


16/25

Silviu GNCU

T#ierea pe vertical#),,,( dcbaPcurenta =

),,,(1 dxbaP i=

),,,(2 dcbxP i=

T#ierea pe orizontal#

),,,(4 iycbaP =

),,,(3 dcyaP i=


17/25

Silviu GNCU

Agoritmul de rezolvare

1. Ini&ial stabilim aria maxim#Smax = 0.

2. Dac# placa curent# nu are g#uri, problema poate fi solu&ionat# direct,compar-nd aria curent# cu valoarea Smax.

3. n caz contrar alegem o gaur# arbitrar# (xi, yi) prin care t#iem placa curent# )npl#ci mai mici:

P1=(a, b, xi, d); P2=( xi, b, c, d);

P3=(a, yi, c, d); P4=(a, b, c, yi ).

4. n continuare examin#m )n acela+i mod fiecare din pl#cileP1, P2, P3 i P4,

ob&inute )n rezultatul t#ierii, memor-nd consecutiv )n variabilaSmax aria pl#cii de

suprafa maxim#.

5. Procesul de calcul se termin#atunci, c-nd nici una din pl#cile curente P1,P2,P3,P4 nu mai con&ine g#uri.


18/25

Silviu GNCU

#include

#include#include

#include

#include

#define nmax 100

doublex[nmax],y[nmax],smax,amax,bmax,cmax,dmax,l,h;

intn;

voidcitire();

voiddesp(double,double,double,double);

intsolutie(double,double,double,double);

voidPrelucrareSolutie(double,double,double,double);

main(){

citire();smax=0;

desp(0,0,l,h); cout


19/25

Silviu GNCU

Procedura DesparteSiStapineste

voiddesp(doublea,doubleb,doublec,doubled){

intq;

cout


20/25

Silviu GNCU

Func&ia Solutie

intsolutie(doublea,doubleb,doublec,doubled){

intl1,j,z;

z=0;l1=0;

for(j=1;ja && x[j]b && y[j]=smax){

smax=s; amax=a;

bmax=b; cmax=c;

dmax=d;

}

}


21/25

Silviu GNCU

Procedura Citire

voidcitire(){

inti;

ifstream f("date.txt");

f>>n>>l>>h;

for(i=1;i>x[i]>>y[i];

f.close();

cout


22/25

Silviu GNCU

Implementare a metodei desparte &i st(p+ne&te

1. Se alege o valoare pivot. Se ia valoarea elementului din mijloc ca

valoare pivot, dar poate fi oricare alt#valoare, care este )n intervalulvalorilor sortate, chiar dac#nu este prezent#)n tablou.

2. Partiionare, Se rearanjeaz#elementele )n a+a fel )nc-t, toate

elementele care sunt mai mari dec-t pivotul merg )n partea dreapt#atabloului. Valorile egale cu pivotul pot sta )n orice parte a tabloului.n plus, tabloul poate fi )mp#r&it )n p#r&i care nu au aceea+idimensiune (nu sunt egale).

3. Se sorteaz(am+ndou(p(rile.se aplic#recursiv algoritmul desortare rapid#)n partea st-ng#+i )n partea dreapt#.

Algoritmul de partiie#n detaliu.

Exist#2 indici i +i j, +i la )nceputul algoritmului de parti&ionare iindic#primul element al tabloului iar j indic#ultimul element din

tablou. La pasul urm#tor algoritmul mut#i )nainte, p-n#c-nd un

Sortarea rapid(


23/25

Silviu GNCU

Algoritmul de partiie #n detaliu

Exist# 2 indici i +i j, +i la )nceputul algoritmului de parti&ionare i

indic#primul element al tabloului iar j indic# ultimul element din tablou. Lapasul urm#tor algoritmul mut# i )nainte, p-n# c-nd un element cu o valoaremai mare sau egal# cu pivotul este g#sit#. Indicele j este mutat )napoi, p-n#c-nd un element cu valoare mai mic# sau egal# cu pivotul este g#sit#. Dac#i= 10 >= 2, interschimb#m 13 cu 21, 2, 7, 28, 10, 16, 3, 10, 13 - 28 >= 10 >= 10 , interschimb#m 28 cu 101, 2, 7, 10, 10, 16, 3, 28, 13 - 10 >= 10 >= 3, interschimb#m 10 cu 31, 2, 7, 10, 3, 16, 10, 28, 13 - i > j, se opre+te parti&ionarease aplic#din nou algoritmul pentru 1, 2, 7, 10, 3 si 16, 10, 28, 13Se ob&ine: 1, 2, 3, 7, 10, 10, 13, 16, 28 +ir sortat


24/25

Silviu GNCU

Implementare#n C++#include

intt[100],i,n;

voidquickSort(intv[],intst, intdr){inti=st,j=dr,aux,pivot=v[(st+dr)/2];

while(i


25/25

Silviu GNCU

Pentru acas#Problema 1. Se consider # un tablou unidimensional cu

numere )ntregi. Elabora.i un program prin intermediul c#ruia:a) se va determina elementul minimal/maximal;

b) se va afi/a elementele pare/impare;c) se va determina num#rul de elemente prime/neprime;d) se va determina suma elementelor pare/impare;

utiliznd metoda Desparte &i St(p+ne&te.Problema 2. Elabora.i un program pentru simularea jocului

Ghici Num#rul. Se consider# segmentul a, b (se citesc de la tastatur#).n mod aleatoriu se selecteaz# un num#r de pe acest segment [a; b].Prin intermediul programului se va demonstra modalitate de aflare a

num#rului ales la )nt-mplare. La ecran se va afi/a num#rul de itera.iinecesare pentru determinarea num#rului.

Din culegere : Probl. 1-6, pag. 59

Date post:	20-Feb-2018
Category:	Documents
Upload:	vlad-aptefrai
View:	219 times
Download:	0 times

Desparte Si Stapineste

Documents