Conf.univ.dr.DORUANASTASIUPOPESCU ABSOLVENT CRISTINACALACAN Pitești 2020 2UNIVERSITATEADINPITEȘTI FACULTATEADEȘTIINȚE,EDUCAȚIEFIZICĂȘIINFORMATICĂ… [611419]

1UNIVERSITATEADINPITEȘTI
FACULTATEADEȘTIINȚE,EDUCAȚIEFIZICĂȘIINFORMATICĂ
PROGRAMDESTUDIILICENȚĂ
LUCRAREDELICENȚĂ
COORDONATORȘTIINȚIFIC
Conf.univ.dr.DORUANASTASIUPOPESCU
ABSOLVENT: [anonimizat]
2020

2UNIVERSITATEADINPITEȘTI
FACULTATEADEȘTIINȚE,EDUCAȚIEFIZICĂȘIINFORMATICĂ
PROGRAMDESTUDIILICENȚĂ
FOLOSIREATEHNICILORDEPROGRAMAREPENTRU
REZOLVAREAPROBLEMELORDEMATEMATICĂ
COORDONATORȘTIINȚIFIC
Conf.univ.dr.DORUANASTASIUPOPESCU
ABSOLVENT: [anonimizat]
2020

3Introducere……………………………………………………………………………………………………….4
CAPITOLULI:MetodaBacktraking……………………………………………………………………5
I.1.Generareapermutărilormulțimii…………………………………………………………….9
I.2.Generareaaranjamentelor…………………………………………………………………11
I.3.Generareacombinărilor……………………………………………………………………….12
I.4)PRODUSCARTEZIAN……………………………………………………………………..14
I.5.Submulțimileuneimulțimi…………………………………………………………………..15
I.6)Partițiileunuinumăr……………………………………………………………………………16
I.7)Problemaparantezelor:………………………………………………………………………..17
I.8)Anagrameleunuicuvânt………………………………………………………………………18
I.9.Descompunereaunuinumărînsumadenumereprime……………………………19
I.10)Problemacelorndamepeotablădeșah………………………………………………21
I.11..Problemacomisuluivoiajor(agentuluidevânzări)……………………………….28
I.12)Pătratemagice…………………………………………………………………………………..30
I.13)Problemalabirintului:……………………………………………………………………….32
I.14)Sărituracalului…………………………………………………………………………………35
I.15)Sudoku…………………………………………………………………………………………….37
CapitolulalII-lea:MetodaGreedy…………………………………………………………………….40
II.1)Problemabanilor……………………………………………………………………………….40
II.2:Problema:Fracțiaegipteană……………………………………………………………….41
II.3)ProblemaColorăriihărților…………………………………………………………………43
II.4)Problema:Programareaspectacolelor………………………………………………….45
II.5)ProblemaComisvoiajorul………………………………………………………………….47
II.6)ProblemaRucsacului(fracționară)……………………………………………………….48
II.7)ProblemaHoțiișipolițiștii………………………………………………………………….49
II.8)ProblemaRafturilor……………………………………………………………………………51
II.9)ProblemaSumaariilorunordreptunghiuri…………………………………………….52
II.10)ProblemaRezervărilorîncadrulunuihotel…………………………………………54
II.11)ProblemaOrdinealexicografică…………………………………………………………55
II.12)ProblemaSarciniledelucru………………………………………………………………57
CapitolulalIII-lea:DIVIDEETIMPERA…………………………………………………………58
III.1)Problemă:Sumaelementelordintr-unvector………………………………………..59
III.2)Celmaimaredivizorcomun………………………………………………………………60
III.3).Rădăcinadeordin3………………………………………………………………………….61
III.4)MergeSort……………………………………………………………………………………….61
III.5)QuickSort………………………………………………………………………………………..63
III.6)Căutareabinară………………………………………………………………………………..65
III.7)Sumaelementelorprimedintr-unvector……………………………………………..66
III.8)Sumaprodusdedoitermeniconsecutivi……………………………………………67
III.9)Metodabisectieiuneifunctiipeintervale…………………………………………….68
Bibliografie:……………………………………………………………………………………………………69

4Introducere
Înrezolvareaproblemelordematematică,nuexistădoarunsingur
algoritmcaresăfiesoluțiatuturor.Înfuncțiedecomplexitateaproblemelorde
matematică,poțifolosidiferitetehnicideprogramarepentruaobținesoluțiiledorite.
TemaacesteilucrăriesteFolosireatehnicilordeprogramarepentru
rezolvareaproblemelordematematicășiconținemetodele:Backtracking,Greedyși
DivideetImpera.
PrimulcapitolabordeazămetodaBacktracking.Aceastămetodăajutăla
rezolvareaproblemelorundetrebuiesăscriemtoatesoluțiilesale.Esteometodacare
necesitămulttimpșinumereupoatefiaplicată.Backtrackingulesteometodă
importantăpentrurezolvareasauîndeplinireaunorconstrângeridinproblemeca:
sudoku,puzzleurietc,pentruoptimizareaunorproblemedecombinatorică.
Backtraking-ulesteadeseafolositînlimbajeledeprogramarelogicăcaIcon,Planner
sauProlog.
ÎnaaldoileacapitolesteprezentatămetodaGreedy.Aceastămetodăiaîn
considerareconstrucțiauneisoluțiioptime,fărăsăconstruiascătoatesoluțiileposibile.
Aceastămetodapoatefiaplicatăcusuccesînproblemeledematematicăatuncicând
avemofuncțieobiectiv(deminimizaresaumaximizare).AlgorimulGreedyface
alegerilafiecarepasșiîntotdeaunaseasigurăcăfuncțiaobiectivesteoptimizată.Un
dezavantajalacesteimetodeestecătrebuiesămunceștimaimultpentruaînțelegeși
rezolvaproblemeledinpunctdevederealconstrângerilor,alcondițiilor.
Ultimulcapitolprezintădiferiteproblemecareserezolvăcuajutorul
metodeiDivideetImpera.Numărulacestorproblemeesterelativmic,deoarecenu
oriceproblemădematematicăpoatefidescompusăîndiferitesubproblemedeacelași
tip.

5CAPITOLULI:MetodaBacktraking
Decelemaimulteoriînpractică,avemderezolvatproblemecareauun
numărmaredesoluțiiposibile.Uneoriînsă,nuneintereseazătoatesoluțiile,cidoar
aceleacareîndeplinescanumitecondițiispecificeproblemei.Pentruacesttipde
problemeesteindicatsăfolosimmetodabackstracking.
Backtrackings-arputeatraduce"urmărireînapoi"ceeacesugereazăfaptulcă
oricevectorsoluțieesteconstruitprogresiv,începândcuprimacomponentăși
mergândcătreultima,cueventualereveniri(urmăriri)asupravaloriloratribuite
anterior(cuunulsaumaimulțipașiînapoi).
Termenul„backtrack”afostinventatdematematicianulamericanD.H.Lehmer
înanii1950.
Backtrackingulesteutillarezolvareaunorproblemedesatisfacerea
constrângerilor,cumarficuvinteleîncrucișate,jocuridesudokușialteprobleme
similare.
MetodaBacktrackingsefoloseșteînrezolvareaproblemelorcareîndeplinesc
simultanurmătoarelecondiții:
1.Trebuiegeneratetoatesoluțiileproblemei
2.Soluțiapoatefipusăsubformaunuivectoracăruielementeaparținunor
mulțimifiniteșiseaflăîntr-oordinestabilită
3.Nusedispunedenicioaltărezolvaremairapidă
MetodaBacktrackingesteunadestuldecostisitoare,însensulcăeaconsumă
multtimpșimultămemorie,darsuntproblemepracticepentrucarenuavemalte
metodemaibunederezolvare.Uneledintreelevorfirezolvateînacestcapitol.
Chiardacăeometodăcostisitoare,pentruanumiteproblemeeanupoatefi
evitată,neexistândaltemetodecuoeficiențămaibună.Easedovedeșteutilăîn
problemeșijocuridelogică(cumarfijoculdeșah,joculsudoku,foartemultejocuri
detippuzzle,rebusșialtele),înuneleaplicațiidindomeniulmatematiciicumarfi:
generareapermutărilor,aaranjamentelor,combinări,partițiialeuneimulțimi,etc.
Descriereametodei:BACKTRAKING
Backtrackingesteotehnicăcaresefoloseștepentruadecidecaresoluțiinu
trebuiescfigenerate.
Backtrackingesteunalgoritmpentruarezolvaproblemerecursivîncercândsă
construiascăsoluțiaprinincrementare,câteoparteperând,înlocuindacelesoluții
carenusatisfaccondițiileproblemeilaunanumitmomentdat.
Acestecondițiispecificeproblemeisenumesccondițiidevalidaresau
condițiiinterne.
Soluțiilesuntconstruiteîntr-omanierăincrementalăpringăsireasuccesivăa
valorilorpotrivitepentrucomponente(lafiecareetapăsecompleteazăocomponentă;

6osoluțieîncaredoaropartedintrecomponentesuntcompletate,senumeștesoluție
parțială.
Fiecaresoluțieparțialăesteevaluatăcuscopuldeastabilidacăestevalidă.O
soluțievalidăpoateconducelaosoluțiefinală,pecândunainvalidăîncalcă
restricțiileparțiale,ceeaceînsemnăcănuvaconduceniciodatălaosoluțiecaresă
satisfacătoaterestricțiileproblemei.
Dacăniciocomponenentănuconducelaosoluțieparțialăvalidă,atuncise
revinelaocomponentăanterioarășiseîncearcăaltăvaloarepentruaceasta.
Soluțiileproblemeisevorgenerarândperândîntr-ostivăimplementatăsubforma
unuivectorpecareîlvomnotast.
Reamintim:
A)StivafuncționeazădupăprincipiulLIFO(lastin,firstout)
B)Pentruasimulacaracteruldestivă,vomobservavectorulstcașicumelementele
salesuntașezatepeverticală,unulpestealtul.
Metodautilizeazăstructuradetipstivășipoatefiprogramatăatâtiterativcâtși
recursiv.
Stivaesteaceaformădeorganizareadatelor(structurădedate)cuproprietatea
căoperațiiledeintroducereșiscoatereadatelorsefacînvârfulei.
C)Îngeneral,număruldeelementecareintrăîncomponențasoluțiilor,poatesădifere
delaosoluțielaalta.Pentruînceputvomstudiacazulîncaretoatesoluțiileauacelași
numărdeelemente.
Stivastvaconțineunnumărdenelemente.Astfeloconfigurațieavectorului
stivăstformatădinelementele(1st,2st,3st,…,nst)sevanumisoluțiefinală.
Fiecaresoluțieistvaluavaloridintr-oanumitămulțimeiS,cui=1,2,…,n.
Particularizămșiconsiderămcătoatecomponenteleistiauvaloriînaceeași
mulțimeS.
AnsamblulmulțimiloriS,adicăprodusulcarteziannSSS …2 1 se
numeștespațiulsoluțilorposibile.
DimensiuneaspațiuluisoluțiilorposibileestenScardScardScard … 2 1  .
Fiecaresoluțievaficonstruităînstivast,pascupas,completândstivanivelcu
nivel.
Astfelpentruaobțineosoluțiefinalăcunnivele,deformast=
(1st,2st,3st,…,nst),vomanalizanișteconfigurațiiintermediarealestivei
numitesoluțiiparțiale.
Cualtecuvinte,osoluțieparțială(1st,2st,3st,…,kst),undekvalua
succesivtoatevaloriledela1lan.Larândulsăufiecaresoluție
(1st,2st,3st,…,kst),seobțineprincompletarecuîncăunnivelasoluțieparțiale
anterioarest=(1st,2st,3st,…,1kst ).

