Info.docx

Portofoliu la informatica

Divide et Impera In programare aceasta metoda se aplica astfel: se descompune problema data in 2 sau mai multe subprobleme de aceeasi natura. Aceastea pot fi de 2 feluri Elementare -cele elementare se rezolva direct Neelementare cele neelementare se descompun in continuare in alte problem elementare si neelementare. Procesul de descompunere se continua pana cand se obtin doar problem elementare. Solutia problemei initiale se obtine prin reconstituirea si reconbinarea solutiilor problemelor elementare in oridne inversa. Datorita acestui lucru algoritmul dei are un character recursive si sunt deobicei rapizi. PB:Fiind dat un vector Vn cu elemente nr intregi. Se cere sa se determine minimul din elementele vectorului, se va aplica dei si se va folosi o functie procedurala. {int min1,min2;m; if(p==q) min=v[p]; else {m=(p/q)/2; minim(p,q,min1);

minim(p,q,min1); if(min>min2) mini=min2; else mini=mini1;} } int main() {int i,mini; //citire n,v; minim(0,n-1,mini); cout<<mini; return 0;}

Cautarea binara Se aplica doar pe un vector ordonat . n=7 v=(-3,4,15,19,21,37,41) x=4 int caut_bin(int p,int q) { if(p>q) return -1; else { int m=(p+q)/2; if(x==v[m]) return 1; else if(x>n; for(i=0;i
cout<<"v["<>v[i]; } cout<<"x=";cin>>x; if(caut_bin(1,n-1)==1) cout<<"am gasit"; else cout<<"nu am gasit"; }

PB:Se considera un vector v ordonat crescator cu n elemente numere intregi si o valoare intreaga k. Se cere folosind DEI sa se determine daca k se gaseste in vector pe pozitia p. int v[50],k,i; int caut.bin(int p,int q) {int m,ok; if(p>q) return -1; else {int m=(p+q)/2; if(k==v[i]&&m==k) return 1; else if(p<m[i]) return caut.bin(p,m-1); else return caut.bin(m+1,q); } int main() {int n, ok=1; cin>>n; for(i=0;i>v[i] ; } cout<<”k=”; cin>>k; if(caut.bin(1,n-1)==ok) cout<<”este”; else cout<<”nu este”; }

}

Sortarea rapida Este cel mai rapid algoritm de sortare; Consta in impartirea repetata a vectorului dat in doi subvectori avand proprietatea ca orice element din subvectorul stang este mai mic decat orice element din subvectorul drept. Pentru a construi cei doi subvectori vom parcurge vectorul cu doi indici: a->parcurge de la stanga la dreapta pornind de la 0; b->parcurge de la dreapta la stanga pornind de la n-1; Vom executa in mod repetat urmatorii pasi pana cand b devine mai mic decat a; Pas1 cat timp v[a]= xb interschimbam cele doua valori si il marim pe a; Pas1 cat timp xa< xb avansam cu a spre dreapta. Cand xa>= xb interschimbam cele doua valori si micsoram b. #include #include #include<stdlib> int x[2000], n; int poz(int p,int u) {int piv, aux,k; piv=x[p]; while(p
{ if(x[p]>x[u]) { aux=x[p]; x[p]=x[u]; x[u]=aux; } if(x[p]==piv) u--; else p++; } k=p; return k; } void quick(int p, int u) {int k; if(p>n; for(i=1;i<=n;i++) {cout<<”x[„<>x[i]; } quick(1,n); for(i=1;i
Backtracking-prezentare generala Este o tehnica utilizata pt rezolvarea problemelor ce indeplinesc conditiile: -solutia lor poate fi pusa sub forma unui vector Iar elementele lor se considera a fi intr-o oridine bine stabilita. -nu se dispune de o alta metoda de rezolvare mai rapida a problemei. Elementele xi pot fi la randul lor vector, metoda backtracking are ca rezultat obtinerea tuturor solutiilor problemei. In cazul in care se cere o se ingura solutie pt problema se poate face oprirea fortata a algoritmului cand a fost gasita prima solutie. Deoarece intr-un algoritm backtracking ne int toate solutiile problemei vom precede astfel: -prentru a obtine fiecare sol finala se compileaza un vector stiva pas cu pas, nivel cu nivel trecand astfel prin niste solutii partiale. -atat solutiile partiale cat si cele finale pt a putea fi luate in considerare trebuie sa indeplineasca anumite conditii specific fiecarei problem numite conditii de validare sau continuare. O solutie ce indeplineste aceste conditii devine solutie valida. Practic senta metodei consta in evitarea generarii tuturor succesiunilor posibile care abia apoi sa fie varificate si

pastrate sau response dupa caz. Acesta alternative de rezolvare ar conduce la consum de timp. Metoda backtracking consta in renuntarea cat mai devreme cu putinta la generarea unor succesiuni sortite esecului. -Algoritmul general al metodei backtracking. Presupunem ca s-au determinat valorile st1,st2…st[k-1] si vrem sad et valorile pt componenta st[k] Pas1: Pentru componenta st[k] la inceput nu s-a testat nicio valoare Pas2: Se verifica daca exista valori netestate pt st[k] a)in caz afirmativ se trece la pas 3 b)altfel se revine la component anterioara st[k-1] reluandu-se pasul 2 pt component k-1 Pas3: Se allege prima valoare din cele netestate inca pentru st[k] Pas4:Se verifica daca combinatia partial obtinuta pt st[k] indeplineste condiile de validare a)daca valoarea aleasa este buna se trece la pasul 5 b)altfel se ramane pe aceeasi pozitie k si se reia pasul 2 Pas5: Se verifica daca s-a obtinut o solutie finala a)in caz afirmativ se oafiseaza aceasta solutie si se ramane la acelasi nivel k reluand pasul 2 b)in caz contrar se reia algoritmul pt urmatoarea component aflata pe pozitia k+1

