Backtracking - descompunere suma - toate combinatiile

//Descompunere suma - toate combinatiile

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

# define MAX 10

int sum,cont;
int sol[MAX];

void final(int n)
{
int i;
for(i=0;i<n;i++)
 cout<<sol[i]<<" ";
cout<<"\n";
cont++;
}

int verif(int j, int s)
{
if(j+s<=sum) return 1;
else return 0;
}

void back(int k, int s)
{
int j;

if(s==sum) final(k);
else
 for(j=1;j<sum;j++)
  if(verif(j,k))
   {
    sol[k]=j;
    back(k+1,s+j);
   }
}

void main(void)
{
clrscr();
cout<<"Intr suma: ";
 cin>>sum;

back(0,0);
cout<<"Nr. sol= "<<cont;
getche();
}
// Descompunere suma - combinatii distincte
// Descompunere suma - combinatii distincte si numere distincte
// Descompunere suma - combinatii cu nr prime (test)
// Descompunere suma - combinatii cu nr prime (test)

// Descompunerea unei table de sah in dreptunghiuri disjuncte diferite
//2 cate 2, care au un nr. de patrate albe = nr de patrate negre
//(N^2 in suma de numere pare)

// Plata unei sume in monezi

Alocare dinamica - inversare lista construita prin insertie

//Inversare lista construita prin insertie
//
//V. Rosca - Culegere de probleme de programare, prb. 7.1 == [2], pag. 127
//+ [2], pag. 126, prb. 1
//
# include <stdio.h>;
# include <alloc.h>;
# include <conio.h>;

struct nod{int util; struct nod * next;};
typedef struct nod NOD;
typedef NOD * NOD_PTR;

int n,i,val;
NOD_PTR first,p,q,r;

void main(void)
{
clrscr();

printf("Intr nr de elemente: ");
 scanf("%d",&n);
//Creare primul nod
i=1;
printf("a[%d]=",i);
 scanf("%d",&val);

first=NULL;
first=(NOD_PTR)malloc(sizeof(NOD));
first->util=val;
first->next=NULL;

//Inserarea celorlalte numere

for(i=2;i<=n;i++)
{
 //Citire valoare
 printf("a[%d]=",i);
  scanf("%d",&val);

 //Determinare pozitie si legarea in lista
 p=first;
 while((p->next!=NULL)&&(p->next->util<val))
  {
   p=p->next;
  }
 //Cream un nou nod(var dinamica), dupa ce i-am determinat pozitia (p->next)
 q=(NOD_PTR) malloc(sizeof(NOD));
  q->util=val;
  q->next=NULL;
  if(val<p->util)
   {
    q->next=p;
    first=q;
   }
  else
   {
    q->next=p->next;
    p->next=q;
   }
}
//Afisam lista sortata prin inserare
printf("\nAfisam lista sortata:\n");
p=first;
while(p!=NULL)
{
 printf("%d ",p->util);
 p=p->next;
}

//Inversam lista
p=first;
//Lucrez cu perechi de pointeri si le interschimb legaturile
q=p->next;
p->next=NULL;

while(q)
{
 r=q->next;
 q->next=p;
 p=q;
 q=r; //q==NULL la ultima bucla
}
first=p;

//Afisam lista inversata
printf("\nAfisam lista inversata:\n");
p=first;
while(p!=NULL)
{
 printf("%d ",p->util);
 p=p->next;
}


getche();
}

Alocare dinamica - sortare liste

# include <stdio.h>;
# include <alloc.h>;
# include <conio.h>;

struct nod{int util; struct nod * next;};
typedef struct nod NOD;
typedef NOD * NOD_PTR;

int n,m,i,val;
NOD_PTR first1,first2,p,q;