7Etapeînproiectareaalgoritmului:
1)Sealegemoduldereprezentareasoluților.
2)SeidentificăspațiulsoluțiilorposibileșisestabilescmulțimilenSSS …,, ,2 1 și
ordineaîncareacesteavorfiparcurse.
3)Sestabilesccondițiilepecaretrebuiesăleîndeplineascăsoluțiileparțialepentrua
fivalide.
4)Sestabileștecondițiadebazăcaredecidedacăosoluțieparțialăestesoluțiefinală.
5)Lafiecarepasppornimdelaosoluțieparțialăst=(1st,2st,3st,…,1kst ),
determinatăpânăînacelmomentșiîncercămsăextindemaceastăsoluțieadăugândun
nouelementlasfârșitulvectorului.
6)CăutămînmulțimeakS,unnouelement.
7)Dacăexistăunelementneselectatîncă,verificămdacăacestelementîndeplinește
condițiileimpusedeproblemă,numitecondițiidecontinuare.
8)Dacăsuntrespectatecondițiiledecontinuare,adăugămelementulsoluțieiparțiale.
9)Verificămdacăamobținutosoluțiecompletă.
10)Dacăamobținutosoluțiecompletăoafișămșisereiaalgoritmuldelapasul5
11)Dacănuamobținutosoluție,k<––k+1sisereiaalgoritmuldelapasul5.
12)Dacănusuntrespectatecondițiiledecontinuaresereiaalgoritmuldelapasul6.
13)DacănumaiexistăniciunelementneverificatînmulțimeakSînseamnăcănu
maiavemnicioposibilitatedinacestmoment,săconstruimsoluțiafinalăașacă
trebuiesămodificămalegerilefăcuteînprealabil,astfelk<–-k-1șisereiaproblema
delapasul5.
Îngeneral,metodabacktrackingesteineficientăavândcomplexitatea
exponențială.
DacămulțimilenSSS ,…, ,2 1 auacelașinumărpdeelemente,timpulnecesareste
npO ,deciexponențial.Dacănuauacelașinumărdeelemente,notămcu
s=min npppp …,,3 2 1 șicuu=max npppp …,,3 2 1 .Atuncitimpuldeexecuțieesteun
numărcuprinsîntre )(nsO și )(nuO ,decitotexponențial.
Cutoateacestelucrurimenționate,existătreitipurideproblemecareserezolvă
cuajutorulmetodeibacktracking:
1.Problemededecizie-secautăosoluțiefezabilă
2.Problemedeoptimizare-secautăceamaibunăsoluție
3.Problemedeenumerare-secautătoatesoluțiileposibile.
Deciavânduntimpdeexecuțieexponențial,utilizareaacesteimetode,estejustificată
doaratuncicândnucunoaștemoaltămetodăderezolvarecueficiențămaimare.
Revenireaîncazdeinsuccessaupentrugenerareatuturorsoluțiilor
problemeiacondusladenumireadebacktracking,întraducereaproximativăar
firevenireadinurmă.
Utilizareaalgoritmuluirecursivametodeibacktrackingestemultmaiușoarășimai
naturală.Segmentuldestivăpusladispozițieprinfuncțieestegestionatautomatde
sistem.Întotdeaunasevarevenilapasulanteriorprinînchidereaniveluluidestivă.

8BacktrakingAlgoritmrecursiv

} } }1) (k Back elsepar(k) ti1) solutie(k) {if1) (valid(k) ; {) i n; i 1; (i for i; int {k) Back(int
 
ifikstvoid
Subprogramulvalid
1.verificădacăunelementeîndeplineștecondițiadecontinuare
2.Dacăesteverificatăcondiția,aceastăfuncțiereturnează1,și0încazcontrar.
intvalid(intk)
{for(inti=1;i<k;i++)
if(conditie)
return1;
return0;
}
Subprogramulsolutie
1.Verificădacăs-auobținuttoateelementelesoluției.
2.Dacăs-agăsitsoluțiavareturna1,altfel0.
intsolutie(intk)
{if(k==n)
return1:
return0;}
Subprogramultipar
1.Afișeazăelementeledinstivă.
2.Afișareaelementelordinstivăcoincidecuafișareasoluției.
voidtipar()
{for(inti=1;i<=n;i++)
cout<<st[i]<<”“;}

9Permutări.Aranjamente.Combinari
Algoritmînpseudocod
(soluțiicuacelașinumărdecomponente=n)
k=1;
st[k]=0;//inițializarestivă
while(k>0)
if(k==n+1)//configurațiaedetipsoluție
tipar();
k–;
else
if(existăvalorineconsumateînSk)
{seatribuieovaloarepentruxkSk!
if(valid(k))//valoareaaleasăsatisfacecondițiiledecontinuare
{k++;
st[k]=0;
}
}
else
{st[k]=0;
k–;
}
I.1.Generareapermutărilormulțimii
Enunț:Seciteștedelatastaturăunșirdennumerenaturaledistinctedouă
câtedouă.Realizațiunprogramcaresăafișezetoatepermutărileșiruluidat.
Dacăn=3,mulțimile 3,2,13 2 1 SSS
Soluțiilearfi:
{123,132,213,231,312,321}
Dacăs-arrezolvaclasicaceastăproblemă,arînsemnacăartrebuisăgenerăm
toateelementeleprodusuluicartezian: 3,2,13,2,13,2,13 2 1 SSS ,adicăo
mulțimeformatădinelementele:  3,3,3,2,3,3,…2,1,1,1,1,1 .Deoarecefiecare
soluțiefinalăartrebuisăaibătoateelemenetelediferite,dinlistamenționată,doar
șaseîndeplinesccondițiaimpusă.
Seobservă,căelementelemulțimilorsuntînordinestrictcrescătoareși
consecutive.Așadarmoduldealegeredinmulțimenuestealeatoriu,cisefaceîn
funcțiedeordineaelementelor.
st=(st1,st2,st3)S={1,2,3}x{1,2,3}x{1,2,3}
Numărulsoluțiilor:3!=6
Condițiiinterne:st[i]st[k] ki

10Generămcuajutorulstivei,soluțiileprimmetodabacktracking.
1 2 3
1 2 2 2 2
1 1 1 1 1 1
1 2 3
3 3 3 3 1
1 1 1 1 2 2
1 2 3 1
1 1 1 2 3 3
2 2 2 2 2 2
#include<iostream>
usingnamespacestd;
charsp1[]=""; ";
intst[10],n;
voidtipar()
{inti;
cout<<sp1;
for(i=1;i<=n;i++)
cout<<st[i]<<"";
cout<<endl;
;
}
intvalid(intk)
{inti;
for(i=1;i<=k-1;i++)
if(st[k]==st[i])return0;
return1;
}
voidBack(intk)
{inti;
for(i=1;i<=n;i++)
{st[k]=i;
if(valid(k))
if(k==n)tipar();
elseBack(k+1);
}
}
intmain()
{cout<<endl<<sp1<<"Dativaloarealuin:";cin>>n;
cout<<"Permutarileprimelornnumerenaturale"<<endl;

11cout<<endl;
Back(1);
return0;
}
I.2.Generareaaranjamentelor)! (!
pnnAp
n
Secitescnșip.Săsegenerezetoatearanjamenteledenluatecâtep.
Dinanalizaproblemeirezultăurmătoarele:
-stivaareînălțimeap;
-fiecareniveliavaloriîntre1șin;
-elementeleplasatepediverseniveluritrebuiesăfiedistincte.
Algoritmulesteasemănătorcuceldelapermutări,cudeosebireacăaicistiva
areînălțimeap.
Exemplu:
{1,2,3}p=2 6!1!32
3A
{1,2},{1,3},{2,1}{2,3},{3,1},{3,2}
Condițiiinterne:st[i]!=st[k]ki
#include<iostream>
#include<conio.h>
usingnamespacestd;
intst[20],n,k;
voidtipar(intp)
{
intj;
for(j=1;j<=p;j++)
cout<<st[j]<<"";
cout<<endl;
}
intvalid(intp)
{
inti,ok;
ok=1;
for(i=1;i<p;i++)
if(st[p]==st[i])
ok=0;

12returnok;
}
intsolutie(intp)
{
return(p==k);
}
voidback(intp)
{
inti;
for(i=1;i<=n;i++)
{
st[p]=i;
if(valid(p))
if(solutie(p))
tipar(p);
else
back(p+1);
}
}
intmain()
{inti;
cout<<"n=";cin>>n;
cout<<"k=";cin>>k;
for(i=1;i<=n;i++)
st[i]=0;
back(1);
system("pause");
}
I.3.Generareacombinărilor!)! (!
kknnCk
n
{1,2,3}k=2 3!2!1!32
3C
Fiinddatedouănumerenșik,seceresăsegenerezetoatecombinăriledenelemente
luatecâtek.
Rezolvare:
Ceeacenepropunemestesăgenerămcombinăriledenelementeluatecâtek.
Fiecaresoluțievafioconfigurațieastivei(st[1],st[2],…,st[k])alcătuitădink
elementedistinctealemulțimii1,2,3,…,n
Notândcupvârfulstivei,osoluțieparțială(st[1],st[2],…,st[p])devinefinală,când
stivaarekelemente,adicădacăp=k.
Condițiiinterne:st[k]>st[k-1] 1k

13#include<iostream>
usingnamespacestd;
intn,p,st[25];
intvalid(intk);
intsolutie(intk);
voidtipar(intk);
voidback(intk);
charsp1[]="";
intmain()
{cout<<endl<<sp1<<"Dativaloarealuin:";cin>>n;
cout<<endl<<sp1<<"Dativaloarealuip:";cin>>p;
cout<<"Combinariledenluatecatep"<<endl;
cout<<endl;
back(1);
return0;
}
voidback(intk)
{inti;
for(i=st[k-1]+1;i<=n;i++)
{st[k]=i;
if(valid(k))
{if(solutie(k))
tipar(k);
else
back(k+1);
}
}
}
intvalid(intk)
{inti;
for(inti=1;i<k-1;i++)
if(st[i]==st[k])
return0;
return1;
}
intsolutie(intk)
{if(k==p)
return1;
return0;
}
voidtipar(intk)
{inti;
for(inti=1;i<=k;i++)
cout<<st[i]<<"";
cout<<endl;
}

14I.4)PRODUSCARTEZIAN
Fiinddatenmulțimi,nMMM ,…, ,2 1 săseafișezeelementeleprodusuluicartezian
nMMM  …2 1 undei in M ,…,3,2,1 .
ProdusulcartezianalmultimilorM1,M2,M3,…,Mn
Dativaloarealuin:4
CardinalulMultimii1:2
CardinalulMultimii2:3
CardinalulMultimii3:1
CardinalulMultimii4:1
1111
1211
1311
2111
2211
2311
#include<iostream>
usingnamespacestd;
charsp[]=" ";
intst[20],n,v[20];
voidtipar()
{inti,j;
cout<<sp;
for(i=1;i<=n;i++)cout<<st[i]<<"";
cout<<endl;
;
}
voidBack(intk)
{inti;
for(i=1;i<=v[k];i++)
{st[k]=i;
if(k==n)tipar();
elseBack(k+1);
}
}
intmain()
{inti;
cout<<sp<<"ProdusulcartezianalmultimilorM1,M2,M3,…,Mn"<<endl;
cout<<endl<<sp<<"Dativaloarealuin:";cin>>n;
for(i=1;i<=n;i++)
{cout<<"CardinalulMultimii"<<i<<":";cin>>v[i];}
Back(1);
return0;
}

15I.5.Submulțimileuneimulțimi
SăsegenerezetoatesubmulțimilemulțimiiA={1,2,3…,n}.
#include<iostream>
usingnamespacestd;
intn,p,st[25];
intvalid(intk);
intsolutie(intk);
voidtipar(intk);
voidback(intk);
intmain()
{inti;
cout<<"n=";
cin>>n;
cout<<"multimeavida"<<endl;
for(p=1;p<=n-1;p++)
back(1);
cout<<"{";
for(i=1;i<n;i++)
cout<<i<<",";
cout<<n<<"}";
}
voidback(intk)
{inti;
for(i=st[k-1]+1;i<=n;i++)
{st[k]=i;
if(solutie(k))
tipar(k);
else
back(k+1);
}
}
intsolutie(intk)
{if(k==p)
return1;
return0;
}
voidtipar(intk)
{inti;
for(inti=1;i<=k;i++)
cout<<st[i]<<"";
cout<<endl;
}
n=4

16multimeavida
1
2
3
4
12
13
14
23
24
34
123
124
134
234
{1,2,3,4}
I.6)Partițiileunuinumăr
Scriețiunprogramcaresăafișezetoatepartițiileunuinumărnaturaln.
Senumeștepartitieaunuinumărnaturalnenulnomulțimedenumerenaturalenenule
{k1,k2,..,km}știindcăconditiak1+k2+…+km=n.
Pentrun=6avem:
Solutianr.1:111111
Solutianr.2:11112
Solutianr.3:1113
Solutianr.4:1122
Solutianr.5:114
Solutianr.6:123
Solutianr.7:15
Solutianr.8:222
Solutianr.9:24
Solutianr.10:33
Solutianr.11:6
11solutii
#include<iostream>
usingnamespacestd;
intn,ns,sol[20];
voidafis(intl)
{inti;
ns++;
cout<<"Solutianr."<<ns<<":";
for(i=1;i<=l;i++)cout<<sol[i]<<"";
cout<<endl;
}

17voidback(inti,intsp)
{intj;
if(sp==n)afis(i-1);
elsefor(j=1;j<=n-sp;j++)
if(j>=sol[i-1])
{
sol[i]=j;
back(i+1,sp+j);
}
}
intmain()
{
cin>>n;
ns=0;
back(1,0);
cout<<ns<<"solutii";
}
I.7)Problemaparantezelor:
Dându-seunnumărparn,afișațitoatevarianteledenparantezecareseînchidcorect.
Exemplu:
4
(())
()()
Rezolvare:
#include<iostream>
usingnamespacestd;
intst[10],n;
voidscriesol()
{intj;
cout<<endl;
for(j=1;j<=n;j++)
if(st[j]==1)cout<<")";
elsecout<<"(";
}
intcond(intk)
{inti,pi=0,pd=0;
for(i=1;i<=k;i++)
if(st[i]==0)pd++;
elsepi++;
returnpd<=n/2&&pi<=pd;
}

