Îmbunătățește-ți Cunoștințele de Informatică, Dezvoltă-ți Abilitățile de Programare și Design Web!
Descompunerea in componente conexe a unui graf neorientat, dat prin matricea de adiacenta #include<fstream.h>int s[20],a[20][20],n,i,j,k; void df(int nod){int k;cout<<nod<<” “;s[nod]=1;for(k=1;k<=n;k++) if((a[nod][k]=1) && (s[k]==0)) df(k);} void main(){fstream f(“graf.txt”,ios::in);f>>n;while(f>>i>>j) a[i][j]=1;f.close();k=1;for(i=1;i<=n;i++) if(s[i]==0) { cout<<“componenta “<<k<<endl; df(i); cout<<endl; k++; }} {joscommentenable}
Suma cifrelor s backtracking Sa se afiseze toat numerele formate din cifre distincte cu proprietatea ca suma cifrelor este s, unde s se citeste de la tastatura. Sa se folosesca metoda backtracking. #include<iostream.h>#include<conio.h>int st[20],n,k,s,c; void init(int k){st[k]=-1;} int succesor(int k){if((st[k]<9)&&(st[k]<s)) {st[k]++; return 1; }else return 0;} int valid(int k){int suma=0;for(int i=1;i<k;i++) if(st[k]==st[i]) return 0;for(i=1;i<=k;i++) suma=suma+st[i];if(suma>s) … Read more
Numarul de nivele ale unui arbore #include<iostream.h>#include<conio.h>#include<stdio.h>struct nod{int nr;nod* st,*dr;};nod *c;int coada[20],s[20],i,sf;nod *r[20]; nod *arb(){int n;nod *c;cout<<“n=”;cin>>n;if(n){c=new nod;c->nr=n;c->st=arb();c->dr=arb();return c;}else return 0;} int max(int x,int y){if (x>y) return x;else return y;} int h(nod *r){if (r==0) return 0;else return 1+max(h(r->st),h(r->dr));} int h1(nod *r){if(r==0) return 0;else return 1+h1(r->st);} int h2(nod *r){if(r==0) return 0;else return 1+h2(r->dr);} void main(){int … Read more
Graf orientat tare conex #include<fstream.h>#include<conio.h>int s[50],a[50][50],n,suc[50],pred[50],i,j;void citire(char fis[20],int a[50][50],int&n){ fstream f(fis,ios::in); int i,j; f>>n; while(f>>i>>j) a[i][j]=1; f.close();} void df1 (int nod){ int k; suc[nod]=i; for (k=1;k<=n;k++) if ((a[nod][k]==1) && (suc[k]==0)) df1(k);}void df2(int nod){ int k; pred[nod]=i; for (k=1;k<=n;k++) if((a[k][nod]==1)&&(pred[k]==0)) df2(k);}void main(){citire(“fis.txt”,a,n);cout<<“nodul de pornire:”;cin>>i;suc[i]=pred[i]=i;df1(i);df2(i);for(j=1;j<=n;j++)if((suc[j]==pred[j])&&(suc[j]==i))cout<<j<<” “;getch();} {joscommentenable}
Sa se parcurga un graf graf in latime (BF) #include<fstream.h>#include<conio.h>struct nod{int inf;nod* adr;}; nod* l[20];int c[20],s[20],i,sf,n; void citire(char fisier[10],nod*l[20],int& n){nod* p;int i,j;fstream f(fisier,ios::in);f>>n;for(i=1;i<=n;i++) l[i]=0;while(f>>i>>j){p=new nod;p->adr=l[i];p->inf=j;l[i]=p;}f.close();} void bf(){nod* p;if(i<=sf){p=l[c[i]];while(p){if(s[p->inf]==0){sf++;c[sf]=p->inf;s[p->inf]=1;}p=p->adr;}i++;bf();}} void main(){citire(“graf.txt”,l,n);i=1;sf=1;c[i]=1;s[1]=1;bf();for(int i=1;i<=sf;i++) cout<<c[i]<<” “;cout<<endl;getch();} {joscommentenable}
Codul pruffer #include<iostream.h>#include<conio.h>int t[50],pt[50],i,j,k,n,gasit; void main(){ cout<<“n=”;cin>>n; for(i=1;i<=n-2;i++) {cout<<“pt[“<<i<<“]=”; cin>>pt[i]; }pt[n-1]=n;for(i=1;i<=n-1;i++) {k=1; do {gasit=0; for(j=1;j<=i-1;j++) if(t[j]==k) gasit=1; if(!gasit) for(j=i;j<=n-1;j++) if(pt[j]==k) gasit=1; if(gasit) k++; } while(gasit); t[i]=k;}for(i=1;i<=n-1;i++) cout<<t[i]<<” “;cout<<endl;getch();}
Arborescenta #include<fstream.h>#include<conio.h>int a[20][20],b[20][20],s[20],gasit,ok,radacina,n,i,j,suma,r; void citire(char nume[10],int a[20][20],int& n){ fstream f(nume,ios::in); int i,j; f>>n; while (f>>i>>j) a[i][j]=1; f.close();} void df(int nod){ int k;s[nod]=1; for(k=1;k<=n;k++) if(a[nod][k]==1 || a[k][nod]==1) {a[k][nod]=a[nod][k]=0; if (s[k]==0) df(k); else gasit=1; }} void df1(int nod){ int k;s[nod]=1; for(k=1;k<=n;k++) if (a[nod][k]==1 && s[k]==0) df1(k);} void main(){ citire(“graf.txt”,a,n);cout<<“n->”<<n<<endl; for(i=1;i<=n;i++) for(j=1;j<=n;j++) b[i][j]=a[i][j]; df(1); for(i=1;i<=n;i++) suma+=s[i]; if(suma!=n) cout<<“nu … Read more
Arbore partial de cost minim #include<fstream.h>#include<iostream.h>float a[20][20],min,cost;int s[20],t[20],n,i,j,k,v; void citire(char nume[20],float a[20][20],int &n){int i,j;float c;fstream f(nume,ios::in);f>>n;for(i=1;i<=n;i++) a[i][i]=0;for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=100;while(f>>i>>j>>c) a[i][j]=a[j][i]=c;f.close();} void main(){cost=0;citire(“graf2”,a,n);cout<<n<<endl;cout<<“nodul de pornire:”;cin>>v;for(i=1;i<=n;i++) if(i==v) s[i]=0; else s[i]=v; for(k=1;k<=n-1;k++){min=100;for(i=1;i<=n;i++) if(s[i]) if(a[s[i]][i]<min) {min=a[s[i]][i]; j=i; }t[j]=s[j];cost+=a[s[j]][j];s[j]=0;for(i=1;i<=n;i++) if(s[i] && a[i][s[i]]>a[j][i]) s[i]=j;}cout<<“cost=”<<cost<<endl;for(i=1;i<=n;i++) cout<<t[i]<<” “<<endl;}
Arbori de cautare #include<iostream.h> #include<conio.h> struct nod {int nr; nod *as,*ad; }; nod *v,*man; int k; void inserare(nod*& c,int k) { if(c) if(c->nr==k) cout<<“nr inserat”<<endl; else if(c->nr<k) inserare(c->ad,k); else inserare(c->as,k); else {c=new nod;c->as=c->ad=0; c->nr=k;} } void parcurg(nod* c) {if(c) {parcurg(c->as); cout<<c->nr<<endl; parcurg(c->ad); } } void main() {v=0; do{ cout<<“k=”;cin>>k; inserare(v,k);} while(k!=0); parcurg(v); getch(); }
Sa se parcurga un arbore binar #include<iostream.h>#include<conio.h>struct nod{int nr;nod* st,*dr;};nod *c;int nrst,nrdr; void svd(nod *c){if(c){svd(c->st);cout<<c->nr;svd(c->dr);}} void vsd(nod *c){if(c){cout<<c->nr;vsd(c->st);vsd(c->dr);}} void sdv(nod *c){if(c){sdv(c->st);sdv(c->dr);cout<<c->nr;}} nod *arb(){int n;nod *c;cout<<“n=”;cin>>n;if(n){c=new nod;c->nr=n;c->st=arb();c->dr=arb();return c;}else return 0;} void main(){clrscr();c=arb();svd(c);cout<<endl;vsd(c);cout<<endl;sdv(c);cout<<endl;getch();}