!Obs: Inainte de implementarea unui algoritm backtracking trebuie sa stabilim: -cate elem are vectorul solutie -ce valoare poate avea un element al vectorului solutie -conditiile de validare -conditie de solutie finala -Implementarea interativa a metodei backtracking Pentru implementarea metodei vom folosi un vector stiva al carei varf il notam cu k typedef int stiva[100] stiva st; -vom folosii variabila n care indica lungimea vectorului stiva deobicei -variabila ev(e valid) si care va avea valoarea -1 daca combinatia partial indeplineste conditiile de validare -0 in caz contrar -variabila as(are successor) care va avea valoarea -1 daca mai exista valoari netestate inca pt nivelul k si vom fol urmatorul subprogram: ->init( ) prin care vom initialize vf. Stivei -functia operant successor are rolul de a verifica daca mai exista valori netestate inca. -Functia operant valid -verifica daca valoarea elementului st[k] indeplineste conditiile de validare.

-functia returneaza val 1 sau 0 variabilei ev -fucntia operant solutie verifica daca s-a ajuns la sol finala -functia procedural tipar afiseaza Solutia finala. Pt a descrie strategia generala backtracking se foloseste un subprogram care in general consta cam acelasi pt toate problemele. void bk() {k=1;init();//se pleaca de pe nivelul 1 initializandu-l while(k>0) //cat timp exista elemente in stiva { as=1;ev=0; //presupunem ca am successor si acesta nu evalid while(as && !ev) //caut in mod repetat un successor valid {as=successor(); if(as) ev=valid(); } if(as) //daca avem successor valid if(solutie()) tipar(); else {k=k+1; init(); } else k=k-1; } typedef int stiva[100]; stiva st; int n,k,p; void init() {st[k]=0;} int succesor() {

if(st[k]0) { as=1; ev=0;

while(as && !ev) { as=succesor(); if(as) ev=valid(); if(as) if(solutie( )) tipar(); else { k=k+1; init();} else k=k-1; } }} int main() {cout<<"n=";cin>>n; cout<<"p=";cin>>p; bt(); return 0; }

Problema colorarii tarilor Fiind data o harta cu n tari se cer toate solutiile de colorare a hartii astfel incat 2 tari cu frontier comuna sa fie colorate diferit