NOD * sl_ins(int n)
{
NOD * first;
//Creare primul nod
i=1;
printf("a[%d]=",i);
 scanf("%d",&val);

first=NULL;
first=(NOD_PTR)malloc(sizeof(NOD));
first->util=val;
first->next=NULL;

//Inserarea celorlalte numere

for(i=2;i<=n;i++)
{
 //Citire valoare
 printf("a[%d]=",i);
  scanf("%d",&val);

 //Determinare pozitie si legarea in lista
 p=first;
 while((p->next!=NULL)&&(p->next->util<val))
  {
   p=p->next;
  }
 //Cream un nou nod(var dinamica), dupa ce i-am determinat pozitia (p->next)
 q=(NOD_PTR) malloc(sizeof(NOD));
  q->util=val;
  q->next=NULL;
  if(val<p->util)
   {
    q->next=p;
    first=q;
   }
  else
   {
    q->next=p->next;
    p->next=q;
   }
}
return first;
}

void afis(NOD * first)
{
//Afisam lista sortata prin inserare
printf("\nAfisam lista:\n");
p=first;
while(p!=NULL)
{
 printf("%d ",p->util);
 p=p->next;
}

}

void main(void)
{
clrscr();

printf("Intr nr de elemente din prima lista: ");
 scanf("%d",&n);
printf("Intr nr de elemente din a doua lista: ");
 scanf("%d",&m);


first1=sl_ins(n);
first2=sl_ins(m);

afis(first1);
 printf("\n");
afis(first2);

getche();
}

Backtracking - permutari - alocare dinamica

//Permutari prin alocare dinamica
# include <stdio.h>;
# include <conio.h>;
# include <alloc.h>;

# define MAX 100

struct nod{int util; struct nod * next;};
typedef struct nod NOD;
typedef NOD * NOD_PTR;

NOD_PTR vf;
int n,sol[MAX];

void final()
{
int i;
 for(i=0;i<n;i++)
  printf("%d ",sol[i]);
printf("\n");
}
int verif(int j, int k)
{
int i;
for(i=0;i<k;i++)
 if(sol[i]==j) return 0;
return 1;
}

void back(int k)
{
int j;
if(k==n) final();
else
 for(j=1;j<=n;j++)
  if(verif(j,k))
   {
    sol[k]=j;
    vf=s_push(vf,j)
   }
vf=s_pop(vf,val);
}

void main(void)
{
clrscr();

printf("Intr n= ");
 scanf("%d",&n);

back(0);

getche();
}

Maxim - Divide et Impera

# include <stdio.h>;
# include <conio.h>;
# include <values.h>;

# define MAX 100 //maxim 100 de elemente in sir

int i,n,val,a[MAX];

void main(void)
{
clrscr();

printf("Intr nr de elemente din sir: ");
 scanf("%d",&n);
printf("\nIntr elementele sirului:\n");
 for(i=0;i<n;i++)
  scanf("%d",&a[i]);

int s,d,mij;
int max,max1,max2;

s=0;
d=n;
mij=(s+d)/2;

max=max1=max2=-MAXINT;

int gasit=1;
while((s<=d)&&(gasit==1))
 {
  gasit=0;
  s=0;
  d=n;
  mij=(s+d)/2;


  while(a[mij+1]>max) {max1=a[mij+1]; s=mij+1;gasit=1;}
  while(a[mij-1]>max) {max2=a[mij-1]; d=mij-1;gasit=1;}
  if(max1>max2) max=max1;
  else max=max2;
 }

printf("\nMAX din sir este: %d",max);

getche();
}

Subsir de suma maxima

//
//Det secventa de m numere distincte dintr-un sir de n nr, cu suma maxima
//
# include <stdio.h>;
# include <conio.h>;
# include <values.h>;

# define MAX 100

