diferenta>modul

Se citesc de la tastatura doua nr naturale n si v.Scrieti un program care afiseaza toate nr de la 1 la n in toate modurile posibile, astfel incat intre oricare doua numere afisate in pozitii invecinate, diferenta in modul sa fie mai mare decat valoarea data v.

Exemplu: n=4,v=1 solutiile vor fi 3 1 4 2 si 2 4 1 3

#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n,k,v;

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;
if((k>1) &&(abs(st[k]-st[k-1]<=v)) 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 {k++;init();}
else k–;
}
}

void main()
{cout<<“n=”;cin>>n;
cout<<“v=”;cin>>v;
bkt();
getch();
}

{joscommentenable}

JUCARII MOS CRACIUN

Copiii asteapta jucarii de la Mos Craciun. Scrieti un program care determina toate modurile diferite in care ei pot sa fie asezati in lista, astfel incat sa fie vizitati toti copiii si vizitele sa se faca in orinea descrescatoare a numarului de jucarii dorite de fiecare.Se citesc de la tastatura: n, numarul de copii, apoi numele si numarul de jucarii cerut de fiecare dintre cei n copii.Sa se scrie numele copiilor, in ordinea in care vor fi vizitati de Mos Craciun.

Exemplu: pentru datele de intrare: n=4
Dan 2
Cristina 4
Corina 6
Iulia 4
se scriu urmatoarele solutii:
Corina Iulia Cristina Dan
Corina Cristina Iulia Dan

#include<iostream.h>
struct copil{char nume[10]; int jucarii; };
struct copil v[10];
int st[20],n,k;
void init()
{
st[k]=0;
}
int succesor()
{if(st[k]<n)

{st[k]++;return 1;}

return 0;}

int valid()

{int i;

for(i=1;1<k;i++)

if(st[k]==st[i]) return 0;

for(i=1;i<k;i++)

if(v[st[k]].jucarii>v[st[i]].jucarii) return 0;

return 1;}

int solutie()

{int i;

for(i=1;i<=n;i++)

 cout<<v[st[i]].nume<<” “;

cout<<endl;}

void bkt()