#include Using namespace std; int n,k,ev,as, a[6][6]; typedef int stiva[100]; stiva st; void init() { st[k]=0; } int succesor() {if(st[k]
return 1; } else return 0; } int valid() { for(int i=1;i0) { as=1; ev=0; while(as&&!ev) {as=succesor(); if(as)\ ev=valid(); } if(as) if(solutie()) tipar(); else {k=k+1; init(); } Else k=k-1; } }

int main() { cout<<” n=”; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) {cout<<”a[„<<<j<<”]= „; cin>>a[i][j]; a[j][i]=a[i][j]; } bkt(); return 0; } Problema celor n dame Fiind data o table de sah de dimensiune n se cer toate solutiile de aranjare a n dame astfel incat 2 dame sa nu se atace reciproc. Conditia ca 2 dame sa nu fie asezate pe aceeasi linie este respectata prin insasi respectarea algoritmului backtracking Conditia ca doua dame sa nu fie asezate pe aceeasi coloana este: Conditia ca 2 dame sa nu fie asezsate pe aceeasi diagonal este: typedef int stiva[100]; stiva st; int n,k,p,es,ev; void init() {st[k]=0;} int succesor() { if(st[k]
int valid() { int i; for(i=1;i0) { as=1; ev=0; while(as && !ev) { as=succesor(); if(as) ev=valid(); if(as) if(solutie()) tipar(); else { k=k+1;

init(); } else k=k-1; } } } int main() {cin>>n;cin>>p; bt(); return 0;}

Problema platii unei sume S utilizand n tipur de monede Se dau n tipuri de monede avand valorile v1,v2...vn. Sa se gaseasca toate modalitatile de plata a sumei S utilizand aceste monede. int st, maxi[100],S0,S,as,ev,k,v[100]; void init() { st[k]=-1; } int succseor { if(st[k]<maxi[k]) { st[k]=st[k]+1; return 1; } else return 0; } int valid() { S0=0 for( int i=1;iS) return 0; else

return 1; } void tipar() { for(int i=;i<=k;i++) cout<<st[k]<< ‚ ‚; cout<<endl; } void bkt() { k=1; init(); while(k>0) { as=1; ev=0; while(as&&!ev) { as=succesor(); if(as) ev=valid(); } if(as) if(solutie()) tipar(); else k=k-1; } } int main() {cout<<”n=”; cin>>n; for(i=1;i>v[i]; for(i=1;i<=n;i++) cout<<”S=”; cin>>S; bkt(); maxi[i]=S/v[i]; return 0; }

Cinci certareti

Un grup de n persoane n<=10 sunt asezate pe un rand de scaune in ordinea sosirii. Dupa un timp, intre oricare doua persoane vecine s-au ivit conflicte. Se cer toate posibilitatile de reasezare a persoanelor astfel incat intre oricare doua persoane aflate la inceut in conflict sa stea una saucel mult doua persoane. typedef int stiva [100]; stiva st; int n,k,as,ev; void init() { st[k]=0}; int succesor() {if(st[k]0)

{ as=1; ev=0; while(as&&!ev) {as=succesor(); if(as) ev=vald(); } if(as) if(solutie()) tipar(); else {k=k+1; init(); } else k=k-1; } } int main() {cout<<”n=”;cin>>n; bkt(); return 0; } -Sa se genereze toate sirurile formate din n cifre, fiecare sir generat avand proprietatile: -contine numai cifre din multimea {1,2,3,4} -oricare 2 cifre alaturate sunt fie ambele pare, fie impare; void bkt() #include Using namespace std; int n,k,ev,as; typedef int stiva[100]; stiva st; void init() { st[k]=0; }

int succesor() {if(st[k]0) { as=1; ev=0; while(as&&!ev) {as=succesor(); if(as) ev=valid(); } if(as) if(solutie()) tipar(); else

{k=k+1; init();} Else k=k-1; } } int main() { cout<<” n=”;cin>>n bkt() ; return 0; }

Metoda greedy Se aplica pentru problemele in care dandu-se o multime finita A trebuie determinata o multime S inclusa in multimea A, S fiind formata din elementele multimii A care indeplinesc conditiile impuse de problema. -metoda furnizeaza o singura solutie reprezentata prin elementele multimii S; Spre deosebire de backtrackig, metoda greedy nu gaseste decat o singura solutie si in general aceasta solutie este solutia optima; Spre deosebire de backtracking la fiecare pas vom alege un candidat optim, element al multimii A, pentru al introduce in solutia S si aceasta alegere este irevocabila; Pasii metodei sunt urmatorii: 1.Se initializeaza multimea S cu multimea vida; 2.Cat timp S nu este solutie a problemei si A este dferta de multimea vida vom executa: 2.1.Se alege dn multimea A elementul a care este candidatul oprim al solutiei; 2.2.Se elimina elementul a din multimea A; 2.3.Daca elementul a poate fi element al solutiei S atunci se adauga in multimea S si se revine la pas 2;

3.Daca multimea S este solutie a problemei atunci se afiseaza solutia, altfel se afiseaza mesaj de eroare; Metoda greedy este o metoda de rezolvare rapida a problemei, avand un timp de calcul polinomial, spre deosebire de metoda backtracking care are un timp de calcul exponential; Timpul de calcul al metodei il putem determina presupunand ca daca multimea A ar avea n elemente si solutia S in cazul cel mai defavorabil aravea tot n elemente. Se vor face n alegeri; la fiecare alegere se fac n teste de aici rezultand un algoritm cu timpul polinomial O(n2). In unele situatii este necesar ca inaintea aplicarii metodei sa sortam elementele multimii A, iar sortarea necesita un timp minim O(n*log2n) acest timp se aduna la cel polinomial neinfluentand timpul final. Problema spectacolelor: Intr-o sala, intr-o zi, trebuie planificare n spectacole; pentru fiecare spectacol se cunoaste in intervalul in care se defasoara(ora inceput/ora sfarsit). Se cere sa se realizeze o planficare optima a spectacolelor astfel incat sala sa fie ocupatala maxim. In rezolvarea problemei vom folosi un struct care va retine ora de inceput, ora de sfarsit si numarul de ordine initial al spectacolelor. Vom sorta spectacolele dupa ora terminarii lor si vom include solutie prmul spectacol care va fi cel care se termina cel mai repede. Din restul spectacolelor ramase il vom alege pe primul care indeplineste conditia ca incepe dupa ce se termina spectacolul pus anterior in solutie #include using namespace std; struct spectacol {int x,y,k; };

spectacol a[20]; int n,m,s[20]; void citire() { cout<<” nr spectacole:”; cin>>n for(int i=1;i<=n;i++) {cout<<” start spectacol” <<<” : „; cin>>a[i].x; cout<<”final spectacol”<<<”:”; cin>>a[i].y;} a[i].k=i; } void ordonare() { spectacol.aux; for(int i=1;ia[j].y) { aux=a[i]; a[i]=a[j]; a[j]=aux; } } void greedy(); {s[1]=1; int j=1; for(int i=2;i<=n;i++) if(a[s[i]].x>=a[s[j]].y) { ++j; s[j]=i; } m=j; } void afis() { cout<<”ordinea pectacolelor va fi”<<endl; cout<<”spectacol”<
Problema continua a rucsacului O persoana are un rucsac cu care poate transporta o greutate G, persoana are la dispozitie n obiecte si pentru fiecare obiect cunoaste greutatea si castigul ce se obtine in urma transportului obiectului la destinatie Pentru a obtine o icarcare mai eficienta al rucsacului se precizeaza ca un obiect poate fi taiat. Sa se determine Solutia optima de incarcare a rucsacului astfel incat sa se obtina castigul maxim. #include using namespace std; struct obiect {int k; float g,c,i; }; obiect a[20]; int n,m,s[20]; float G,Gr,x[20]; void citire() { cout<<”G ce poate fi transportata:”; cin>>G; cout<<”nr de ob:”;cin>>n; for(int i=1;i<=n;i++) {cout<<”g obiect” <<<” : „; cin>>a[i].g; cout<<”profit pt ob.”<<<”:”; cin>>a[i].c; a[i].e=a[i].c/a[i].g; a[i].k=i;} } void ordonare()

{inti,j; for(int i=1;i<=n;i++) for(j=i+1;j<=n;j++) if(a[i].e>a[j].e) { aux=a[i]; a[i]=a[j]; a[j]=aux; } } void greedy(); {int i,j=1; Gr=G; for(int i=1;i<=n && Gr!=0;i++) if(Gr>a[i].g) { ++j; s[j]=i; } x[j]=1; Gr=Gr-a[i].g; } else {++j; S[j]=I; x[j]=Gr/a[i].y; } m=j;} void afis() { for (int i=1;i
greedy(); afis(); return 0; } Programarea dinamica Alaturi de greedy programarea dinamica este o tehnica ce conduce de cele mai multe ori la un timp de calcul polynomial Mai mult ea furnizeaza intodeauna solutia optima. Din nefericire programarea dinamica nu se poate aplica tuturor problemelor ci doar acelora care indeplinesc anumite conditii. Solutia optima se allege dintr-o multime de solutii fiecarei solutii putand sa i se asocieze o valoare, alegerea solutiei optime inseamna alegerea solutiei care are valoarea optima minima sau maxima. Problema data poate fi descompusa in subprobleme similar cu problema initial ace respecta principiul optimalitatii adica solutia problemei este optima daca ea contine solutiile optime ale subproblemelor. Subproblemele in care se descompune problema nu sunt independente. -exista o multime finite A din care se poate allege un element xi al solutiei -fiecare etapa de determinare al unui element xi al solutiei se bazeaza pe rezultatele etapelor in care s au determinat elementele anterioare ale solutiei (programare dinamica inainte sau inapoi) - numarul de posibilitati de a alege un elemnt xi al solutiei se reduce din cauza cerintelor de optimizare si a restrictiilor inpuse solutiei. Algoritmul programarii dinamice are complexitatea 0(n*m) unde n reprezinta nr subproblemelor in care este descompusa

problema initiala iar pt fiecare subproblema se calculeaza cele m elemente ale valorii associate solutiei etapele de rezolvare ale unei problem cu tehnica programarii dinamicii sunt urmatoarele: Pas1:Se demostreaza ca problema are o strucutra optima din reducere la absurd Pas2:Se carac. Structura unei solutii optime adica se realizeaza descompunerea problemei in subproblema Pas3:Se defineste recursive valoarea solutiei optime Pas4: Se calculeaza valoarea solutiei optime intr-o maniera de jos in sus Pas5:Se construieste solutia optima din informatiile optinute prin calcularea valorii solutiei optime Problema triunghiului Se considera un triunghi de numere naturate format din n linii.Prima linie contine un nr, a doua 2 numere…, ultima linie n numere cu ajutorul acestui triunghi se pot forma sume de nr in felul urmator: -se porneste cu numarul din linia1 -succesorul unui nr se afla pe linia urmatoare plasat sub el sau pe diagonal la dreapta. Care este cea mai mare suma ce se poate forma astfel in care sunt numerele care o alcatuiesc? int main () {int i,j; cout<<”n=”;cin rel="nofollow">>n; for(i=1;i<=n;i++) for(j=i;j<=i;j++) {cout<<”t[“<<<”][“<<j<<”]=”; cin>>t[i][j];}

for(j=i;j<=n;j++) c[n][j]=t[n][j]; for(i=n-1;i>=1;i--) for(j=1;j<=i;j++) if(c[i+1][j]
Tipuri de date Pointer Pointerul este o variabila care memoreaza adresa unei altei variabile Un pointer se asociaza intodeauna unui tip de baza (int,char,float etc) numit tip de baza. Declararea unui pointer se face cu sintaxa: tip_data *nume_pointer; Unde tipul pointerului este tipul de baza a datei stocate la adresa memorata de pointer.

“ * ” se numeste operator de referinta “nume_pointer” este indentificatorul variabilei de tip pointer ex: int *a , float *r , char *q… etc Fiind o variabila si pointerul este caracterizat de aceleasi attribute ca orice variabila: nume, valori si tip Valoarea unui pointer este adresa variabilei de referinta de catre pointer Atribuirea de adrese este facuta de catre sistemul de recuperare in functie de spatiei memoriei libere. Lungimea adica dimensiunea zonei de memorie alocata unui pointer depinde de mai multi factori printer care intervin compilatorul. Punem determina dimensiunea zonei de momorie alocata unui pointer folosind operatorul size-off int *p cout<<sizeoff(p); Pointerul 0 are val 0 si el nu indicate nicio adresa. Spunem ca este un pointer in vant. In loc de valoarea 0 putem folosii constanta simbolica NULL. Operatorii specifici pt variabilele de tip pointer -Operatorul de adresare “ & “, se aplica pe o variabila de memories au pe un element de tablou si furnizeaza adresa variabilei de memorie, respective adresa elementelor de tablou.

Nu se poate aplica pe o expresie pe o constanta sau pe o variabila de tip pointer. -Operatorul de redirectare se aplica pe o variabila de tip pointer si furnizeza fal variabilei de mem a carei adresa este i indicate de catre pointer. Putem spune ca voim putea manipula informatia de adresa prin operatorul de redirectare. ex: int a=10,*p=&a; cout<
*p=1;

//*p=*p+1

Cout<
1)Se citesc valoarea a doua variabile a caror adrese sunt referite de pointerii p,q.Sa se calculeze suma si produsul celor 2 variabile. int *p,*q,S,p1,a,b;

p=&a; q=&b; cout<<”a=”;cin rel="nofollow">>*p; cout<<”b=”;cin>>*q; S=(*p)+(*q); P1=(*p)*(*q); cout<<”S=”<<S<<endl; cout<<”P=”<>*p; c=&p; ogl=&x; *ogl=a; while(c) {*ogl=(*ogl)*10+c%10; c/=10;} if((*p)==(*ogl) cout<<”Da”; else cout<<”Nu”;}

3)Un nr nat n, apoi se citesc pe rand n, numere naturale.Se cere sa se afiseze acele valori care se divid cu suma cifrelor lor.Se vor folosi pointeri {int i,n,x,*p=&n,*q=&x,s,c; cout<<”n=”;cin>>*p; for(i=1;i<=*p;i++) {cout<<”q=”;cin>>*q; c=*q; s=0; while(c) {s=s+c%10; c/=10; } if(*q%s==0) cout<<*q; } return 0;} 4)Din fisierul date.in se citesc valori nr natural in fisier fiind cel mult 1 milion astfel valori, Sa se afiseze nr perfecte din fisier sis a se determine si nr acestora. int x,sd,*p=&x,k=0,d,k=0; ifstream f(“date.in”); while(f>>x)

{sd=1; for(d=2;d<=(*p)/2;d++) if(*p%d==0) sd=sd+d; if(*p==sd) {cout<<*p<<” “<<endl; K++;}} cout<
Alocarea dinamica a memoriei Pana in present s-a folosit alocarea statica a memoriei. Alocarea statica memoriei se face in timpul compilarii in functie de modul in care a fost declarata data sau structura de date iar in timpul executiei programului nu mai poate fi modificat. Variabilele care folosesc alocarea statica a memoriei se numesc variabile statice iar sistemul de operare le aloca spatiu in segmental de date sau in stiva sistemului in functie de modul in care au fost declarate.

Alocarea statica a memoriei se numesc variabile statice iar sistemul de operare le aloca spatiu in segmentul de date sau in stiva sistemului in functie de modul in care au fost declarate. Alocarea statica a memoriei prezinta dezavantajul ca se poate depasii spatiul alocat unei variabileAceste dezavantaje dispar in cazul alocarii dinamici a memoriei.Variabilele care folosesc alocarea dinamica se numesc variabile dinamice, iar spatiul de memorie pentru ele va fi in zona de adrese libere numa si heap Pasii pt alocare dinamica a memoriei respectiv pt eliberarea memoriei sunt urmatorii: Pas 1: Se declara o variabila de tip * catre tipul de data al variabilei tip_baza *nume_pointer Pas 2: Se face cerere in momentul in care avem probleme de variabila dinamica respectiva. Pentru a i se aloca spatiul de memorie in zona Heap, aceasta cerere se face cu “new” in urmatoarea sintaxa: nume_pointer=new tip+baza; Pas 3: Dupa utilizarea variabilei se poate elibera spatiul de memorie Heap folosind sintaxa: delete nume_pointer Concluzie: In cazul utilizarii alocarii dinamice unei variabile dinamice ii se aloca spatiul in memoria Heap doar n momentul in

care avem aceeasi variabila in program, si se elibereaza in momentul in care mai avem nevoie de variabila in program. 1)Sa se calculeze suma si produsul a doua valori folosind

alocarea dinamica {int *p,*q; p=new int; q=new int; cout<<”prima val:”; cin>>*p; cout<<”a doua valoare:” cin>>*q; int s s=new int; *s=*p+*q; cout<<”s=”<<*s<<endl; delete s; int *pr; pr=new int; *pr=(*p)*(*q); cout<<”pr=”<<*pr; delete pr; }

2)Se citeste un nr natural n, apoi se citesc cele n elemente nr intregi ale unui vector. Se cere sa se afiseze vectorul si sa se determine nr de elemente pozitive din vectori. Se vor folosi pointeri {int *n,*p,*q,*nr; n=new int; cout<<”n=”;cin>>*n; p=new int[*n]; for(q=p;q>*q; for(q=p;q0) (*nr)++; cout<<”nr=”;<
Liste dublu inlantuite Este o structura de date in care fiecare nod cu exceptia primului si ultimului pe langa informatia utila retine adresa nodului precedent si adresa nodului urmator.Primul nod are precedentul NULL iar ultimul nod are urmatorul NULL struct nod {int inf; nod *urm,*prec;}; Creearea listei- trebuie sa parcurgem 2 etape a)in lista nu exista niciun nod  alocam memorie pt prim  citim inf  urmatorul lui prim este NULL  precedentul lui prim este NULL  fiind singurul nod este si ultim b)in lista exista cel putin un nod  alocam memorie pt noul nod, *c  citim informatia  urmatorul lui c este NULL  precedentul lui c este ultim  urmatorul lui ultim este c  ultim trece prin c

Parcurgerea LDI a)parcurgerea de la stg la dreapta Ramane indentica cu parcurgerea LSI b)parcurgere de la dr la stanga Se pleaca cu o copie de pe ultimul nod al listei Cat timp nu am ajuns la sf listei:  afisam inf din nodul curent  copia se muta pe modul precedent struct nod {int inf; nod *urm,prec; } nod *prim,*ultim; void adaug(nod *&prim, nod *ultim,int val) {if (prim!=NULL) {prim=new nod; prim->inf=val; prim->urm=NULL; prim->prec=NULL; ultim=prim; } else {nod *c;

c=new nod; c->inf=val; c->urm=NULL: c->prec=ultim; ultim->urm=c; ultim=c; } void parcurg_dr_st(nod *ultim) { nod *c=ultim; While(c!=NULL) {cout<int<<” “; C=c->prec; } parcurgere st_dr(nod *prim) {nod *c; c=prim; while(c!=NULL) {cout<inf<<” “; c=c->urm;

}}

int main() {int x,n; cout<<”cate noduri:”;cin>>n; {cout<<”inf:”<<<” ;”;

cin>>i; adaug(prim,ultim,x); } cout<<”st->dr:”; parcurgere_st_dr(prim); cout<<endl<<”dr->st”; parcurgere_dr_st(ultim); } Stergere Void stergere(nod *prim, nod *ultim, int val) {if(prim->inf==val) {nod *aux=prim; prim=aux->urm; prim->prec=NULL; delete aux;} else if(ultim->if==val) {nod (aux=ultim; ultim=aux->prec; ultim->urm=NULL; delete aux;} else {nod *c=prim; while(c!=NULL) {if(c->inf==val) {nod *aux=c; c->prec->urm=aux->urm; c=aux->prec; delete aux;

} c=c->urm; }}} Cautare int caut(nod *prim, int y) {nod *c; c=prim; int y=0; while(g==0 && C!=NULL) if(c->inf==y) y=1; else c=c->urm; return y; }