int i,n,m,s,max=-MAXINT,a[MAX],sol[MAX];//,solmax[MAX];
int * solmax;
void afis()
{
int i;
s=0;
for(i=0;i<m;i++)
 {
  //printf("%d ",a[sol[i]]);
  s=s+a[sol[i]];
 }
 if(s>max)
   {
    max=s;
    //for(i=0;i<m;i++)
     //solmax[i]=sol[i];
     solmax=sol;  // !!! NU
   }
//printf("\n");
}
int verif(int j,int k)
{
int i;
for(i=0;i<k;i++)
 if(a[sol[i]]==a[j]) return 0;
return 1;
}
void back(int k)
{
int j;
if(k==m) afis();
else
 for(j=0;j<n;j++)
  if(verif(j,k))
   {
    sol[k]=j;
    back(k+1);
   }
}
void main(void)
{
clrscr();
printf("Intr n,m:\n");
 scanf("%d%d",&n,&m);
printf("Intr elemtele sirului:\n");
for(i=0;i<n;i++)
 scanf("%d",&a[i]);
back(0);
printf("\nSolutia optima este:\n");
for(i=0;i<m;i++)
 printf("%d ",a[solmax[i]]);
printf("\nSuma maxima este: %d\n",max);
getche();
}

Alocare dinamica - interclasare liste

# include <stdio.h>;
# include <alloc.h>;
# include <conio.h>;
# include <values.h>;
# include <math.h>;

struct nod{int util; struct nod * next;};
typedef struct nod NOD;
typedef NOD * NOD_PTR;

int n,m,i,val;
NOD_PTR first1,first2,first3,p,q,r,s,aux;

NOD * sl_ins(int n)
{
NOD * first;
//Creare primul nod
i=1;
printf("a[%d]=",i);
 scanf("%d",&val);

first=NULL;
first=(NOD_PTR)malloc(sizeof(NOD));
first->util=val;
first->next=NULL;

//Inserarea celorlalte numere

for(i=2;i<=n;i++)
{
 //Citire valoare
 printf("a[%d]=",i);
  scanf("%d",&val);

 //Determinare pozitie si legarea in lista
 p=first;
 while((p->next!=NULL)&&(p->next->util<val))
  {
   p=p->next;
  }
 //Cream un nou nod(var dinamica), dupa ce i-am determinat pozitia (p->next)
 q=(NOD_PTR) malloc(sizeof(NOD));
  q->util=val;
  q->next=NULL;
  if(val<p->util)
   {
    q->next=p;
    first=q;
   }
  else
   {
    q->next=p->next;
    p->next=q;
   }
}

//Creare santinele

r=NULL;
r=(NOD *)malloc(sizeof(NOD));
r->next=NULL;
r->util= - MAXINT;

//Legare la primul nod
r->next=first;
first=r;

r=NULL;
r=(NOD *)malloc(sizeof(NOD));
r->next=NULL;
r->util= + MAXINT;

//Legare dupa ultimul nod
// (**)

// !!! Parcurg lista (q nu e ultimul daca s-a inserat primul si p=?)
p=first;
while(p->next!=NULL)
{
p=p->next;
}
//Acum p==ultimul nod

// (**)
p->next=r;

return first;
}

void afis(NOD * first)
{
//Afisam lista sortata prin inserare
printf("\nAfisam lista:\n");
p=first;
while(p!=NULL)
{
 if(abs(p->util)!=MAXINT)
   printf("%d ",p->util);
 p=p->next;
}

}