18I.8)Anagrameleunuicuvânt
#include<bits/stdc++.h>
usingnamespacestd;
voidanagrame(strings,intl,intr)
{
if(l==r)
cout<<s<<endl;
else
{
for(inti=l;i<=r;i++)
{
swap(s[l],s[i]);
anagrame(s,l+1,r);
swap(s[l],s[i]);
}
}
}voidback(intk)
{
inti;
for(i=0;i<=1;i++)
{
st[k]=i;
if(cond(k))
if(k==n)scriesol();
elseback(k+1);
}
}
intmain()
{
cin>>n;
back(1);
}

19intmain()
{
stringstr="aer";
intn=str.size();
anagrame(str,0,n-1);
return0;
}
Date.in
Aer
Date.out
aer
are
ear
era
rae
rea
I.9.Descompunereaunuinumărînsumadenumereprime.
ScriețitoatedescompunerilenumăruluiNcasumădenumereprime.
N=7
223
232
25
322
52
7
#include<iostream>
#include<math.h>
usingnamespacestd;
intN,st[10],k;
intdescompunereSuma(intk)
{
intS=0;
for(inti=1;i<=k;i++)
S+=st[i];
returnS;
}
intverificaPrim(intm)
{
if(m<=1)return0;

20for(inti=2;i<=sqrt(m);i++)
if(m%i==0)
return0;
return1;
}
intSolutie(intk)
{
return(descompunereSuma(k)==N);
}
voidTipar(intk)
{
cout<<endl;
for(intj=1;j<=k;j++)
cout<<st[j]<<"";
}
intValid(intk)
{
return((verificaPrim(st[k]))&&(descompunereSuma(k)<=N));
}
voidBack()
{
for(intk=1;k<=N;k++)
st[k]=1;
k=1;
while(k>0)
{
while(st[k]<N)
{
st[k]++;
if(Valid(k))
if(Solutie(k))
Tipar(k);
else
k++;
}
st[k–]=1;
}
}
intmain(void)
{
cout<<"N=";cin>>N;
Back();
}

21Backtrackinggeneralizatsauînplan
Încapitolulanterior,amstudiatmetodabacktracking,șiamobservatcăstiva
stcarememorasoluțiilefinaleeraunvector,adicăuntablouunidimensional.Astfel,
fiecareelementalstiveikst aveaosingurăvaloarelaunmomentdat.
Sepoateîntâmplacaîntr-oproblemăfiecareelementalstiveikst săaibă
maimultecaracteristici?
Răspunsulesteafirmativșicaexemplu,peotablădeșahvremsăobținemtoate
traseelepecarele-arurmauncal,astfelîncâtporninddincolțuldinstângasualtablei,
acestavreasăajungăîncolțuldindreaptajos.Dacăvremsămemorămpestivă,
căsuțeleîncarepoatesăricalul,vomținecontcăfiecarecăsutăaredouăcaracteristici:
liniașicoloana.
Înaceastăsituație,stivastnumaipoatefiuntablouunidimensional,deoarece
fiecareelementkst trebuiesăaibămaimultecaracteristici.
Deaceea,trebuiesădefinimstivacauntabloubidimensional(matrice)sau
tridimensional.
Pentrubacktracking-ulgeneralizatestemaidificildeproiectatunalgoritm
standard,deoarececaracteristicilepecaretrebuiesăleaibăvectorulsoluțiediferăde
laoproblemălaalta.
I.10)Problemacelorndamepeotablădeșah
OproblemăclasicădebacktrackingoreprezintăproblemacelorN-Dame,
propusăpentruprimadatădeșahistulgermanMaxBezzelîn1848,utilizându-sede
psudonimul”Schachfreund”,pentruotablădeșahde8x8,iarîn1869,
Francois-JosephEustacheLionnetpropuneformageneralădenxn.
Pentruaceiacarenusuntfamiliarizațicuregulileșahului,douăreginenu
sepotaflaînaceeașilinie,coloanădiagonalăpentruanuseataca.
Înscrisoareadin1850cătreprietenulsăuHeinrichScumacher,eminentul
matematicianCarlFriedrichGaussasusținutcăademonstratîncâtevaoreșifoarte
ușor,răspunsulluiFranzNauckpentruproblemăcareîncazul8x8,are92soluții.
ScrisoarealuiGaussdescrieurmătoareaformărecursivăastrategieide
rezolvareaproblemeiN-Dame,aceeașipecareadescris-oîn1882,matematicianul
francezEdouardLucasșipecarei-aatribuit-oluiEmmanuelLaquiere.
Plasămdamelepetablă,câteunaperând,începândcuprimulrânddesus.
Pentruaplasaak-damă,vomîncercatoatecelenpătrateînliniakdelastângala
dreaptafolosindu-nedebuclă.Dacăunpătratesteatacatdeoaltădamă,vomignora
acelpătrat,altfelputemplasadamaînelșirecursiv,vomputeaplasafiecaredamăpe
rândpânălaultimalinie.
Figura1,prezintăalgoritmulmenționat,șicareînmodrecursivenumeră
toatesoluțiileproblemeiN-Dame,porninddelaosoluțieparțială.
ConformluimetodeiGauss,noiputemreprezentapozițiiledamelor
utilizândvectorulnQ ,…,2,1 ,undeiQ indicăpătratulicareconțineodamă.Când
PlaseazăDamaesteapelat,parametruldeintrarekesteindexulprimieiliniigoale,iar
prefixul1 ,…,2,1kQ conținepozițiileprimelork-1dameplasatedeja.

