Îmbunătățește-ți Cunoștințele de Informatică, Dezvoltă-ți Abilitățile de Programare și Design Web!
admin 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
Pe prima linie a fişierului “date.in” se află n numere naturale nenule,fiecare număr având cel mult 4 cifre. Să se formeze şi afişeze un număr din prima cifră a fiecărui element al şirului. #include<fstream.h>void main(){int nr=0,x;fstream f(“nr.txt”,ios::in);while(f>>x){while(x>10)x=x/10;nr=nr*10+x;}f.close();cout<<nr;}
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
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}
Functia Ackermann recursiv #include<iostream.h>long ack(unsigned x,unsigned y){if(x==0) return y+1;if(y==0) return ack(x-1,1);return ack(x-1,ack(x,y-1));} void main(){unsigned m,n;cout<<“m=”;cin>>m;cout<<“n=”;cin>>n;cout<<ack(m,n);}
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}