void main(void)
{
clrscr();

printf("Intr nr de elemente din prima lista: ");
 scanf("%d",&n);
printf("Intr nr de elemente din a doua lista: ");
 scanf("%d",&m);


first1=sl_ins(n);
first2=sl_ins(m);

afis(first1);
 printf("\n");
afis(first2);

//Interclasare
p=first1;
q=first2;

first3=NULL;
first3=(NOD *)malloc(sizeof(NOD));
first3->next=NULL;


if(p->util<q->util)
 {
  first3->util=p->util;
  p=p->next;
 }
else
{
 first3->util=q->util;
  q=q->next;
}
aux=first3;

while((p!=NULL)&&(q!=NULL))
{

r=NULL;
r=(NOD *)malloc(sizeof(NOD));
r->next=NULL;

if(p->util<q->util)
 {
  r->util=p->util;
  p=p->next;
 }
else
{
 r->util=q->util;
  q=q->next;
}
aux->next=r;
aux=r;
}

//Copiere
if(p==NULL)
 aux=q;
else aux=p;

s=r;

r=NULL;
r=(NOD *)malloc(sizeof(NOD));
r->next=NULL;
r->util=aux->util;

aux=aux->next;
s->next=r;
s=r;

while(aux!=NULL)
{
r=NULL;
r=(NOD *)malloc(sizeof(NOD));
r->next=NULL;

r->util=aux->util;
aux=aux->next;

s->next=r;
s=r;

}

//Afisare sir interclasat
printf("\nAfisez sirl interclasat:\n");
afis(first3);

getche();
}

# include <stdio.h>;
# include <alloc.h>;
# include <conio.h>;

struct nod{int util; struct nod * next;};
typedef struct nod NOD;
typedef NOD * NOD_PTR;

int n,m,i,val;
NOD_PTR first1,first2,first3,p,q,r,s,aux;

NOD * sl_ins(int n)
{
NOD * first;
//Creare primul nod
i=1;
printf("a[%d]=",i);
 scanf("%d",&val);

first=NULL;
first=(NOD_PTR)malloc(sizeof(NOD));
first->util=val;
first->next=NULL;

//Inserarea celorlalte numere

for(i=2;i<=n;i++)
{
 //Citire valoare
 printf("a[%d]=",i);
  scanf("%d",&val);

 //Determinare pozitie si legarea in lista
 p=first;
 while((p->next!=NULL)&&(p->next->util<val))
  {
   p=p->next;
  }
 //Cream un nou nod(var dinamica), dupa ce i-am determinat pozitia (p->next)
 q=(NOD_PTR) malloc(sizeof(NOD));
  q->util=val;
  q->next=NULL;
  if(val<p->util)
   {
    q->next=p;
    first=q;
   }
  else
   {
    q->next=p->next;
    p->next=q;
   }
}
return first;
}

void afis(NOD * first)
{
//Afisam lista sortata prin inserare
printf("\nAfisam lista:\n");
p=first;
while(p!=NULL)
{
 printf("%d ",p->util);
 p=p->next;
}

}

void main(void)
{
clrscr();

printf("Intr nr de elemente din prima lista: ");
 scanf("%d",&n);
printf("Intr nr de elemente din a doua lista: ");
 scanf("%d",&m);


first1=sl_ins(n);
first2=sl_ins(m);

afis(first1);
 printf("\n");
afis(first2);

//Interclasare
p=first1;
q=first2;

first3=NULL;
first3=(NOD *)malloc(sizeof(NOD));
first3->next=NULL;


if(p->util<q->util)
 {
  first3->util=p->util;
  p=p->next;
 }
else
{
 first3->util=q->util;
  q=q->next;
}
aux=first3;

while((p!=NULL)&&(q!=NULL))
{

r=NULL;
r=(NOD *)malloc(sizeof(NOD));
r->next=NULL;

if(p->util<q->util)
 {
  r->util=p->util;
  p=p->next;
 }
else
{
 r->util=q->util;
  q=q->next;
}
aux->next=r;
aux=r;
}

//Copiere
if(p==NULL)
 aux=q;
else aux=p;

s=r;

r=NULL;
r=(NOD *)malloc(sizeof(NOD));
r->next=NULL;
r->util=aux->util;

aux=aux->next;
s->next=r;
s=r;

while(aux!=NULL)
{
r=NULL;
r=(NOD *)malloc(sizeof(NOD));
r->next=NULL;

r->util=aux->util;
aux=aux->next;

s->next=r;
s=r;

}

//Afisare sir interclasat
printf("\nAfisez sirl interclasat:\n");
afis(first3);

getche();
}