II.Recursivitate.

Definiiirecursive.

Odefiniierecursivfolosetetermenuldedefinitncorpuldefiniiei.Ofunciepoatefirecursiv,adicsepoateapelapeeansi,nmoddirectsauindirect,printrunlandeapeluri.

/* apel recursiv direct*/voidf(intx){...f(10);...}

/*apelrecursivindirect*/voidf2(int); /*declaratieanticipataf2voidf1(intx) voidf2(inty){... {...f2(10); f1(20);... ...} }

ncazulrecursivitiiindirecte,compilatorultrebuiesverificecorectitudineaapelurilorrecursivedinfiecarefuncie.Odeclarareanticipataprototipurilorfunciiloroferinformaiisuficientecompilatoruluipentruafaceverificrilecerute.

Exemple.

10.numrulnatural 1N dacxNatuncisucc(x)N

20.factorialuln!= 1 dac n=0 n*(n1)! dac n>0

longfact(intn){return(n?n*fact(n1):1);}

30.celmaimaredivizorcomuncmmdc(a,b)= a dacb=0 cmmdc(b,a%b) dacb>0

intcmmdc(inta,intb){return(b?cmmdc(b,a%b):a);}

40.arborelebinar arborelevidestearborebinar x estearborebinar,cuSSiSDarboribinari

SSSDOricedefiniierecursivaredoupri:

bazasauparteanerecursiv partearecursiv

1

Codulrecursiv: rezolvexplicitcazuldebaz apelurilerecursiveconinvalorimaimicialeargumentelor

Funciiledefiniterecursivsuntsimpleielegante.Corectitudinealorpoatefiuorverificat.Definireaunorfunciirecursiveconducelaineficien,motivpentrucareseevit,putndfinlocuitntotdeaunapriniteraie.Definireaunorfunciirecursiveestejustificatdacselucreazcustructuridedatedefinitetotrecursiv.

Recursivitateliniar.Esteformaceamaisimplderecursivitateiconstdintrunsingurapelrecursiv.Deexemplupentrucalcululfactorialuluiavem:

f(0)=1 cazuldebazf(n)=n*f(n-1) cazulgeneralSevedecdactimpulnecesarexecuieicazuluidebazesteaiacazuluigeneralesteb,atuncitimpultotaldecalculeste:a+b*(n1)=O(n),adicavemcomplexitateliniar.

Recursivitatebinar.Recursivitateabinarpresupuneexistenaadouapelurirecursive.ExemplultipiclconstituieirulluiFibonacci:longfibo(intn){if(n

Deundededucem:

f2n=fn+1fn+fnfn1=fn(fn+1+fn1)=fn(fn+2fn1)f2n1=f2n+f2n1

Calcululluifnsefacefolosindprimasauadouadintrerelaiiledemaisusnfunciedeparitatealuin(dacnesteparatuncicalcululluif(n)presupunecalcululluif(n/2)if(n/21),altfelf((n1)/2)if((n+1)/2)

voidfiblog(intn,long*f1,long*f2){longa,b,c,d;if(n==1){*f1=0;*f2=0;}else{fiblog(n/2,&a,&b);c=a*a+b*b;d=b*(b+2*a);if(n%2){*f1=d;*f2=c+d;}else{*f1=c;*f2=d;}}}

3

Metodadivizrii(DivideetImpera).

Unalgoritmrecursivobinesoluiaproblemeiprinrezolvareaunorinstanemaimicialeaceleeaiprobleme.

semparteproblemansubproblemedeaceeainatur,dardedimensiunemaisczut

serezolvsubproblemeleobinndusesoluiileacestora

secombinsoluiilesubproblemelorobinndusesoluiaproblemei

Ultimaetappoatelipsi(nanumitecazuri),soluiaproblemeirezultnddirectdinsoluiilesubproblemelor.

Procesuldedivizarecontinuipentrusubprobleme,pncndseajungelaodimensiunesuficientderedusaproblemeicarespermitrezolvareaprintrometoddirect.

Metodadivizriiseexprimnaturalnmodrecursiv:rezolvareaproblemeiconstnrezolvareaunorinstanealeproblemeidedimensiunimaireduse

void DivImp(int dim, problema p, solutie *s){ int dim1, dim2; problema p1, p2; solutie s1, s2; if(dim > prag){ Separa(dim,p,&dim1,&p1,&dim2,&p2); DivImp(dim1, p1, &s1); DivImp(dim2, p2, &s2); Combina(s1, s2, s); } else RezDirect(dim, p, s);}Pentruevaluareacomplexitiiunuialgoritmdezvoltatprinmetodadivideetimperaserezolvoecuaierecurentavndformageneral:T(n)=a.T(n/b) + f(n), ncare a >= 1, reprezintnumrulsubproblemelor,iarn/bestedimensiuneasubproblemelor,b>1.

f(n)reprezintcostuldivizriiproblemeinsubproblemeiacombinriisoluiilorsubproblemelorpentruaformasoluiaproblemei.

Soluiaacesteiecuaiirecurenteestedatdeteoremamaster

10.dacatunci

20.dacatunci

30.daci

atunci

Exemple

Ridicareaunuinumrlaoputerentreag.

4

)n(O)n(f alog b = )n()n(Talog b=

)n()n(f alog b= )nlgn(O)n(Talog b

=

)n()n(f alog b += 1c),n(fc)b/n(fa

double putere(double x, int n) { if (n==0) return 1; double y = putere(x, n/2); if (n%2==0) return y*y; else return x*y*y;}Seconstatcnurmaseparriiserezolvosingursubproblemdedimensiunen/2.Aadar:T(n)= T(n/2)+1,carearesoluiaT(n)=O(log2n).

Cutareabinar

secomparvaloareacutatycuelementuldinmijlocultablouluix[m]

dacsuntegale,elementulyafostgsitnpoziiam

ncazcontrarsecontinucutareantrunadinjumtiletabloului(nprimajumtate,dacyx[m]).

Funciantoarcepoziiamavaloriiynxsau1,dacynuseaflnx.ComplexitateaesteO(log2n)

intCB(inti,intj,doubley,doublex[]){if(i>j)return1;doublem=(i+j)/2;if(y==x[m])returnm;if(y

ElementulmaximdintrunvectorAplicareametodeidivizriisebazeazpeobservaiacmaximulesteceamaimarevaloaredintremaximeledinceledoujumtialetabloului.double max(int i, int j, double *x){ double m1, m2; if(i==j) return x[i]; if(i==j-1) return ( x[i]>x[j]? x[i]:x[j];); int k = (i+j)/2; m1 = max(i, k, x); m2 = max(k+1, j, x); return (m1>m2)? m1: m2;}

TurnuriledinHanoiSedau3tije:stnga,centru,dreapta;peceadinstngasuntplasatendiscuricudiametredescresctoare,formndunturn.Generaimutrilecaredeplaseazturnuldepetijadinstngapeceadindreapta.Seimpunurmtoarelerestricii:

launmomentdatsepoatemutaunsingurdisc

nusepermiteplasareaunuidiscdediametrumaimarepesteunulcudiametrulmaimic

unadintijeservetecazondemanevr.Problemamutriicelorndiscuridinzonasursnzonadestinaiepoatefiredusladousubprobleme:

mutareaan-1discuridinzonasursnzonademanevr,folosindzonadestinaiecazondemanevr

mutareaan-1discuridinzonademanevrnzonadestinaie,folosindzonasurscazondemanevr

ntreceledousubproblemesemutdisculrmasnzonasursnzonadestinaie

void Hanoi(int n,char s,char m,char d){ if(n) { Hanoi(n-1, s, d, m); Printf(%d -> %d\n, s, d); Hanoi(n-1, m, s, d); }}Avemsatisfcutecuaiarecurent:T(n) = 2.T(n-1) + 1,careserescrie:T(n)=22T(n2)+1)+1=22T(n2)+2+1=23T(n3)+22+2+1=2n1T(1)+2n2++2+1T(n)=2n1+...+2+1=2n1=O(2n)

Sortareaprininterclasare(mergesort)iruldesortatsempartendousubiruridedimensiunepectposibilegal.Sesorteazsubirurile(divizndulerecursivnaltesubiruri,pncndseajungelasubiruridelungime1,caresuntgatasortate).Subirurilesortateserecombinntrunsingurirsortatprininterclasare.

voidmerge(int,int,int,double*);

6

void msort(int, int, double*);void mergesort(int n, double *x){ msort(0, n-1, x); }

void msort(int i, int j, double *x){ if(i

do { j--;} while (x[j]>=piv); if(i < j){ t=x[i]; x[i]=x[j]; x[j]=t; } else return j; }}

CeldealNleaelement.

OmetodevidentdegsireaceluidealNleaelementarfisortareavectoruluiiselectareaelementuluidinpoziiaN,cucomplexitateO(n log2n).Ometodavndocomplexitatemaimicpartiioneazvectorulnraportcuunpivot.Dacprimulelementdinceadeadouapartiieestenpoziiaj==N,atuncielementeleprimeipartiiisuntmaimicisauegalecuacesta,decielementulreprezintceldealNleaelement;dacj > N celdealNleaelementseaflnprimapartiiedecivaficutatrecursivndomeniul(p, j),ncazcontrarelseaflnceadeadouapartiie,fiindcutatrecursivndomeniul(j, r).double elementN(double* v,int N,int p, int r){ int j = pivot(v, p, r); if(j==N) return v[N]; if(N

}ComplexitateaalgoritmuluidepartiionareesteO(n).Complexitateaalgoritmuluidesortaredepindedeechilibrareapartiiilor.Dacpartiiilesuntdezechilibrate(ncazulcelmainefavorabil,ncareirulestesortatdescresctorceledoupartiiisuntde1,respectivn-1elemente),atuncicomplexitateaesteO(n2).

nlturarearecursivitii.

ngeneralrecursivitateanuesteeficient.DeexemplugenerarearecursivatermeniloriruluiFibonacciarecomplexitateexponenial,ntimpcesoluiaiterativarecomplexitateliniar.

Algoritmiiformulaifolosindstrategiadivideetimperasunteficienidacsubproblemelesuntdedimensiuniaproapeegale.(pentrusubproblemecudimensiunidezechilibratedeexempluturnuriledinHanoi,seobinetotcomplexitateexponenial).

Seprefersoluiirecursivensituaiilencarevariantaiterativconducelaalgoritmifoartecomplicai.

Recursivitateapoatentotdeaunafitransformatniteraie.nacestscopsefoloseteostiv.Dacfunciaconineunsingurapelrecursiviacestaesteultimainstruciune(recursivitate terminal)transformarearecursivitiiniteraiepresupuneurmtoriipai:

o setranscrieparteanerecursiv,cuparametriicureniivariabilelelocaleo seactualizeazvariabileleiparametriicorespunztornoiiiteraiio seefectueazunsaltlanceputulpriiiterative

Exemplificmcuafiareaelementeloruneilistenlnuite:

struct nodL { int info; struct nodL* leg;};void afisare(struct nodL* L) { if(L){ printf(%d\n, L->info); afisare(L->leg); }}void afisare(struct nodL* L){ label 1; 1:if(L){ printf(%d\n, L->info); L = L->leg; goto 1; }}Desfinmsaltulnecondiionatgotofolosinduncicluwhile:

void afisare(struct nodL* L) {

9

while(L){ printf(%d\n, L->info); L = L->leg; }}Dacfunciaconineunsingurapelrecursiv,carenuesteterminal,vomfolosiostivncaresepunparametriiivariabilelelocale.Variantaiterativaalgoritmuluirecursiveste:

while(se fac apeluri recursive) { partea nerecursiva care precede apelul; Push(S, parametri); Push(S, variabile locale); actualizare param.si var.locale pt.urmatorul apel;}while(!S_Empty(S)){ Pop(S); parte nerecursiva de dupa apelul recursiv;}Definimofuncierecursivcareafieazelementeledintrolistnlnuitiapoifaceafiareaelementelornordineinvers,ncepndcuultimul:

void afisare(nodL* L) { if(L){ printf(%d-, L->info); afisare(L->leg); printf(%d\n, L->info); }}Ovariantiterativeste:

void afisare(nodL* L) { Stiva S; while(L){ printf(%d-, L->info); Push(L, S); L=L->leg; } while(!S_Empty(S)){ L=Pop(S); printf(%d\n, L->info); }}

10

MetodaBacktracking.

Metodabacktrackingreprezintunadintremetodelecelemaigeneralepentrudeterminareasoluiiloruneiprobleme.

Pentruaplicareametodeiestenecesarcasoluiaproblemeisseexprimeprintrunntuplu(x1,x2,,xn),ncarexiSi, Sifiindomulimefinit,izomorfcumulimea{1:m}.Acestecondiiipoartnumelederestricii(saucondiii)explicite,iartupliicaresatisfacrestriciileexplicite(produsulcartezianS1xS2xxSn)definescspaiulsoluiilor problemei.

Deexemplu,pentrugenerareapermutrilordenobiecte,mulimileSi={1:n}permitformareaanntuplicaredefinescspaiulsoluiilor.OsoluievectortrebuiessatisfacofunciecriteriuP(x1,...,xn),cunoscutisubnumelederestricii(saucondiii)implicite.Generareatuturortuplilorprodusuluicartezian

iselectareacelorcaresatisfacrestriciileimplicite,cunoscutsubnumeledemetodaforeibrute,nuesteaplicabil,datoritcomplexitiiexponenialeilipseioricreiposibilitideoptimizare.

Restriciileimpliciteacioneazcaofunciedetiere(limitare),reducnddimensiuneaspaiuluisoluiilorproblemei,frageneratoituplii.

Deexemplu,ngenerareapermutrilorexistrestriciaimplicitcaelementelevectoruluisoluiesfiedistincte,ceeacereducenumrulposibilitilor(soluiilor)lan!.Restriciileexplicitedefinescunarbore(implicit)alspaiuluisoluiilor.Osoluiereprezintocaledelanodulrdcinlaunnodterminal.Cutareanspaiulstrilorpresupunetraversareaacestuiarbore.nmetodabacktracking,aceasttraversaresefacenadncime.Metodabacktrackinggenereazsoluianmodprogresiv,adugndlasoluiaparial,x1,...,xk1ocomponentxk,astfelnctsoluiaparialextinsssatisfacocondiieimplicit,cunoscutsubnumeledecondiiedecontinuare.P(x1,...,xk)ngenerareastrilorproblemeisepornetedinstareainiial(nodulrdcin)isegenereazaltenoduri.Unnodgeneratpoartnumeledenodviu,dacnuiaufostgenerainctoidescendenii.Aadar,amputeadefinimetodabacktrackingcaogeneraredenodurinadncimenarborelespaiuluistrilorsoluiilor,folosindfunciidelimitare.Complexitateametodeirmneexponenial,eficienaeidepinzndnmodsemnificativdeeficienafunciilordetiere.

Datoritcomplexitiiexponeniale,metodabacktrackingsefolosetenumainsituaiilencarenudispunemdealtemetode

generareapermutrilordenobiecte generareatuturorplasrilora8damepeotabldeah,astfelnctsnuseatace determinareatuturorposibilitilordeplatauneisume,folosindanumitetipuride

bancnote determinareatuturorposibilitilordesortaretopologicavrfurilorunuigraf

GsireaunuiarboredeacoperiredecostminimntrungrafponderatsedetermineficientprinalgoritmiigreedyPrimiKruskal.Gsireatuturorarborilordeacoperirepoatefifcutnumaiprinbacktracking.

Dintretoatesoluiileuneiproblemedeoptimizare,prezintinteresnumaicelecareextremizeaz(maximizeazsauminimizeaz)ofunciedecost(saufuncieobiectiv)cadeexemplu:

11

== ==

nn

1ii

n

1ii mmS

gsireatuturorcilordelungimeminim,deieiredintrunlabirint colorareavrfurilorunuigraffolosindunnumrminimdeculori gsireaciclurilorhamiltonienedecostminimntrungrafponderat debitareauneibaredupnitereperedate,astfelnctrestuldetieresfieminim problemadiscretarucsacului

Presupunemcsageneratsoluiaparial(x1,x2,,xk1)idorimsoextindemprinadugareacomponenteixk.Aparurmtoarelesituaii:

dacnusepoategeneraxk,serevineasupraluixk1isegenereazoaltvaloare dacsepoategeneraxki

o suntndeplinitecondiiiledecontinuareo dacestesoluiesereineiserevinecutndaltxk(altsoluie)o dacnuestesoluiesegenereazxk+1

nusuntndeplinitecondiiiledecontinuaresegenereazunnouxk

intn;lungimeasoluieiintnsol;numruldesoluiiintx[N];vectorulsoluieintinf;marginea.inferioaradomeniuluivalorilorcomponentealesolutieiintsup;marginea.superioaradomeniuluivalorilorcomponentealesolutieiintxopt[N][NSOL];soluiileoptimalevoidBKT(int);funciecarerealizeazstrategiabacktrackingnmodrecursivsauiterativvoidRetSol();funciecarerealizeazprelucrrilenecesarelagsireauneisoluiiintContinuare(int);funciecareverificdacsuntndeplinitecondiiiledecontinuareintSolutie(int);funciecareverificdacsaobinutsoluieintSuccesor(int);funciecareverificdacmaiexistvaloridisponibilepentruxkvoidInclude(int);conineprelucrrileasociateselectriiuneicomponentevoidExclude(int);conineprelucrrileasociaterenunriilaocomponentselectat

//backtrackingrecursivvoidBKT(intk){if(Solutie(k))RetSol();elsefor(;x[k]S[k]&&P(x[0],,x[k]);)BKT(k+1);}voidBKT(intk){if(Solutie(k))RetSol();elsewhile(x[k]=Successor(k))if(Continuare(k))BKT(k+1);}

voidBKT(intk){if(Solutie(k))

12

RetSol(); else { x[k] = inf-1; while(Succesor(k)) if(Continuare(k)) BKT(k+1); }}void BKT(int k) { int i; for (i=inf;i n) RetSol(); else for (i=inf;in){ //avem solutie RetSol(); k--; //cauta alta solutie } else //solutie incompleta if(x[k]

{ x[k]=inf-1; k--; //se revine la x[k-1] }}

void BKT () { int k=1, exista, corect; x[k] = inf-1; while(k > 0) { do { exista = Succesor(k); corect = Continuare(k); } while(exista && !corect); if(exista) if(Solutie(k)) RetSol(); else x[++k] = inf-1; else k--; }}}

void BKT(){ int k=1; while(k){ if(Solutie(k)){ RetSol(); nsol++; k--; //pas inapoi pt gen. alta solutie } else if(x[k]

scanf(%d, &n); BKT(0);}int Solutie(int k){ return k> n-1;}void RetSol(){ for(int i=0; i

else printf(0); printf(\n); }}3.Ssegenerezeosoluiedeacoperireauneitabledeahdedimensiunenxndectreuncal,carepornetedepetabldintropoziieiniial(x0,y0)iurmeazodeplasarespecificnL,fraieinafaratableideahifratreceprinpoziiipecareleaparcursdeja.Soluiaestedelungimefixn2iestereprezentatprintromatrice,completatcunumereledeordinealemutrilor,ncepndcupoziiainiial,numerotatcu1.Opoziieliberpetablestemarcatcu0.Avansareapetabldintropoziiecurent(xc,yc)ntropoziieurmtoare(xu,yu)indic8posibilitivirtuale,dacmutareaestepetabl:0

BKT(k+1,xu,yu); Elibereaza(xu,yu);; } }}Funciamain()citetenipoziiainiial(x0,y0),iniializeaztablacaliber,plaseazcalulnprimapoziieiapeleazfunciaBKT()pentruageneracelelaltemutri.#include #define N 8#include backtrack.hint dx[8]={2,1,-1,-2,-2,-1,1,2};int dy[8]={1,2,2,1,-1,-2,-2,-1};int main(){ int x0,y0; scanf(%d, &n); scanf(, &x0, &y0); //initializare tabla for(int i=0; i

(ncazcontrarnuammaiaveasoluiecuseleciafcutpnacum).Vomevitacalcululn

fiecarepasalsumeloripunndacestevalorinlistadeparametriaifunciei

BKT().Aceastaimplica0 Si.

Apeluliniialpresupunecalcululnprealabilalultimuluiparametru.

nfunciaBKT()vomconsideraseparatceledousituaii:x[k]=1selectmcomponentaa[k]ix[k]=1nuselectmcomponenta.Condiiiledecontinuare,caistabilireadacsagsitsoluieseformuleazexplicit,framaidefinifunciisuplimentare.

Problemepropuse.Divideetimpera

1.Pentruevaluareapolinomuluipn(x)=a0+a1x++anxnprinmetodadivideetimpera,segrupeaztermeniipolinomuluisubforma:a)pentrunpar:n=2k

pn(x)=a0+a2x2+...+a2kx2k+x(a1+a3x2+...+a2k1x2k2)=b0+b1y+...+bkyk+y(c0+c1y++ck1yk1)b)pentrunimpar:n=2k+1

pn(x)=a0+a2x2+...+a2kx2k+x(a1+a3x2+...+a2k+1x2k)=b0+b1y+...+bkyk+y(c0+c1y++ckyk)Seevalueazdirectnumaipolinoameledegrad0i1.Scrieiofunciecusemntura:

doublepoly(intn,double*a,doublex);

careevalueazpolinomulprinmetodadescris.Exemplu:1x+2x24x3+3x4+x5=1+2x2+3x4x(1+4x2x4)=2p=1+2y+3y2y(1+4yy2)=1+3y2+y(2)y[1y2+y(4)]=

( ) ( ) ` ``

41231 zzzz +++=

2.Pentruevaluareapolinomuluipn(x)=a0+a1x++anxnprinmetodadivideetimpera,segrupeaztermeniipolinomuluisubforma:a)pentrunpar:n=2kpn(x)=a0+a1x+...+akxk+xk+1(ak+1+ak+2x2+...+a2kxk1)=a0+a1x+...+akxk+xk+1(b0+b1x++bk1xk1)b)pentrunimpar:n=2k+1pn(x)=a0+a1x+...+akxk+xk+1(ak+1+ak+2x+...+a2k+1xk)=a0+a1x+...+akxk+xk+1(b0+b1x++bkxk)Seevalueazdirectnumaipolinoameledegrad0i1.Scrieiofunciecusemntura:doublepoly(intn,double*a,doublex);careevalueazpolinomulprinmetodadescris.Exemplu:p(x)=1x+2x2+4x3+3x4+x5+2x6=1x+2x24x3)+x4(3+x+2x2)=

18

=

1n

0jja,0,0BKT

=

k

0jjjxa

+=

1n

1kjja

=

1n

1jj Sa

` ``

+++

+ 2xx3xx42xx1 242

Sedunvectorxcunelementeiunntreg0 k

Descompunereaminimvafireprezentatprintrunirdeptrateiundreptunghi.Deexemplu:a=21,b=34seobin5ptrate21,13,4,8,1iundreptunghi17Indicaie:Sedefineteofuncierecursivdedescompunere(cuparametrilaturileunuidreptunghi,numruldefigurinedecompozabileidimensiunileacestora),caredetermin(dacdreptunghiulpoatefidescompus)celedoumodalitidedescompunereiseselecteazdescompunereacunumrminimdecomponente.

9.Obucatdetabldedimensiunia x barepracticatenguricucentreleavndcoordonatele(x[i],y[i]),raportatelacolulstngajos,consideratcaorigine.Diametrelegurilorseconsiderneglijabile.Determinai,princoordonateleadoucoluriopuse,folosindostrategiedivideetimpera,bucatadreptunghiulardeariemaxim,carenuconineguri,cesepoatedecupaprintierepedireciiparaleleculaturile.

10.ntrunparcdeformdreptunghiularcudimensiunilea x bseaflncopaci,avndcoordonatele(xi,yi),i=0:n1,nraportcuorigineacolulstngajosalparcului.Gsiitoateamplasamenteleposibilepentruunterendetenis,avnddimensiunileuxv,fratianacestscopvreuncopac.Unamplasamentesteundreptunghicarenuincludecopacininteriorulsu,cinumaipemargini,caracterizatprindimensiunilesaleicoordonatelecoluluistngajos,raportatelaacelaisistemdecoordonate.

Indicaie:ntrunterendreptunghiular,datprindimensiuniicoordonatelecoluluistngajosseverificdacexistcopaci.Prezenaunuicopacmpartemaintiterenulprintroorizontalndouterenuri(iapoiprintroverticalnaltedouterenuri),ncare,nmodrecursivsecautcopaci.nmomentulncareseobineunterenfrcopaci,severificdacdimensiunileluipotformaunterendetenis,incazafirmativsememoreazdimensiunileluiicoordonatelecoluluistngajos.

11.PentrucalcululceluimaimaredivizorcomunadounumeresefolosetealgoritmulluiEuclid.Pentruacalculacmmdcannumereplasatentruntablou,folosindmetodadivideetimpera,sempartetabloulndoujumtiisecalculeazcmmdcalcelordoidivizoricomuniaicelordoujumtialetabloului.Calculaicmmdcalelementelortablouluiievaluaicomplexitatea.

Backtracking

1.Peotabldeahdedimensiunen x nsedaucoordonatele(x,y)aleunuirege,aleunuicaliapobstacole.Scrieiunprogramcareslajutepecalsajunglaregeissentoarcnapoinpozitiadeplecare,genernduitoatetraseeleposibile,urmndmersulspecificnLalcalului,evitndobstacolele,faraieidepetablifaratreceprinpozitiipecareleaparcursdeja.Programulvagenerafiecaretraseuilungimeasa

2.DupocercetareatentainscriptiilorobscenedepeziduridetipulIONUT+MARIA=COSTEL,Vasilicaajunslaconcluziacacesteanureprezinttriunghiuriconjugale,cisimpleoperaiideadunarenbaza10codificate.ScrieiunprogramcarteslajutepeVasilicsdescifrezemisterioaseleadunri,stabilindcorespondenelentrelitereicifre.

20

3.Acoperireacunoduriaarcelorunuigraf.FiinddatungrafneorientatG=(V,M),ssedeterminenumarulminimdevrfuri(osubmulimeamulimiiV)careacopertoatemuchiilegrafului(mulimeaM).Indicatie:Vectorulsoluiecontinenumeredevrfuriiareolungimevariabila,maimicsauegalcun(nfiindnumaruldevrfuridingraf).Conditiadeacceptareaunuivrfnpozitiakdinvectorulsoluie:snufifostselectatanterior(diferitdex[0],..x[k-1])Saajunslaosoluieatuncicndaufostacoperitetoatemuchiiledingraf.Sevastabilimainticumsetineevidentamuchiiloracoperiteirespectivneacoperitencdingraf.

Exempludedate:Grafulcu7noduriicumuchiile:(1,2),(2,3),(3,4),(3,5),(4,5),(4,6),(5,6),(4,7).Soluiaoptimfoloseste3noduri:x[1]=2,x[2]=4,x[3]=5.

4. Pentru ca echipanational de fotbal s obin rezultate mai bune, Iordnescua recurs laserviciileunuiinformatician,careapropustrecereacelor11jucatoripealteposturidectcelepecareevolueaznmodobinuit,nscopulimbuntiriirandamentuluiglobalalechipei.Pentruaceastasafcutoevaluareavaloriifiecruijuctorprintrunprocentajipentrufiecarejuctorsaevaluat(totprocentual),randamentulutilizriijuctoruluipefiecarepost.

Folosindacestedate,ssestabileascoalocareajuctorilorpeposturiastfelnctrandamentulglobalalechipeisfiemaxim.

5.Peocasettrebuiescnregistratenmelodii.Pentrufiecaremelodiesecunoateduratansecunde.Determinaiitoateposibilitiledeplasarealemelodiilorpeceledoufee,astfelcadiferenaduratelorcelordoufeesfieminim.

6.Generaitoatepartiiileunuinumrntregn.Deexemplu:5=5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1

7.Omatricenxnareelemententregi1,2i3.nmatriceseintroducnelemente0.Determinaitoateposibilitiledeplasarealeacestora,tiindcpotfinlocuitenumaielemente1i2,icnupotaparemaimulteelementezeropeaceeailinie,coloansaudiagonal.

8.Unalfabetconinevvocaleicconsoane.Ssegenerezetoatecuvinteledelungimen,carenuconin3vocalesau3consoanealturate.Datelecititesunt:nlungimeacuvintelor,vnumruldevocale,voctabelulvocalelor,cnumrulconsoaneloriconstabelulconsoanelor.

9.SeconsiderobardelungimeMinrepereavandlungimile:a0

Ssegenerezetoatemoduriledistinctencarepoatefitiatbara,putndfolosiunreperdemaimulteori,astfelnctrestulrezultatdintieresafieminim.

12.AcoperireacuarceanodurilorunuigrafUngrafcucosturipoatefiacoperitcuarceprinmaimultiarbori(grafurifaracicluri).Unarboreacoperaungrafdacaatingetoatenodurilesalecuarcedingrafulinitial.

Indicaie:Pentruadeterminaarboreledecostminimmetodabacktrackinggenereaztoiarboriideacoperireposibili,calculeazcosturilelor(casumaacosturilorarcelor),lecomparireinearborelecucostminim.Osoluieaproblemeiesteunvectordearce(deperechidenoduri)ipoatefireduslaunvectordepredecesori.Inacestvectordentregix, x[k]reprezintpredecesorulnoduluik,deciarceledinarborelecutatsuntdeforma(x[i],i).Vectorulxareexactn1omponente.Condiiiledeacceptareauneivalori(ntre1sin)pentrux[k]sunt:x[k]diferitdeksexistearcntrex[k]sikarcul(x[k]k)sanufiedejainclusnarboreledecostminimExemplu:Grafulneorientatcu4nodurisicuarcele(1,2)=1,(1,4)=2,(2,3)=2,(2,4)=1,(3,4)=1.Pentruacestarboreexista8arborideacoperirediferiti,dintrecare3aucostul5,4aucostul4siunularecostul3.Arboreledecostminimeste12,24,34cu3arcedecost1fiecare.Vectorulsolutievafix[1]=2,x[2]=4,x[3]=4

13.Acoperireacunoduriaarcelorunuigraf.FiinddatungrafneorientatG=(V,M),sasedeterminenumarulminimdevrfuri(osubmultimeamultimiiV)careacoperatoatemuchiilegrafului(multimeaM).Indicatie:Vectorulsolutiecontinenumeredevrfurisiareolungimevariabila,maimicasauegalacun(nfiindnumaruldevrfuridingraf).Conditiadeacceptareaunuivrfnpozitiakdinvectorulsolutie:sanufifostselectatanterior(diferitdex[0],..x[k1])Saajunslaosolutieatuncicndaufostacoperitetoatemuchiiledingraf.Sevastabilimainticumsetineevidentamuchiiloracoperitesirespectivneacoperitencadingraf.Exempludedate:Grafulcu7nodurisicumuchiile:(1,2),(2,3),(3,4),(3,5),(4,5),(4,6),(5,6),(4,7)Solutiaoptimafoloseste3noduri:x[1]=2,x[2]=4,x[3]=5.

14.Pentrurepartizareacelornstudenti(npar)dintrogrupnsubgrupeformatedecte2studenisefoloseteuntablouP[n][n]ncareP[i][j]estepreferinastudentuluiipentrualucracustudentulj.Pondereaperechii(i,j)seexprimprinP[i][j]*P[j][i].Seceresamperechemstudeniiastfelnctsumaponderilorperechilorsfiemaximizat.

22