22Înparticularpentruacalculatoatesoluțiileproblemeifărărestricții,putem
apelaPlaseazăDama()1,…1(nQ .Ieșireadinbuclaforconsiderătoateposibilitățile
pentruplaseareauneidamepeliniak.Intrareaînbuclafor,verificădacăplasarea
dameiîntr-unpătratpeliniak,nucontrazicepozițiileprimelork-1damedeja
plasat  ) () ( ikjiQsauikjiQsaujiQ    e.
AlgoritmulGAUSSșiLaquierepentruproblemacelorN-Dame
PlaseazăDama),…1(knQ
Ifk=n+1
printnQ ,…,2,1
Altfel
forj←1ton
legal←TRUE
Fori←1tok-1
If
legal←FALSE
Iflegal
iQ←j
PlaseazăDama )1,…1( knQ
ExecuțiaPlaseazăDamapoatefiilustratăîntr-unarborede
recurență.Fiecăruinoddinacestarboreîicorespundeosupbroblemărecursivă,șicare
reprezintăosoluțieparțialălegală,înparticularfiecarerădăcinăîicorespundeotablă
goală,adicăk=0.Vârfuriledinarborelederecurențăcorespundapelurilorrecursive.
Frunzelecorespundsoluțilorparțialecarenupotmergemaideparte,fiedincauzăcă
existădejacâteoreginăînfiecarepătrat,fiecaindiferentdepozițiadameipe
următoarealinie,nuputemîndeplinicondițiadeanuatacaoaltădamă.Căutarea
backtrackingpentrusoluțiilecompleteesteechivalentăcucăutareaDEPTH_FIRSTa
acestuiarbore.
Fiinddatăotablădeșah,dedimensiunen,xn,secertoatesoluțiiledearanjarea
ndame,astfelîncâtsănuseafledouădamepeaceeașilinie,coloanăsaudiagonală
(damesănuseatacereciproc).

23Exemplu:Săpreuspunemcăavemotablăde4x4și4regine.Atunciosoluție
finalăarfi:
Seobservăcăodamătrebuiesăfieplasatăsingurăpelinie.Așezămprimadamăpe
linia1,coloana1.
Adouadamăpoatefiașezatădoarîncoloana3.
Deci,atreiadamănupoatefiplasatăînlinia3.
Înacestcaznuavemsoluții,deoarececeade-a4damănumaipoatefiașezatăpe
tablăconformcerințelorproblemei.
Așacăvomîncercaatunciplasareaceleide-adouadameîncoloana4.Atreiadamă
nupoatefiplasatădecâtîncoloana2.

24
Încercândsăavansămcudamaapatra,observămcănuesteposibilsăo
plasămniciîncoloana3,niciîncoloana4.Dinnou,nuvomaveasoluție.
Avansămcuprimadamăîncoloana2.
Adouadamănupoatefiașezatădecâtîncoloana4.
Damaatreiaseașeazăînprimacoloană.
Acumesteposibilsăplasămapatradamăîncoloana3siastfelamobținuto
soluțieaproblemei.
Algoritmulcontinuăînacestmodpânăcândtrebuiescoasădepetablăprima
damă.
Pentrureprezentareauneisoluțiiputemfolosiunvectorcuncomponente
(avândînvederecăpefiecareliniesegăseșteosingurădamă).
ExemplupentrusoluțiagăsităavemvectorulSTcepoatefiasimilatuneistive.
Douădamesegăsescpeaceeașidiagonalădacăsinumaidacăesteîndeplinită
condiția:|st(i)-st(j)|=|i-j|(diferența,înmodul,întreliniisicoloaneesteaceeași)
ST(4)
ST(3)ÎngeneralST(i)=ksemnificăfaptulcăpeliniaidamaocupăpozițiak.
ST(2)
ST(1)3
1
4
2

25Exemplu:întabla4x4avemsituația:
st(1)=1i=1
st(3)=3j=3
|st(1)-st(3)|=|1–3|=2
|i–j|=|1–3|=2
sausituația
st(1)=3 i=1
st(3)=1 j=3
|st(i)-st(j)|=|3–1|=2
|i–j|=|1–3|=2
Întrucâtdouădamenusepotgăsiînaceeașicoloană,rezultăcăosoluțieeste
subformădepermutare.Oprimăideeneconducelagenerareatuturorpermutărilorsi
laextragereasoluțiilorpentruproblemacadouădamesănufieplasateînaceeași
diagonală.Aprocedaastfel,înseamnăcălucrămconformstrategieibacktracking.
Aceastapresupunecaimediatceamgăsitdouădamecareseatacă,săreluăm
căutarea.
latăalgoritmul,conformstrategieigeneratedebacktracking:
-Înprimapozițieastiveiseîncarcăvaloarea1,cusemnificațiacăînliniaunu
seașeazăprimadamăîncoloană.
-Linia2seîncearcăașezareadameiîncoloana1,acestlucrunefiindposibil
întrucâtavemdouadamepeaceeașicoloană.
-Înlinia2seîncearcăașezareadameiîncoloana2,însăacestlucrunueste
posibil,pentrucădamelesegăsescpeaceiașidiagonală(|st(1)-st(2)|=|1-2|);
-Așezareadamei2încoloana3esteposibilă.
-Nusepoateplasadama3încoloana1,întrucâtînliniile1-3dameleocupa
acelașicoloană.
-Șiaceastăîncercareeșueazăîntrucâtdameledepe2și3suntpeaceeași
diagonală.
-Dameledepe2-3segăsescpeaceeașicoloană.
-Dameledepe2-3segăsescpeaceeașidiagonală.
-Amcoborâtînstivămutânddamadepelinia2șicoloana3încoloana4.
Algoritmulseîncheieatuncicândstivaestevidă.
Conditiiinterne:
njijijstistjinjijijstistnist
,1,, ,][ ][,1,, ],[ ][},…,2,1{][
 
Damelenupotfiplasatepeaceeasicoloana
Damelenupotfiplasatepeaceeasi
diagonala

26
#include<iostream>
#include<math.h>
usingnamespacestd;
intst[10],n,i,k,nrsol=0,j;
voidinit()
{for(i=1;i<=n;i++)
st[i]=0;
}
voidtipar()
{for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
if(st[i]==j)
cout<<"R";
else
cout<<"*";
cout<<endl;
}
}
intvalid(intk)
{for(i=1;i<k;i++)
if(st[i]==st[k]||abs(i-k)==abs(st[i]-st[k]))
return0;
return1;
}

27voidback()
{
k=1;
while(k>0)
if(k==n+1)
{nrsol++;
cout<<"Solutiacunr."<<nrsol<<"este:"<<endl;
tipar();
k–;
}
else
if(st[k]<n)
{st[k]++;
if(valid(k))
k++;
}
else
{st[k]=0;
k–;
}
}
intmain()
{cout<<"n=";cin>>n;
init();
back();
cout<<endl;
cout<<"Nr.sol="<<nrsol<<endl;
}
n=4
Solutiacunr.1este:
*R**
***R
R***
**R*
Solutiacunr.2este:
**R*
R***
***R
*R**

28I.11..Problemacomisuluivoiajor(agentuluidevânzări)
Seconsiderănorașe1,2,3,…,n.Unagentdevânzăritrebuiesăîșiprezinteprodusele
întoatecelenorașe,plecânddintr-unorașdestart,trecândprinfiecareorașdoaro
singurădatășirevenindînorașulîncareaplecat.Știindcăîntreuneledintreorașe
existădrumuridirecte,iarîntrealtelenu,săseafișezetoatetraseelepecarelepoate
urmaagentuldevânzări.
Drumuriledirectedintreorașe,suntmemorateîntr-omatricecunliniișimcoloane,în
carefiecareelementa[i,j]=1dacăexistădrumulîntreceledouăorașe,și0încaz
contrar.
n=5
01001
10110
01011
01100
10100
Plecânddinorașul1,traseeleposibilesunt:(1,2,4,3,5,1)și(1,5,3,4,2,1).
Descriereaalgoritmului:
Notăm-orașelecunumeredela1lan.
-st-vectorulstivă
-sorașuldeplecare
Fiecaresoluțiefinalăvareprezentatraseulcomis-voiajoruluișivaconținetoate
orașele,osingurădată.Decivomavea,defapt,osoluțieformatădinpermutarea
mulțimiin,…,3,2,1 .Opartedinpermutărivorfielimnateautomat,datorită
condițiilordevalidare.
Înfuncțiainit():
-vomcitipen
-vominițializastiva
-vomcompletamatriceaa
-vompunecondițiacatoateelementeledepediagonalaprincipalăsăfie0,adică
000iia
-citimporțiuneadeasupradiagonaleiprincipaleșivomfaceatribuirea
00 00 ijajia ,matriceaafiindunasimetrică,adicădacăexistădrumîntrei0
șij0,vaexistadrumșiîntrej0,i0.
Penivelul0alstiveivomindicaorașuldeplecares.
Verificămvaliditateauneisoluțiiparțialest[1],st[2],…,st[p]șipentruaceasta
vompresupuneîncădelaînceputcăestevalidă,inițializândcu1,ovariabilăbooleană
ok,apoivomcăutacazulcontrar,carearputeafifurnizatdeurmătoarelecondiții:

291.dacăvreunorașsemaigăseștepeunnivelanterior.
2.dacăîntreorașulst[p]șist[p-1]nuexistădrum,înseamnăcădeplasareacomisului
voiajornuareloc.
Osoluțiest[1],st[2],…,st[p]estesoluțiefinalădacăconținenorașeșiîntre
1snsta ,adicăîntreorașulfinalșiceldestartsăexistedrum.
Algoritm:
#include<iostream>
#include<conio.h>
#include<stdio.h>
usingnamespacestd;
inta[25][25];
intst[25],n,s;
voidafis_matrice()
{
inti1,j1;
cout<<"\nMatriceadrumuriloreste:\n";
for(i1=1;i1<=n;i1++)
{
for(j1=1;j1<=n;j1++)
cout<<a[i1][j1]<<"";
cout<<"\n";
}
}
intinit()
{inti0,j0;
cout<<"\nnumaruloraselor=";cin>>n;
cout<<"\norasuldeplecare=";cin>>s;
for(i0=0;i0<25;i0++)
st[i0]=0;
for(i0=1;i0<=n;i0++)
a[i0][i0]=0;
cout<<"\nDatimatriceadrumurilor:\n";
for(i0=1;i0<=n;i0++)
for(j0=1;j0<=n;j0++)
if(i0<j0)
{
cout<<"a["<<i0<<"]["<<j0<<"]=";
cin>>a[i0][j0];
a[j0][i0]=a[i0][j0];
}
afis_matrice();
st[0]=s;
}
voidtipar(intp)
{
intj;
for(j=1;j<=p;j++)
cout<<st[j]<<"";

30cout<<"\n";
}
intvalid(intp)
{inti,ok,i1,j1;
ok=1;
for(i=0;i<=p-1;i++)
if(st[p]==st[i])
ok=0;
if(a[st[p]][st[p-1]]==0)
ok=0;
returnok;
}
voidback(intp)
{intpval;
for(pval=1;pval<=n;pval++)
{st[p]=pval;
if(valid(p))
if(p==n&&a[st[p]][st[s]]==1)
{
cout<<"solutie=";
tipar(p);
}
elseback(p+1);
}
}
intmain()
{init();
back(1);
getch();}
I.12)Pătratemagice
Unpătratdelaturanestenumitmagicdacăesteformatdinnumereledela1la
n*nșisumapefiecarelinie,pefiecarecoloană,precumșipecele2diagonaleeste
constantă.Înplussecerecapeoricelinieșipeoricecoloană,sănuexistevaloriegale.
Exemplu:
Date.in
N=4
S=34
Date.out
121516
121435
137104
81169

31Algoritm:
#include<fstream>
#include<cstring>
usingnamespacestd;
ifstreamf("date.in");
ofstreamg("date.out");
intn,p[100],a[10][10],s,gata;
voidafis()
{
inti,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
g<<a[i][j]<<"";
g<<endl;
}
g<<endl;
gata=1;
}
intsumap(inti,intj)
{
ints=0,k;
for(k=1;k<=j;k++)s=s+a[i][k];
returns;
}
intsumal(inti)
{
ints=0,j;
for(j=1;j<=n;j++)s=s+a[i][j];
returns;
}
intsumac(intj)
{
ints=0,i;
for(i=1;i<=n;i++)s=s+a[i][j];
returns;
}
intsumad2()
{
ints=0,i;
for(i=1;i<=n;i++)s=s+a[i][n+1-i];
returns;
}
intsumad1()

32{
ints=0,i;
for(i=1;i<=n;i++)s=s+a[i][i];
returns;
}
intbun(inti,intj)
{
if(sumap(i,j)>s)return0;
if(j==n)if(sumal(i)!=s)return0;
if(i==n)if(sumac(j)!=s)return0;
if(i==n&&j==1)if(sumad2()!=s)return0;
if(i==n&&j==n)if(sumad1()!=s)return0;
return1;
}
voidback(inti,intj)
{
if(!gata)
for(intv=1;v<=n*n;v++)
if(!p[v])
{
a[i][j]=v;
p[v]=1;
if(bun(i,j))if(i==n&&j==n)afis();
elseif(j<n)back(i,j+1);
elseback(i+1,1);
p[v]=0;
}
}
intmain()
{
f>>n;
s=n*(n*n+1)/2;
gata=0;
back(1,1);
return0;
}
I.13)Problemalabirintului:
Unlabirintsecodificăprintr-omatricenxn.Elementeleacesteimatricesunt
numerotatecu0dacăestedrumblocat,1dacăpoatemergemaideparte.
Afișatidrumulprincareșoricelulpoatepărăsilabirintul.