{int as;k=1;

init();

while(k>0)

{

do {} while ((as=succesor() && (!valid()));

if (as)

if (solutie()) tipar();

else

{k++; init();}

else k–;

}

}

void main()

{cout<<“n=”;cin>>n;

for(int i=1;i<=n;i++)

{

cout<<“nume”<<i;cin>>v[i].nume;

cout<<“nr de jucarii pentru copilul “<<i;cin>>v[i].jucarii;

}

bkt();

}

COMBINARI ITERATIV

#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n,k,p;

void init()
{ if(k>1) st[k]=st[k-1];
else st[k]=0;
}

int succesor()
{if (st[k]<n-p+k)
{st[k]++;
return 1;
}
else return 0;}

int valid()
{
return 1;}

int sol()
{return (k==p);}

void tipar()
{for(int i=1;i<=p;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 {k++;init();}
else k–;
}
}

void main()
{cout<<“n=”;cin>>n;
cout<<“p=”;cin>>p;
bkt();
getch();
}

{joscommentenable}

 

 

ARANJAMENTE ITERATIV

#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==p);}

void tipar()
{for(int i=1;i<=p;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 {k++;init();}
else k–;
}
}

void main()
{cout<<“n=”;cin>>n;
cout<<“p=”;cin>>p;
bkt();
getch();
}

{joscommentenable}

 

fotbal

//un patron are o suma s;ce jucatori poate lua
#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n,p,s,a[20];

int valid(int p)
{int suma=0;
for(int i=1;i<p;i++)
if(st[i]>=st[p]) return 0;
for(i=1;i<=p;i++) suma=suma+a[st[i]];
if(suma>s) return 0;
return 1;}

int sol(int p)
{int suma=0;
for(int i=1;i<=p;i++) suma=suma+a[st[i]];
return (suma==s);}

void tipar(int p)
{for(int i=1;i<=p;i++) cout<<st[i];
cout<<endl;
}

void bkt(int p)
{
int val;
for(val=1;val<=n;val++)
{
st[p]=val;
if(valid(p)) if(sol(p))
tipar(p);
else bkt(p+1);
}
}

void main()
{cout<<“n=”;cin>>n;
cout<<“s=”;cin>>s;
for(int i=1;i<=n;i++)
{cout<<“a[“<<i<<“]=”;cin>>a[i];}

bkt(1);}

{joscommentenable}

cifre distincte pare alaturate

Backtracking cifre distincte pare alaturate

Folosind metoda backtracking, sa se afiseze toate nr din n cifre distincte a.i. sa nu fie 2 cifre pare alaturate

#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n,k,p;

int valid(int p)
{if(p==1 && st[p]==0) return 0;
for(int i=1;i<p;i++)
if(st[i]==st[p]) return 0;
if(p>1 && st[p]%2==0 && st[p-1]%2==0) return 0;
return 1;}

int sol(int p)
{return (p==n);}

void tipar(int p)
{for(int i=1;i<=p;i++) cout<<st[i];
cout<<endl;
}

void bkt(int p)
{
int val;
for(val=0;val<=9;val++)
{
st[p]=val;
if(valid(p)) if(sol(p))
tipar(p);
else bkt(p+1);
}
}

void main()
{cout<<“n=”;cin>>n;
bkt(1);
getch();
}

{joscommentenable}

cifre pare alaturate

Se citesc n cifre.Sa se afiseze toate nr formate cu acestea astfel incat sa nu existe doua cifre pare alaturate.

#include<iostream.h>
#include<conio.h>

int n,st[10],k,p;
int v[10];

int valid(int p)
{
if((p==1) && v[st[p]]==0) return 0;
if((p>1) && (v[st[p]]%2==0 && v[st[p-1]]%2==0)) return 0;

return 1;
}

int sol(int p)
{
return (n==p);
}

void tipar(int p)
{
for(int i=1;i<=p;i++)
cout<<v[st[i]];
cout<<endl;
}

void bkt(int p)
{

for(int val=1;val<=n;val++)
{st[p]=val;
if (valid(p))
if (sol(p)) tipar(p);
else bkt(p+1);
}}

void main()
{
int i;
cout<<“n=”;cin>>n;
for(i=1;i<=n;i++)
{cout<<“v[“<<i<<“]=”;cin>>v[i];}
bkt(1);
getch();
}

litere

Se citesc n litere.Sa se formeze toate cuvintele de cate p litere formate din cele n litere astfel incat aceeasi litera sa nu se afle pe 2 pozitii alaturate.

#include<iostream.h>
#include<conio.h>

int n,st[10],k,p;
char v[10];

int valid(int k)
{
if((k>1) && (st[k]==st[k-1])) return 0;
return 1;
}

int sol(int k)
{
return (k==p);
}

void tipar(int p)
{
for(int i=1;i<=p;i++)
cout<<v[st[i]];
cout<<endl;
}

void bkt(int k)
{

for(int val=1;val<=n;val++)
{st[k]=val;
if (valid(k))
if (sol(k)) tipar(p);
else bkt(k+1);
}}

void main()
{
int i;
cout<<“n=”;cin>>n;
cout<<“p=”;cin>>p;
for(i=1;i<=n;i++)
{cout<<“v[“<<i<<“]=”;cin>>v[i];}
bkt(1);
getch();
}

{joscommentenable}

nr negative alaturate

se citesc n nr.sa se afle toate modalitatile de afisare a nr a.i. 2 nr alaturate sa nu fie negative

#include<iostream.h>
int st[20],n,k,v[20];

void init()
{cout<<“n=”;cin>>n;}

int valid(int k)
{for(int i=1;i<k;i++)
if(st[i]==st[k]) return 0;
if((v[st[k]]<0) && (v[st[k-1]]<0)) return 0;
return 1;}

int sol(int k)
{return (k==n);}

void tipar(int k)
{for(int i=1;i<=k;i++) cout<<v[st[i]];
cout<<endl;
}

void bkt(int k)
{int val;
for(val=1;val<=n;val++)
{st[k]=val;
if(valid(k))
if (sol(k)) tipar(k);
else bkt(k+1);
}
}

void main()
{cout<<“n=”;cin>>n;
for(int i=1;i<=n;i++)cin>>v[i];
bkt(1);}

{joscommentenable}

combinari

//combinari
#include<iostream.h>
int st[20],n,k;

void init()
{
int i;
cout<<“n=”;cin>>n;
cout<<“k=”;cin>>k;
st[0]=0;
}

void tipar(int p)
{
int j;
for(j=1;j<=p;j++)
cout<<st[j]<<” “;
cout<<endl;
}

int solutie(int p)
{
return (p==k);
}

void bkt(int p)
{
int val;
for (val=st[p-1]+1;val<=n;val++)
{
st[p]=val;
if(solutie(p))
tipar(p);
else
bkt(p+1);
}
}

void main()
{
init();
bkt(1);
}

{joscommentenable}