Îmbunătățește-ți Cunoștințele de Informatică, Dezvoltă-ți Abilitățile de Programare și Design Web!
Tocmai ai primit cadou de ziua ta un șir de numere naturale a[1], a[2], …, a[n]. Ca să te simți împlinit, trebuie să determini lungimea maximă a unei secvențe cu proprietatea că oricare două valori din secvență sunt distincte. Cerința Determină lungimea maximă cerută și anul viitor vei mai primi un șir! Date de intrare Programul citește de … Read more
Se citeste un arbore cu n varfuri dat prin vectorul muchiilor si apoi se citeste varful radacina. Sa se construiasca si sa se afiseze vectorul TATA. Vectorul de tati de declara astfel: T[i]=parintele(tata) nodului i. Pentru arborele din figura vectorul TATA este 0,1,2,1 si radacina este 1.Muchiile care se citesc sunt 1-2,2-1,1-4 #include<iostream.h>int n, r, … Read more
Se citeste un arbore cu n varfuri dat prin vectorul TATA. 1) Sa se afiseze muchiile arborelui 2) Sa se construiasca si sa se afiseze matricea de adiacenta a arborelui. Observatie: vectorul TATA precizeaza pentru fiecare varf i, nodul TATA[i] care reprezinta parintele sau Pentru arborele din imagine vectorul TATA este: 0,1,2,1. #include<iostream.h>int n, t[20], … Read more
Sa se determine un arbore partial de cost minim folosind algoritmul Kruskal Pentru memorarea muchiilor grafului si a costurilor acestora se defineste o structura de date cu trei campuri (nodurile muchiei si costul ei) pe care o numim muchie #include<iostream.h>#include<fstream.h>typedef struct{int u,v,c;} muchie;int l[30],n,m;muchie e[30];void citire(){int i;fstream f(“apm.txt”, ios::in);f>>n;f>>m;for(i=1;i<=m;i++)f>>e[i].u>>e[i].v>>e[i].c;f.close();} void main(){int k,ultim,i,u,v,ct,ind,ms,lu,lv;muchie aux;citire();for(i=1;i<=n;i++)l[i]=i;ultim=m;while(ultim>1){k=0;for(i=1;i<=ultim-1;i++)if(e[i].c>e[i+1].c){aux=e[i];e[i]=e[i+1];e[i+1]=aux;k=1;}ultim=k;}cout<<“APM contine muchiile:”<<endl;ct=0;ms=0;ind=0;while(ms<n-1){doind++;while(l[e[ind].u]==l[e[ind].v]);u=e[ind].u;lu=l[u];v=e[ind].v;lv=l[v];cout<<u<<” … Read more
Sa se parcurga in adancime DF un graf orientat. Graful este dat prin matricea de adiacenta. #include<fstream.h>#include<iostream.h>int v[20],a[20][20],n;void citire(){int i,j;fstream f(“matrice.txt”,ios::in);f>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++)f>>a[i][j];}void df(int nod){int k;cout<<nod<<” “;v[nod]=1;for(k=1;k<=n;k++)if((a[nod][k]==1) && (v[k]==0))df(k);}void main(){citire();df(1);} {joscommentenable}
Backtracking cifre pare crescatoare Folosind metoda backtracking, sa se scrie un program care genereaza toate nr din 3 cifre pare,cifrele strict in ordine crescatoare #include<iostream.h>#include<math.h>int st[20],i,p,v[]={0,2,4,6,8}; int valid(int p){for(i=1;i<p;i++)if(st[p]<=st[i])return 0;if(p==1 && st[p]==0)return 0;return 1;} int sol(int p){return (p==3);} void tipar(int p){ int i;for(i=1;i<=p;i++)cout<<st[i]<<” “;cout<<endl;} void bkt(int p){int val;for(val=0;val<=4;val++){st[p]=v[val];if(valid(p))if (sol(p))tipar(p);else bkt(p+1);}} void main(){bkt(1);}
Problema labirintului backtracking Se dă un labirint sub formă de matrice de m linii şi n coloane. Fiecare element al matricii reprezintă o cameră. Într-una din camerele labirintului se găseşte un om. Se cere să se afle toate soluţiile ca acel om să iasă din labirint, fără să treacă de două ori prin aceeaşi cameră.Se … Read more
Problema calului backtracking Fiind dată o tablă de şah de dimensiunea nxn şi un cal în colţul stânga sus al acesteia, se cere să se afişeze toate posibilităţile de mutare a calului astfel încât să treacă o singură dată prin fiecare pătrat al tablei. #include<iostream.h>#include<fstream.h>long st[100][100],vec[20][20],i,n; int valid(int k){if((st[k][1]<1)||(st[k][1]>n)||(st[k][2]<1)||(st[k][2]>n))return 0;for(i=1;i<k;i++)if((st[i][1]==st[k][1])&&(st[i][2]==st[k][2]))return 0;return 1;} int solutie(int k){return … Read more
Masa rotunda backtracking La o petrecere sunt invitate un numar de perechi, sot si sotie.Ei trebuie asezati in jurul unei mese rotunde astfel incat membrii aceleasi perechi sa nu fie unul langa altul,dar in acelasi timp fiecare femeie sa aiba vecini doi barbati si fiecare barbat sa aiba vecini doua femei. Femeile vor avea numere … Read more
Descompunerea in componente tare conexe a unui graf orientat, dat prin matricea de adiacenta Matricea de adiacenta se citeste dintr-un fisier text #include <fstream.h>int s[20],p[20],a[20][20],n,nr,i,j;void df1(int nod){int k;s[nod]=nr;for(k=1;k<=n;k++) if ((a[nod][k]==1) && (s[k]==0)) df1(k);}void df2(int nod){int k;p[nod]=nr;for(k=1;k<=n;k++) if((a[k][nod]==1) && (p[k]==0)) df2(k);}void main(){fstream f(“grafo.txt”,ios::in);f>>n;while(f>>i>>j) a[i][j]=1;f.close();nr=1;for (i=1;i<=n;i++) if (s[i]==0) { s[i]=nr; df1(i);df2(i); for(j=1;j<=n;j++) if (s[j]!=p[j]) s[j]=p[j]=0; nr++; }for(i=1;i<=n;i++){cout<<“componenta … Read more