33#include<stdio.h>
#defineN4
boolsolutie(
intlabirint[N][N],intx,
inty,intv[N][N]);
voidafiseaza(intv[N][N])
{
for(inti=0;i<N;i++){
for(intj=0;j<N;j++)
printf("%d",v[i][j]);
printf("\n");
}
}
boolsigur(intlabirint[N][N],intx,inty)
{
if(
x>=0&&x<N&&y>=0
&&y<N&&labirint[x][y]==1)
returntrue;
returnfalse;
}
boolsolutielabirint(intlabirint[N][N])
{
intv[N][N]={{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0}};
if(solutie(
labirint,0,0,v)
==false){
printf("Nuarescapare");
returnfalse;
}
afiseaza(v);
returntrue;
}
boolsolutie(
intlabirint[N][N],intx,
inty,intv[N][N])

34{
if(
x==N-1&&y==N-1
&&labirint[x][y]==1){
v[x][y]=1;
returntrue;
}
if(sigur(labirint,x,y)==true){
v[x][y]=1;
if(solutie(
labirint,x+1,y,v)
==true)
returntrue;
if(solutie(
labirint,x,y+1,v)
==true)
returntrue;
v[x][y]=0;
returnfalse;
}
returnfalse;
}
intmain()
{
intlabirint[N][N]={{1,0,0,0},
{1,1,0,1},
{0,1,0,0},
{1,1,1,1}};
solutielabirint(labirint);
return0;
}
Cifra1aratădrumulșoriceluluiînlabirint
1000
1100
0100
0111

35I.14)Sărituracalului
Fiinddatăotablădeșahdedimensiuneanxnșiuncalîncolțulstângasusal
acesteia,seceresăseafișezetoateposibilitățiledemutareaacesteipiesedeșahastfel
încâtsătreacăosingurădatăprinfiecarepătrataltablei.Osoluțievafiafișatăcao
matricenxnîncaresuntnumerotatesăriturilecalului.
Pentrurezolvareaacesteiproblemevomcodificadirecțiilededeplasarepentrucăarfi
ineficientsăscriemdouăciclurifordela–2la2cucele25devariantededeplasare
dincarevalidesuntdoaropt.Deasemeneaaicispredeosebiredecelelalteprobleme
tratatelaaplicareametodeibacktrackingînplannuvomfolosiunvectorsoluție,ci
vomscriesăriturileîntablouurmărindcalareveniresărefacempozițiileocupate
pentruanuseluablocaje.Înfigurademaijossuntprezentatecele8mutăriposibile
pentruuncal.
#include<fstream>
#include<iostream>
usingnamespacestd;
constintdx[8]={-1,1,2,2,1,-1,-2,-2};
constintdy[8]={-2,-2,-1,1,2,2,1,-1};
inta[10][10],n;
ofstreamf("cal.out");
voidafis()
{inti,j;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)f<<a[i][j]<<"";
f<<endl;
}
f<<endl;
}
intinside(inti,intj)

36{
returni>=1&&i<=n&&j>=1&&j<=n;
}
voidback(inti,intj,intpas)
{intk,inou,jnou;
a[i][j]=pas;
if(pas==n*n)afis();
elsefor(k=0;k<8;k++)
{inou=i+dx[k];
jnou=j+dy[k];
if(inside(inou,jnou)&&a[inou][jnou]==0)
back(inou,jnou,pas+1);
}
a[i][j]=0;
}intmain()
{cin>>n;
back(1,1,1);
}
Cal.outPrimeledouăsoluțiisunt:
12023341736
222716192433
7221263518
28156113225

37I.15)Sudoku
include<bits/stdc++.h>
usingnamespacestd;
#defineliber0
#defineN9
boolgasestelocliber(intmatrice[N][N],
int&lin,int&col);
boolisSafe(intmatrice[N][N],intlin,
intcol,intnum);
boolSolveSudoku(intmatrice[N][N])
{
intlin,col;
if(!gasestelocliber(matrice,lin,col))
returntrue;
for(intnum=1;num<=9;num++){
if(isSafe(matrice,lin,col,num)){
matrice[lin][col]=num;381330510
1429491231
12023341736
223316192427
7221263518
32156112825
381330510
1431491229

38if(SolveSudoku(matrice))
returntrue;
matrice[lin][col]=liber;
}
}
returnfalse;
}
boolgasestelocliber(intmatrice[N][N],
int&lin,int&col)
{
for(lin=0;lin<N;lin++)
for(col=0;col<N;col++)
if(matrice[lin][col]==liber)
returntrue;
returnfalse;
}
boolutilizatInlin(intmatrice[N][N],intlin,intnum)
{
for(intcol=0;col<N;col++)
if(matrice[lin][col]==num)
returntrue;
returnfalse;
}
boolutilizatInCol(intmatrice[N][N],intcol,intnum)
{
for(intlin=0;lin<N;lin++)
if(matrice[lin][col]==num)
returntrue;
returnfalse;
}
boolutilizatInpatratel(intmatrice[N][N],intpatratelStartlin,
intpatratelStartCol,intnum)
{
for(intlin=0;lin<3;lin++)
for(intcol=0;col<3;col++)
if(matrice[lin+patratelStartlin]
[col+patratelStartCol]
==num)
returntrue;
returnfalse;
}
boolisSafe(intmatrice[N][N],intlin,

39intcol,intnum)
{
return!utilizatInlin(matrice,lin,num)
&&!utilizatInCol(matrice,col,num)
&&!utilizatInpatratel(matrice,lin-lin%3,
col-col%3,num)
&&matrice[lin][col]==liber;
}
voidprintmatrice(intmatrice[N][N])
{
for(intlin=0;lin<N;lin++){
for(intcol=0;col<N;col++)
cout<<matrice[lin][col]<<"";
cout<<endl;
}
}
intmain()
{
intmatrice[N][N]={{0,0,0,9,1,0,4,0,7},
{3,0,4,6,8,0,0,1,0},
{0,7,9,0,5,0,6,0,3},
{9,0,2,0,0,0,8,0,1},
{0,1,5,0,0,6,3,4,0},
{0,3,0,0,9,0,0,5,0},
{2,0,0,5,3,0,7,0,0},
{0,0,3,1,0,0,0,9,0},
{6,0,0,4,7,0,1,3,0}};
if(SolveSudoku(matrice)==true)
printmatrice(matrice);
else
cout<<"NuexistasolutiepentruacestjocSudoku";
return0;
}
586913427
324687915
179254683
962345871
815726349
437891256
291538764
743162598
658479132

40CapitolulalII-lea:MetodaGreedy
AlgoritmiidetipGreedyseaplicaunorproblemedeoptimizareacăror
solutiepoatefiexprimatăsubformaunuivectordenumereîntregi(cuvaloriîntre1si
n).Într-oproblemădeoptimizaretrebuiegăsităsoluțiaoptimădintretoatesoluțiile
posibile.
MetodaGreedysepoateaplicaunorproblemedeoptimizare,caalternativă
maieficientălaocăutareexhaustivă(detip'backtracking').Spredeosebiredemetoda
Backtraking,metodaGreedynudispunedemecanismuluideîntoarcereșioferădoar
osoluție.
DescriereametodeiGreedy:
Pentrufiecareelementcareurmeazăsăfieadăugatsoluțieifinale,se
efectueazăoalegereasadinelementelemulțimiiA(dupăunmecanismspecific
fiecăreiproblemeînparte),iardacăesteposibil,acestaesteadăugat.Algoritmulse
terminăfiecândafostgăsităsoluțiacerută,fiecânds-aconstatatinexistențaacesteia.
Intuitiv,alegemunelement,aldoilea,….pânăcândobținemcedorimsaupânăcândau
fosttestatetoateelementelemulțimii.Deaiciprovinesinumelemetodei
(greedy=lacom).
TehnicaGreedyconducelatimpdecalculpolinomial.
II.1)Problemabanilor
PentruproblemaurmătoarevomfolosiunalgoritmGreedypentruagăsi
numărulminimdemonedesaubancnotepentruaputeaplătiosumădată.Trebuiesă
menționatcăsevorfolosimonedesaubancnotecareauvaloareaegalăcuunuldin
elementelemulțimii:{1,2,5,10,20,50,100,200,500,2000}șivatrebuisă
returnezenumărulmonedelorsaubancnotelorfolositepentruaplătisuma.
ÎnrezolvareaacesteiproblemecuajutorulmetodeiGreedy,vomcăuta
valoareamaximăauneibancnote/monedemaimicădecâtsumacaretrebuieplătităși
apoivomrealizadiferențadintresumășivaloareabancnoteișivomrepetaprocedeul
pânăcândsumaeste0.
#include<bits/stdc++.h>
usingnamespacestd;
intbancnote[]={1,2,5,10,20,50,100,200,500,2000};
intn=sizeof(bancnote)/sizeof(bancnote[0]);
voidschimb(intsum)
{
vector<int>monede;
for(inti=n-1;i>=0;i–){
while(sum>=bancnote[i]){
sum-=bancnote[i];

41monede.push_back(bancnote[i]);
}
}
for(inti=0;i<monede.size();i++)
cout<<monede[i]<<"\t";
}
intmain()
{
intn=7000;
cout<<"Minimuldebancnotepentruaplatisuma"<<n<<"este\t";
schimb(n);
return0;
}
II.2:Problema:Fracțiaegipteană
Oricefracțienm,cunm, ,poatefireprezentatăcasumădefracțiicareau
numărătorulegal1.OastfeldefracțieestecunoscutăsubnumeledeFracție
egipteană.
Exemplu:21
101
53
GenerămofracțieegipteanăfolosindalgoritmulGreedy.
#include<iostream>
usingnamespacestd;
voidegiptr(intm,intn)
{
if(n==0||m==0)
return;
if(n%m==0)
{

42cout<<"1/"<<n/m;
return;
}
if(n%m==0)
{
cout<<m/n;
return;
}
if(m>n)
{
cout<<m/n<<"+";
egiptr(m%n,n);
return;
}
intk=n/m+1;
cout<<"1/"<<k<<"+";
egiptr(m*k-n,n*k);
}
intmain()
{
intm=3,n=5;
cout<<"Fracția"
<<m<<"/"<<n<<"sescriecasumăastfel\n";
egiptr(m,n);
return0;
}

