Îmbunătățește-ți Cunoștințele de Informatică, Dezvoltă-ți Abilitățile de Programare și Design Web!
Sa se verifice daca un graf este hamiltonian Fiind dat un graf neorientat memorat prin matricea de adiacenta sa se determine daca graful este Hamiltonian sau nu. Notiuni teoretice Definitie: Se numeste ciclu hamiltonian un ciclu elementar care trece prin toate varfurile grafului Definitie: Un graf care admite un ciclu hamiltonian se numeste graf hamiltonian … Read more
Subgraf Se citesc 2 grafuri neorientate, unul cu n noduri si m muchii, iar celalalt cu k varfuri si l muchii, ambele date prin vectorul muchiilor. Sa se determine daca al doilea graf este subgraf al primului. #include<fstream.h>fstream f(“date.in”,ios::in);fstream g(“date2.in”,ios::in); int a[100][100],b[100][100],n,m,k,l;void citire() {int x,y,i; f>>n>>m; for(i=1;i<=m;i++) {f>>x>>y; a[x][y]=1; a[y][z]=1; } g>>k>>l; for(i=1;i<=l;i++) {g>>x>>y; b[x][y]=1; … Read more
PERMUTARI ITERATIV metoda backtarcking PERMUTĂRI. Se citeşte un număr natural n. Să se genereze permutările mulţimi {1, 2, …, n} #include<iostream.h>#include<conio.h>#include<math.h>int st[20],n,k,p; void init(){st[k]=0;} int succesor(){if (st[k]<n){st[k]++;return 1;}else return 0;} int valid(){for(int i=1;i<k;i++)if(st[i]==st[k]) return 0;return 1;} int sol(){return (k==n);} void tipar(){for(int i=1;i<=n;i++) cout<<st[i];cout<<endl;} void bkt(){int as;k=1;init();while(k>0){do {} while ((as=succesor()) && !valid());if (as)if (sol()) tipar();else … Read more
#include<fstream.h>#include<conio.h>const float pinf=1.e20;float a[50][50];int n; void citire(char nume[20],float a[50][50],int& n){int i,j;float c;fstream f(nume,ios::in);f>>n;for(i=1;i<=n;i++) for(j=1;j<=n;j++) if (i==j) a[i][j]=0; else a[i][j]=pinf;while(f>>i>>j>>c) a[i][j]=c;f.close();} void drum(int i,int j){int k=1,gasit=0;while ((k<=n) && !gasit){ if ((i!=k) && (j!=k) && (a[i][j]==a[i][k]+a[k][j])) { drum(i,k);drum(k,j); gasit=1; } k++;}if (!gasit) cout<<j<<” “;} void tipar(int nodi,int nodf){if (a[nodi][nodf]<pinf){ cout<<“drumul de la “<<nodi<<” la “<<nodf<<” are lungimea … Read more
Graf eulerian #include<fstream.h>#include<conio.h>struct nod{int nd;nod *adr_urm;};int a[10][10],s[10],n;nod *lista, *indice; void citire(char graf[10],int a[10][10],int& n){int i,j;fstream f(graf,ios::in);f>>n;while (f>>i>>j) a[i][j]=a[j][i]=1;f.close();} void ciclu(nod* v){int nodul;nod *nod_baza,*nod_gasit,*nod_urm;nod_urm=v->adr_urm;nod_baza=v;do{ nodul=1;while (a[nod_baza->nd][nodul]==0) nodul++;a[nod_baza->nd][nodul]=0;a[nodul][nod_baza->nd]=0;nod_gasit=new nod;nod_gasit->nd=nodul;nod_gasit->adr_urm=0;nod_baza->adr_urm=nod_gasit;nod_baza=nod_gasit;}while (nod_gasit->nd!=v->nd);nod_baza->adr_urm=nod_urm;} int adauga(){int i,gasit=0;indice=lista;while(indice && !gasit){for(i=1;i<=n;i++)if (a[indice->nd][i]==1) gasit=1;if (!gasit) indice=indice->adr_urm;}if(indice){ciclu(indice);return 1;}else return 0;} int grade_pare(){int i=1,j,s,gasit=0;while ((i<=n) && !gasit ){s=0;for(j=1;j<=n;j++) s+=a[i][j];if (s%2) gasit=1;i++;}return !gasit;} void df(int nod){int k;s[nod]=1;for(k=1;k<=n;k++)if … Read more
#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[20],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[1]=1;s[1]=1;bf();for(int i=1;i<=sf;i++) cout<<c[i]<<” “;cout<<endl;getch();} {joscommentenable}
Problema comis-voiajorului Un comis voiajor trebuie să viziteze un număr n de oraşe. Iniţial, el se află într-unul dintre ele, notat 1. Comis voiajorul doreşte să nu treacă de două ori prin acelaşi oraş, iar la întoarcere să revină în oraşul din care a plecat. Cunoscând legăturile existente între oraşe, se cere să se tipărească … Read more
Problema colorarii hartilor Fiind data o harta cu n tari, se cer toate solutiile de colorare a hartii, utilizand cel mult patru culori, astfel incat doua tari ce au frontiera comuna sa fie colorate diferit. Este demonstrat faptul ca sunt suficiente numai patru culori pentru ca orice harta sa poata fi colorata. #include<iostream.h>#include<conio.h>#include<math.h>int st[20],n,k; … Read more
Problema damelor Considerandu-se o tabla de sah de dimansiune nXn, sa se determine toate modalitatile de amplasare a n regine pe tabla de sah astfel incat sa nu se atace doua cate doua(doua regine se ataca daca se afla pe aceeasi linie, coloana, sau diagonala). //problema damelor#include<iostream.h>#include<conio.h>#include<math.h>int st[20],n,k; void init(){st[k]=0;} int succesor(){if (st[k]<n) {st[k]++; … Read more
Scrieti un program care afiseaza pe ecran toate secventele de n litere (n numar natural par citit de la tastatura) din multimea {A,R,G,V), secvente care se pot construi respectand urmatoarele reguli: nu plasam doua litere identice una langa alta;trebuie sa utilizam exact n/2 litere R #include<iostream.h> #include<conio.h> #include<math.h> int st[20],n,k;char a[5]; void init() {st[k]=0;} int … Read more