43II.3)ProblemaColorăriihărților
Sedăohartăcunțări.Găsițiosoluțiedecolorareahărții,utilizândcelmultpatru
culori,dacăoricaredouățărivecinesuntcoloratediferit.
Exemplu:
Dateintrare:Perechiledețărivecinedinharta1:
(0,1);
(0,2);
(1,2);
(1,3);
(2,3);
(3,4);
Perechiledețărivecinedinharta2:
(0,1);
(0,2);
(1,2);
(1,4);
(2,4);
(4,3);
Dateieșire:Coloreazăharta1
tara0areculoarea0
tara1areculoarea1
tara2areculoarea2
tara3areculoarea0
tara4areculoarea1
Coloreazăharta2
tara0areculoarea0
tara1areculoarea1
tara2areculoarea2
tara3areculoarea0
tara4areculoarea3
#include<iostream>
#include<list>
usingnamespacestd;
classGraf
{
intV;
list<int>*adiacenta;
public:
Graf(intV){this->V=V;adiacenta=newlist<int>[V];}
~Graf() {delete[]adiacenta;}

44voidadaugamuchie(intv,intw);
voidgreedyColor();
};
voidGraf::adaugamuchie(intv,intw)
{
adiacenta[v].push_back(w);
adiacenta[w].push_back(v);
}
voidGraf::greedyColor()
{
intculoare[V];
culoare[0]=0;
for(intu=1;u<V;u++)
culoare[u]=-1;
boolvalabil[V];
for(intcr=0;cr<V;cr++)
valabil[cr]=false;
for(intu=1;u<V;u++)
{
list<int>::iteratori;
for(i=adiacenta[u].begin();i!=adiacenta[u].end();++i)
if(culoare[*i]!=-1)
valabil[culoare[*i]]=true;
intcr;
for(cr=0;cr<V;cr++)
if(valabil[cr]==false)
break;
culoare[u]=cr;
for(i=adiacenta[u].begin();i!=adiacenta[u].end();++i)
if(culoare[*i]!=-1)

45valabil[culoare[*i]]=false;
}
for(intu=0;u<V;u++)
cout<<"tara"<<u<<"areculoarea"
<<culoare[u]<<endl;
}
intmain()
{
Grafg1(5);
g1.adaugamuchie(0,1);
g1.adaugamuchie(0,2);
g1.adaugamuchie(1,2);
g1.adaugamuchie(1,3);
g1.adaugamuchie(2,3);
g1.adaugamuchie(3,4);
cout<<"Coloreazaharta1\n";
g1.greedyColor();
Grafg2(5);
g2.adaugamuchie(0,1);
g2.adaugamuchie(0,2);
g2.adaugamuchie(1,2);
g2.adaugamuchie(1,4);
g2.adaugamuchie(2,4);
g2.adaugamuchie(4,3);
cout<<"\nColoreazaharta2\n";
g2.greedyColor();
return0;
}
II.4)Problema:Programareaspectacolelor
Într-ozisuntprogramatenspectacoledemuzică,iarpentrufiecaresecunoaște
momentuldeînceputșimomentuldesfârșit,exprimateprinnumerenaturale.Unelev
doreștesăurmăreascăcâtmaimultespectacoleînîntregime.
Determinaținumărulmaximdespectacolecarepotfiurmărite,fărăcaacesteasăse
suprapună.
Exemplu:
Dateintrare:
V={{1,4},{2,3},{3,6},{6,7},{5,7},{6,9}};

46Dateieșire:
Alegespectacolele:(2,3);(3,6);(6,7);
#include<bits/stdc++.h>
usingnamespacestd;
structspectacol
{
intinceput,sfarsit;
};
boolcompara(spectacols1,spectacols2)
{
return(s1.sfarsit<s2.sfarsit);
}
voidarataspecatolele(spectacolv[],intn)
{
sort(v,v+n,compara);
cout<<"Alegespectacolele:";
inti=0;
cout<<"("<<v[i].inceput<<","<<v[i].sfarsit<<");";
for(intj=1;j<n;j++)
{
if(v[j].inceput>=v[i].sfarsit)
{
cout<<"("<<v[j].inceput<<","
<<v[j].sfarsit<<");";
i=j;
}
}
}
intmain()
{
spectacolv[]={{1,4},{2,3},{3,6},{6,7},
{5,7},{6,9}};
intn=sizeof(v)/sizeof(v[0]);
arataspecatolele(v,n);
return0;}

47II.5)ProblemaComisvoiajorul
Unagentdevânzăritrebuiesăvizitezeunnumărndeorașeșisăseîntoarcăînorașul
deplecareastfelîncâtsănutreacădedouăoriprinacelașiloc.Determinațiuntrasu
delungimeminimăpecareîlpoaterealizaagentul,știindcăelcunoaștedrumurile
dintreorașeșidistanțeleacestora.
#include<fstream>
usingnamespacestd;
ifstreamfin("date.in");
ofstreamfout("date.out");
intx[100],pus[100],n,s;
inta[100][100];
voidcitire()
{
inti,j;
fin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
fin>>a[i][j];
}
voidscriere()
{for(inti=1;i<=n;i++)fout<<x[i]<<"";
fout<<endl<<s;
}
voidvoiajor(intk)
{ intmin=100000,imin;
for(inti=1;i<=n;i++)
if(!pus[i]&&a[x[k-1]][i]<min&&i!=x[k-1])
{
min=a[x[k-1]][i];
imin=i;
}
x[k]=imin;
pus[imin]=1;
s=s+a[x[k-1]][imin];
if(k==n)scriere();
elsevoiajor(k+1);
}
intmain()
{
citire();
x[1]=1;

48pus[1]=1;
voiajor(2);
fin.close();
fout.close();
return0;
}
II.6)ProblemaRucsacului(fracționară)
SeconsiderăcădispunemdeunrucsaccucapacitateaWsidenobiecte,
definitefiecarepringreutatesivaloare,cetrebuieintroduceinrucsac.Secereo
modalitatedeaumplerucsaculcuobiecte,astfelîncâtvaloareatotalăsăfiemaximă.
Esteposibilcaoricâteobiectesibucătidinobiectesăfieintroduse.
Dateintrare:fiecareobiectestedefinitprin(valoare,greutate)
arr[]={{60,10},{100,20},{120,30}}
Volumulrucsacul,V=50;
Dateieșire
Valoareamaximăesteegalăcu240careseobțineprinpunereaa10și20kgși2/3
fraction
din30kg.Decicostultotalvafi:60+100+(2/3)(120)=240
Înproblemafracționarăarucsaculputemîmpărțiunobiectpentruamaximiza
valoareatotalăarucsacului.
Orezolvarebrutăs-arobțineprintestareatuturorsubmulțimilorcudiferitefracții,dar
aceastăabordarearduramult.
OsoluțieeficientăesteaplicareaalgoritmulGreedy.Ideeadebazăestesăcalculăm
raportuldintrevaloareșigreutatepentrufiecareobiectșisălesortăm.
#include<bits/stdc++.h>
usingnamespacestd;
structobiect
{intvaloare,greutate;
obiect(intvaloare,intgreutate):valoare(valoare),greutate(greutate)
{}
};
boolcmp(structobiecta,structobiectb)
{doubler1=(double)a.valoare/a.greutate;
doubler2=(double)b.valoare/b.greutate;
returnr1>r2;
}
doublerucsacfractionar(intW,structobiectv[],intn)
{sort(v,v+n,cmp);
intcurgreutate=0;
doublefinalvaloare=0.0;
for(inti=0;i<n;i++)

49{
if(curgreutate+v[i].greutate<=W)
{
curgreutate+=v[i].greutate;
finalvaloare+=v[i].valoare;
}
else
{
intremain=W-curgreutate;
finalvaloare+=v[i].valoare*((double)remain/v[i].greutate);
break;
}
}
returnfinalvaloare;
}
intmain()
{
intW=50;
obiectv[]={{60,10},{100,20},{120,30}};
intn=sizeof(v)/sizeof(v[0]);
cout<<"Valoareamaximaobtinuta"
<<rucsacfractionar(W,v,n);
return0;
}
II.7)ProblemaHoțiișipolițiștii
Sedăunvectordelungimencareîndeplineșteurmătoarelecerințe:
1.Fiecareelementdinvectorconținefieunpolițist,fieunhoț
2.Fiecarepolițistpoatecapturaunsingurhoț
3.Unpolițistnupoatecapturaunhoțcareestesituatlakpozițiideel.
Trebuiesăgăsimnumărulmaximdehoțicapturați.
Exemplul1.
Dateintrare:v[]={'P','H','H','P','H'},
k=1.
Dateieșire:2.
Exemplul2.
Dateintrare:v[]={'H','H','P','P','H','P'},

50k=2.
Dateieșire:3.
Dateintrare:v[]={'P','H','P','H','H','P'},
k=3.
Dateieșire:3.
Numărulmaximdehoțicarepotfiprinșiesteegalcu2.Primulpolițistîl
prindepeprimulhoț,aldoileapolițistpoateprindealdoileasaualtreileahoț.
OsoluțieeficientăesteutilizareaalgoritmuluiGreedy.Uneledinproprietățile
algoritmuluiGreedypotfiînșelătoare.
Dacăîncercămsăutilizăm:Fiecarepolițistdinstângapoateprindecelmai
apropiathoț.Algoritmulfuncționeazăpentruexemplul3,darpentruexemplul2
eșuează.
Deasemenea,amputeaspune:Fiecarepolițistdinstângapoateprindecelmai
îndepărtathoț.Algoritmulfuncționeazăpentruexemplul2,dareșueazăpentru
exemplul3.
1.Notămcelmaimicindicepentrupolițișticup,iaralhoțilorcuh.
Realizeazăatribuirea.Dacăkhp ,atuncigăseștenoulpșih.
2.Altfelincrementeazămin(p,h)pentruurmătorulpșihgăsit.
3.Repetătoțipașiipânăcândurmătorulpsauhestegăsit.
4.Returneazănumăruldeatribuirifăcute.
#include<iostream>
#include<vector>
#include<cmath>
usingnamespacestd;
intpolhot(charv[],intn,intk)
{
intres=0;
vector<int>hot;
vector<int>pol;
for(inti=0;i<n;i++){
if(v[i]=='P')
pol.push_back(i);
elseif(v[i]=='H')
hot.push_back(i);
}
intl=0,r=0;

51while(l<hot.size()&&r<pol.size()){
if(abs(hot[l]-pol[r])<=k){
res++;
l++;
r++;
}
elseif(hot[l]<pol[r])
l++;
else
r++;
}
returnres;
}
intmain()
{intk,n;
charv1[]={'P','H','H','P','H'};
k=2;
n=sizeof(v1)/sizeof(v1[0]);
cout<<"Numărulmaximdehoticapturati:"
<<polhot(v1,n,k)<<endl;
charv2[]={'H','H','P','P','H','P'};
k=2;
n=sizeof(v2)/sizeof(v2[0]);
cout<<"Nrmaximdehotiprinsi:"
<<polhot(v2,n,k)<<endl;
charv3[]={'P','H','P','H','H','P'};
k=3;
n=sizeof(v3)/sizeof(v3[0]);
cout<<"Nrmaximdehotiprinsi"
<<polhot(v3,n,k)<<endl;
return0;
}
II.8)ProblemaRafturilor
Avândînvederelungimeapereteluiwșirafturilededouălungimimșin,
găsiținumărulfiecăruitipperaftcaretrebuieutilizatșispațiulgolrămasînsoluția
optimă,astfelîncâtspațiulgolsăfieminim.Ceamaimaredintreceledouărafturieste
preferatădeoarececostulesteminim.Cutoateacestea,costulestesecundarșiprima
prioritateesteminimizareaspațiuluigolpeperete.
Exemple:
Dateintrare:w=40m=3n=6
Dateieșire:351
1 39 4039 6533


52Dateintrare:w=29m=2n=3
Dateieșire:470
0 29 2929 7342

#include<bits/stdc++.h>
usingnamespacestd;
voidoptimizare(intperete,intm,intn)
{
intnrm=0,nrn=0,nrperete=perete;
intp=0,q=0,spatiu;
while(perete>=n){
p=perete/m;
spatiu=perete%m;
if(spatiu<=nrperete){
nrm=p;
nrn=q;
nrperete=spatiu;
}
q+=1;
perete=perete-n;
}
cout<<nrm<<""<<nrn<<""
<<nrperete<<endl;
}
intmain()
{
intperete=40,m=3,n=6;
optimizare(perete,m,n);
perete=29,m=2,n=3;
optimizare(perete,m,n);
return0;}
II.9)ProblemaSumaariilorunordreptunghiuri
Pentruunvectorvdelungimen,determinațisumatuturorariilormaximeaunor
dreptunghiuricaresepotformadinelementelorvectorului.Deasemenea,valoarea
unuielementdinvectorpoatescădeamaximcuvaloarea1.
Exemple:
Dateintrare:v={7,6,7,8,1,2,1,2}
Dateieșire:44
Explicație:Decisumaariilordreptunghiurilorcreateesteegalăcu: 44 2167
Pas1:Ordonămdescrescătorelementelevectorului

53Pas2:Primeledouăelementevorreprezentalungimileprimuluidreptunghi.Acest
estevalabildoardacăacestedimensiuniegalesauprimulelementestemaimarecu1
decâtceldealdoilea.
Pas3:Procedămlafelșipentrulățimiledreptunghiului.Ovariabilăvaverificadacă
pentruundreptunghiexistăceledouădimensiuni:lungimeașilățimea.
#include<bits/stdc++.h>
usingnamespacestd;
intariemaxim(intv[],intn)
{
sort(v,v+n,greater<int>());
intsuma=0;
boolt=false;
intn1;
for(inti=0;i<n;i++)
{
if((v[i]==v[i+1]||v[i]-
v[i+1]==1)&&(!t))
{
t=true;
n1=v[i+1];
i++;
}
elseif((v[i]==v[i+1]||
v[i]-v[i+1]==1)&&(t))
{
suma=suma+v[i+1]*n1;
t=false;
i++;
}
}
returnsuma;
}
intmain()
{
intv[]={7,6,7,8,1,2,1,3};

54intn=sizeof(v)/sizeof(v[0]);
cout<<ariemaxim(v,n);
return0;
}
II.10)ProblemaRezervărilorîncadrulunuihotel
UnmanagerdehotelvreasăobținăînavansNrezervăripecamerepentruurmătorul
sezon.HotelulsăuareKcamere.Rezervărileconținatâtdateledesosire,câtșidatele
deieșire.Elvreasăafledacăaresufiecientecameredisponibileînhotelpentrua
satisfacecererea.
Exemplu:
DateintrareSosiri:[135]
Iesiri:[268]
K:1
Dateieșire:False
Managerularenevoiecamăcardouăcameredinintervalulaldoileașialtreilea
săsesuprapună.
Ideeaestesăsalvămdateleintrărilorșialeieșirilorîntr-unvectorauxiliarcuun
aditionalmarkerpentruaindicadacăestetimpulpentruintraresauiesire.Acum
sortămvectorul.Observămvectorulsortat,șipentrufiecaresosirecreștemcu1
numărulrezervăriloractive,șipentrufiecareieșirescădemcu1.Mereutrebuie
analizatlanumărulmaximderezervăriactive.Dacănumărulmaximderezervări
activeestemaimaredecâtk,returnămfals,altfeladevărat.
#include<bits/stdc++.h>
usingnamespacestd;
boolrezervariposibile(intsosire[],
intplecare[],intn,intk)
{
vector<pair<int,int>>ans;
for(inti=0;i<n;i++){
ans.push_back(make_pair(sosire[i],1));
ans.push_back(make_pair(plecare[i],0));
}
sort(ans.begin(),ans.end());
intcurr_active=0,max_active=0;
for(inti=0;i<ans.size();i++){

55if(ans[i].second==1){
curr_active++;
max_active=max(max_active,
curr_active);
}
else
curr_active–;
}
return(k>=max_active);
}
intmain()
{
intsosire[]={1,3,7};
intplecare[]={2,6,8};
intn=sizeof(sosire)/sizeof(plecare[0]);
cout<<(rezervariposibile(sosire,plecare,n,1)?
"Yes\n"
:"No\n");
return0;
}
II.11)ProblemaOrdinealexicografică
Dându-seunvectorv,găsițivectorulcuvalorilecelemaimicidinpunctdevedere
lexicograf,carepoatefiobținutprinschimbuladouăelementevecine,prink
operațiideschimb.
Examples:
Dateintrare:arr[]={5,4,2,1,9}
k=3
Pas1:54129
Pas2:51429
Pas3:15429
Decidupăceletrei,interschimbări,vomobținevectorul:
15429
Dateintrare:arr[]={5,4,2,1,9}
k=5
Dateieșire:arr[]={1,2,5,4,9}
OabordareeficientăarfiaplicareaunuialgorimGreedy.
Primadată,alegemceamaimicăvaloaredinvector.Plasă,acestavaloarepeprima
pozițiedupăceammutatcelalaltevaloricucâteopoziție.Scădemnumărulde

56operațiideinterschimbare(k-1).Dacăk>0aplicămaceeașiprocedurăpentru
următoareleelementepânăk=0.
#include<bits/stdc++.h>
usingnamespacestd;
voidnrmininterschimbari(intv[],intn,intk)
{
for(inti=0;i<n-1&&k>0;++i)
{
intpos=i;
for(intj=i+1;j<n;++j)
{
if(j-i>k)
break;
if(v[j]<v[pos])
pos=j;
}
for(intj=pos;j>i;–j)
swap(v[j],v[j-1]);
k-=pos-i;
}
}
intmain()
{
intv[]={7,6,9,2,1};
intn=sizeof(v)/sizeof(v[0]);
intk=3;
nrmininterschimbari(v,n,k);
for(inti=0;i<n;++i)
cout<<v[i]<<"";
}

57II.12)ProblemaSarciniledelucru
Sedăunvectordesarcinidelucru,încarefiecaresarcinădelucruareuntermen
limitățiunprofitasociatdacăsarcinaesteterminatăînaintedetermen.
Deasemenea,seconsiderăcăfiecaresarcinadelucruareosingurăunitatedetimp,
decitermenulminimminimposibilpentruoricejobeste1.Cumsepoatemaximiza
profitultotaldacăpoatefiprogramatăcâteolucrarelaunmomentdat.
Exemple:
Dateintrare:următoarelepatrusarcinidelucru
SarcinaIdTermenlimităProfit
a 5 25
b 2 12
c 3 55
d 1 30
Dateieșire:Profitulestemaximdacăsuntrezolvatesarcinilecareauid-ul
b,c,a
#include<iostream>
#include<algorithm>
usingnamespacestd;
structsarcina
{
charid;
inttermen;
intprofit;
};
boolcomparare(sarcinaa,sarcinab)
{
return(a.profit>b.profit);
}
voidafisareorarsarcina(sarcinav[],intn)
{
sort(v,v+n,comparare);
intrezultat[n];
boolslot[n];
for(inti=0;i<n;i++)
slot[i]=false;

58CapitolulalIII-lea:DIVIDEETIMPERA
Cumînmatematicăexistămaimultemodalitățispecificedearezolvao
problemă,șiîninformaticăpentrumulteproblemegăsimrețetecareauroluldea
dirijaînalegereaceluimaibunalgoritmșiauneimetodedeaconstruiunalgoritm
eficient.
Expresia“Divideetimpera“provinedinlimbalatinășiîntraducere
înseamnă“dezbinășicucerește”.Principiulacestemetodeconstăînfaptulcăo
problemăpoatefirezolvată,dacăpoatefiîmpărțităînmaimulteproblemesimilarede
dimensiunimaimici.
Înprogramareprincipiulsepoatefaceastfel:sedescompuneproblemaîn
douăsaumaimulteproblemedeacelașitip.for(inti=0;i<n;i++)
{
for(intj=min(n,v[i].termen)-1;j>=0;j–)
{
if(slot[j]==false)
{
rezultat[j]=i;
slot[j]=true;
break;
}
}
}
for(inti=0;i<n;i++)
if(slot[i])
cout<<v[rezultat[i]].id<<"";
}
intmain()
{
sarcinav[]={{'a',5,25},{'b',2,12},{'c',3,55},
{'d',1,30}};
intn=sizeof(v)/sizeof(v[0]);
cout<<"Secventasarcinilordelucrupentruaobtineprofitmaximeste";
afisareorarsarcina(v,n);
return0;
}

59Acesteproblemepotfi:
1.elementare
2.neelementare.
Celeelementareserezolvădirect,iarceleneelementaresevorîmpărțiînaltedouă
tipurideproblemeelementareșineelementare,pânăcândseobțindoarprobleme
elementare.Menționămcăoperațiadedescompuneretrebuiesăgenereze
subproblemeindependente(acesteaprelucreazămulțimidisjunctealedatelorde
intrare).
Prinreconstituireașirecombinareasoluțiilorsubproblemelor,înordine
inversă,obținemsoluțiileproblemeiinițiale.AlgoritmulDivideetImperaeste
implementatrecursiv.
Numărulproblemelorcareserezolvăcuaceastămetodăestedestuldemic,
deoarecenuoriceproblemăpoatefidescompusărepetat.
DescriereametodeiDivideetImperaeste:
1.Împarte(divide)-împarteproblemaînproblememaimici
2.Cucerește(Conquer)-rezolvăsubproblemelerecursiv
3.Combină(combine)-combinărezultatele
Existăsituațiicândfazadecombinarearezultatelorlipsește.
Acestlucruseîntâmplăatuncicândsoluțiaproblemeiinițialeestesoluțiaunei
subproblemeobținutăînurmadescumpuneriisauesteconstruităsimultanînetapele
dedescompunere.
III.1)Problemă:Sumaelementelordintr-unvector
CuajutorulmetodeiDivideetImpera,realizațiofuncțiecaresădeterminesuma
elementelordintr-unvectordelungimen.Elementelevectoruluisuntnumereîntregi.
#include<iostream>
usingnamespacestd;
intsuma(intv[100],intl,intr)
{if(l==r)returnv[l];
elsereturnsuma(v,l,(l+r)/2)+suma(v,(l+r)/2+1,r);
}
intmain()
{
intv[100],n,i;
cin>>n;
for(i=1;i<=n;i++)cin>>v[i];
cout<<suma(v,1,n);
system("pause");
return0;
}

60III.2)Celmaimaredivizorcomun
CuajutorulmetodeiDivideetImpera,realizațiofuncțiecaresădetermine
celmaimaredivizorcomunalelementelorîntregidintr-unvectordelungimen.
Descriereaproblemei:
Citimdelimitărilevectoruluiprinindicii ),(rl.
Descompunemproblemainițială,îndouăsubproblemealecărorindicidevin ),(ml și
),1 (rm .Variabilamidentificăindicelemijloculuidinvectorulinițial.
Dacăllr ,soluțiaestecmmdc(rvlv, ).
Aceastăproblemăpoatefirezolvatăprinaplicareaproprietățiideasociativitatea
operațieicmmdc.
#include<iostream>
usingnamespacestd;
intv[100],n,x;
voidcitire()
{
cout<<"numaruldeelemente=";cin>>n;
cout<<"siruldeelemente\n";
for(inti=1;i<=n;i++)
{cout<<"v["<<i<<"]=";cin>>v[i];
}
}
intalgoritm(inta,intb)
{if(a==b)returna;
elseif(a>b)returnalgoritm(a-b,b);
elsereturnalgoritm(a,b-a);
}
intcmmdc(intp,intu)
{intm;
if(u-p==1)algoritm(v[p],v[u]);
else
if(p==u)returnv[p];
{
m=(p+u)/2;
returnalgoritm(cmmdc(p,m),cmmdc(m+1,u));
}}
intmain()
{
citire();
cout<<"cmmdc="<<cmmdc(1,n);
}

61III.3).Rădăcinadeordin3
#include<iostream>
usingnamespacestd;
doubleradcubica(doublex,doublea,doubleb)
{
if(b-a<=0.0001)returnb;
else
{doublem=(a+b)/2;
if(m*m*m<x)returnradcubica(x,m,b);
elsereturnradcubica(x,a,m);
}
}
intmain()
{doublex;
cin>>x;
if(x>0)if(x<1)cout<<radcubica(x,0,1);
elsecout<<radcubica(x,0,x);
elseif(x>-1)cout<<radcubica(x,-1,0);
elsecout<<radcubica(x,x,0);
system("pause");
return0;
}
18
2.26209
III.4)MergeSort
Pentruunvectorvdedimensiunen,realizațiunsubprogramcaresăimplementezeo
sortareprininterclasare.
Sedăunvectorrlv….SeîmpartevectorulvîndouăpărțișivomapelamSort
pentruasortafiecaresubvector,șifuncțiacombinapentruacontopiceidoisubvectori
sortați.
Dacărl,problemanumainecesităodescompunere,vectorulestedejasortat.
Interclasare(rmlv ,,, )estecheiaprocedeuluicareneasigurăcăvectoriimlv…și
rmv …1 dejasortați,sevorcombinapentruaformaunsingurvector.
Găseșteelementuldinmijlocpentruaîmpărțivectorulîndoisubvectori
Mijlocul 2/) (rlm
1.ApeleazămSort ),,(mlv
2.ApeleazămSort ),1 ,(rmv
3.Apeleazăcombina ),,,(rmlv
Vectorulinițial

623,0,5,67,12,7,9,15
Vectorsortat:
27915324567
#include<iostream>
usingnamespacestd;
voidinterschimbare(int&a,int&b)
{
intt;
t=a;
a=b;
b=t;}
voidafisare(int*v,intsize){
for(inti=0;i<size;i++)
cout<<v[i]<<"";
cout<<endl;}
voidcombina(int*v,intl,intm,intr){
inti,j,k,ns,nd;
ns=m-l+1;nd=r-m;
intsv[ns],dv[nd];
for(i=0;i<ns;i++)
sv[i]=v[l+i];
for(j=0;j<nd;j++)
dv[j]=v[m+1+j];
i=0;j=0;k=l;
while(i<ns&&j<nd){
if(sv[i]<=dv[j]){
v[k]=sv[i];
i++;
}else{
v[k]=dv[j];
j++;
}
k++;
}
while(i<ns){
v[k]=sv[i];
i++;k++;
}
while(j<nd){
v[k]=dv[j];
j++;k++;
}}
voidmSort(int*v,intl,intr){
intm;
if(l<r){
intm=l+(r-l)/2;
mSort(v,l,m);
mSort(v,m+1,r);
combina(v,l,m,r);
}}

63intmain()
{
intv1[]={3,0,5,67,12,7,9,15};
intn=sizeof(v1)/sizeof(v1[0]);
printf("Vectorulinitial:\n");
afisare(v1,n);
mSort(v1,0,n-1);
printf("\nVectorsortat:\n");
afisare(v1,n);
return0;
}
III.5)QuickSort
QuicksortesteunalgoritmcareprovinedinmetodaDivideetImpera.
Problemă:Pentruunvectorvdedimensiunen,realizațiunsubprogram
caresăimplementezealgoritmulQuikSort.
Considerămcăvectorulprincipal,careestedelimitatdeindiciilșir.
Ultimulelementdinvectorv,rv esteplasatînpozițiacorectănotatăcupoz,în
vectorulordonat..Toateelementeledinstângaelementulrvsuntmaimici,iarcele
dindreaptamaimari.
Problemasedescompuneîndouăsubproblemedelimitatedeindicii
)1 ,(pozl și ),1 (rpoz .Fiecareproblemăurmăreștesăsortezesubvectoruluipe
careîlprelucrează.
Dacărl,vectorulestedejasortat.
Problemaaresoluțiedoardacăpoatefiaplicatprocesulrecursivde
descompunerepânăcândobținemproblemeelementare.
#include<bits/stdc++.h>
usingnamespacestd;
voidschimba(int*a,int*b)
{
intt=*a;
*a=*b;
*b=t;
}

64intfunctie(intv[],intl,intr)
{
intpoz=v[r];
inti=(l-1);
for(intj=l;j<=r-1;j++)
{
if(v[j]<poz)
{
i++;
schimba(&v[i],&v[j]);
}
}
schimba(&v[i+1],&v[r]);
return(i+1);
}
voidqSort(intv[],intl,intr)
{
if(l<r)
{
intk=functie(v,l,r);
qSort(v,l,k-1);
qSort(v,k+1,r);
}
}
voidafisare(intv[],intsize)
{
inti;
for(i=0;i<size;i++)
cout<<v[i]<<"";
cout<<endl;
}
intmain()
{
intv[]={10,7,8,9,1,5};
intn=sizeof(v)/sizeof(v[0]);
qSort(a,0,n-1);
cout<<"Vectorsortateste:\n";
afisare(v,n);

65return0;}
Vectorulsortat:1,5,7,8,9,10
III.6)Căutareabinară
Pentruunvectordelungimensortatcrescătorrealizațiofuncțiecare
determinăpozițiaelementuluik.Dacăelementulknuaparținevectorului,atunci
returnează0.
Considerămcăvectorulprincipal,careestedelimitatdeindiciilșir.Problemapoate
fidescompusăîndouăsubproblemedelimitatedeintervalele )1,(ml și ),(rm .
Variabilamesteindiceledemijlocalvectoruluiprincipal.
Dacăxmv,soluțiaesteindicelem.
Dacămmvcăutareasevarealizaînprimulsubvector )1,(ml ,altfelseva
realizaîncelălaltsubvector.
Observămcăprinaceastămetodă,amredusproblemaprincipală,laoproblemăde
dimensiunemaimică.Vomaveadouăproblemededimensiuneredusă,daralgoritmul
sevaaplicadoarpentruuna.
Cuajutorulacesteimetode,găsimmultmaiușorintervalulîncaresegăseștesoluția,
decietapadecombinareasoluțiilordinceledouăintervalevalipsi.
#include<iostream>
usingnamespacestd;
intv[100],n,k;
voidcautbin(intl,intr)
{
intm=(l+r)/2;
if(k==v[m])
cout<<"pozitiaelementuluieste="<<m;
else
if(l<r)
if(k<v[m])
cautbin(l,m-1);
elsecautbin(m+1,r);
elsecout<<"nuafostgasit.";
}
intmain()
{
cout<<"n=";cin>>n;
for(inti=1;i<=n;i++)
{
cout<<"v["<<i<<"]=";cin>>v[i];
}
cout<<"k=";cin>>k;
cautbin(0,n);
return0;
}

66






40372615041 32 24 17

pozitiakvvvvvvvn
III.7)Sumaelementelorprimedintr-unvector
Determinaținumărulelementelorprimedinacestvectordelungimen.
6
012365
3
#include<iostream>
usingnamespacestd;
intv[100],n;
intverificareprim(intn)
{
if(n<=1)return0;
inti=2;
while(i<=n/2)
if(n%i==0)return0;
elsei++;
return1;
}
intimpartire(intl,intr)
{
intm,x;
if(l==r)
if(verificareprime(v[l])and(v[l]!=1))
return1;
elsereturn0;
else
{m=(l+r)/2;
returnimpartire(l,m)+impartire(m+1,r);;
}
}
intmain()
{

67cin>>n;
inti;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<impartire(1,n);
}
CuajutprulmetodeialgoritmulDivideetimpera,săsecalculezesuma:
)1( …3221  nn S
Pentrun=20
Suma=3080
#include<iostream>
usingnamespacestd;
intn;
voidimparte(intl,intr,int&suma)
{
intm,suma1,suma2;
if(l==r)
termen=l*(l+1);
else
{m=(l+r)/2;
imparte(l,m,suma1);
imparte(m+1,r,suma2);
suma=suma1+suma2;
}
}
intmain()
{intsuma=0;
cin>>n;
imparte(1,n,suma);
cout<<suma;
}III.8)Sumaprodusdedoitermeniconsecutivi

68III.9)Metodabisectieiuneifunctiipeintervale
Sedăfuncția  300,300 :f , 1 7 5)(2 3xxxf .Determinațiosoluțiea
funcției 0)(xf peintervalul300,300 cuoeroarede610.
Dateieșire:Valoarearadaciniieste-0.339118.
#include<iostream>
usingnamespacestd;
#defineeroare0.000001
doublefunctie(doublex){
return5*x*x*x-7*x*x+1;
}
voidbisectiem(doublel,doubler){
if(functie(l)*functie(r)>=0){
cout<<"farasolutie\n";
return;
}
doublem=l;
while((r-l)>=eroare){
m=(l+r)/2;
if(functie(m)==0.0)
break;
elseif(functie(m)*functie(l)<0)
r=m;
else
b=m;
}
cout<<"solutiaeste"<<m;
}
intmain(){
doublel=-300,r=300;
bisectiem(l,r);
return0;
}

69Bibliografie:
1)MiloșescuMaria,Informatică.ManualpentruclasaaXI,EdituraDidactică
șiPedagogică,București,2006
2)MateescuD.M,MoraruP,Informaticăpentruliceușibacalaureat,Materia
declasaaIX-a,edituraDonaris,Sibiu2006
3)DanaLica,MirceaPasoi,FundamenteleProgramării,Culegerede
problemepentruclasaaXI-a,EdituraL&SSoft,2006
8)AdrianRunceanu,Metodeșitehnicideprogramare,EdituraAcademică
Brâncuși,2003
Site-uri
http://info.mcip.ro/?cap=Backtracking&prob=363
https://informaticacnet.wordpress.com/category/clasa-a-xi-a/metode-backtra
king/
http://ro.wikipedia.org/wiki/Backtracking
http://en.wikipedia.org/wiki/Backtracking
https://infoarena.ro/
https://www.pbinfo.ro/articole/16619/metoda-greedy
https://www.geeksforgeeks.org
https://info.mcip.ro