IMPORTANT: Per accedir als fitxer de subversion: http://acacha.org/svn (sense password). Poc a poc s'aniran migrant els enllaços. Encara però funciona el subversion de la farga però no se sap fins quan... (usuari: prova i la paraula de pas 123456)

Algorismes d'ordenació

Bombolla

Recursos:

Backtracking

Problema dels elements que han de sumar un valor exacte (mochila, xifres)

#include <stdio.h>
#include <stdlib.h>

#ifndef NOUTILITZAT
 #define NOUTILITZAT 0
 #define UTILITZAT 1 
#endif
     
void buscar_suma(int nvalorsActual, int *valorsActuals,int nvalors,int *valors,int valorBuscat);   
 
int suma(int n,int *valorsActuals, int *valors);

void mostrarResultat(int n,int *valorsActuals, int *valors, int resultat);

int main (int argc, char *argv[]) {

 //argv[1] --> Conté el nombre de valors
 int nvalors=atoi(argv[1]);
 
 int *valors = (int*) calloc(nvalors,sizeof(int));
 
 int i;
 for(i=0; i<nvalors; i++) {
   valors[i]=atoi(argv[i+2]);
 }
 
 int valorbuscat=0;
 
 valorbuscat=atoi(argv[argc-1]);
 
 int *valorsActuals = (int*) calloc(nvalors,sizeof(int));
 int k;
 for(k=0; k<nvalors; k++) {
    valorsActuals[k]=NOUTILITZAT; //O indica que el valor no s'utilitza
 }
 valorsActuals[0]=UTILITZAT;
 buscar_suma(1,valorsActuals,nvalors,valors,valorbuscat);
 exit(0);
}

void buscar_suma(int nvalorsActual, int *valorsActuals,int nvalors,int *valors,int valorBuscat) {

 if (suma(nvalors,valorsActuals,valors)==valorBuscat) {
  //Solució
  mostrarResultat(nvalors,valorsActuals,valors,valorBuscat);
 }
 
 if (nvalorsActual!=nvalors) {
  
  //Esquerre--> El valorActual no s'utilitza
  valorsActuals[nvalorsActual-1]=NOUTILITZAT;
  valorsActuals[nvalorsActual]=UTILITZAT;
  buscar_suma(nvalorsActual+1,valorsActuals,nvalors,valors,valorBuscat);  
  
  //Dreta--> El valor actual s'utilitza
  valorsActuals[nvalorsActual-1]=UTILITZAT;
  valorsActuals[nvalorsActual]=UTILITZAT;
  buscar_suma(nvalorsActual+1,valorsActuals,nvalors,valors,valorBuscat);
   
 }
}

int suma(int n,int *valorsActuals, int *valors) {
 int acumulador=0;
 int i;
 for (i=0;i<n;i++) {
  if (valorsActuals[i]==UTILITZAT)
    acumulador=acumulador+valors[i];
 }
 return acumulador;
} 

void mostrarResultat(int n,int *valorsActuals, int *valors, int resultat) {
 int i;
 for (i=0;i<n;i++) {
  if (valorsActuals[i]==UTILITZAT) { 
   if (i!=(n-1)) 
    printf("%d+",valors[i]);  
   else
    printf("%d=%d\n",valors[i],resultat);
  }
 }    
}

Sudoku

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

#ifndef MAX_FILES
 #define MAX_FILES 9
 #define MAX_COLUMNES 9
#endif

#ifndef TRUE
 #define TRUE 1
 #define FALSE 0
#endif

typedef int boolean;  

typedef struct quadre QUADRE;  

struct quadre{
 int posicio; // Les posicions van de la 0 (1,1) a la 80 (9,9) passant per 7 (1,9) i 8 (2,1)
 int valor; // Els valors són 0 si no hi ha cap valor o de 1-9.
};

void sudoku(int posicio,QUADRE valorsinicials[], int nvalorsinicials, int tauler[]); 

boolean esValorInicial(int posicio,QUADRE valorsinicials[], int nvalorsinicials); 

boolean esValorValid(int valor,int posicio,int tauler[]);

void mostrarSolucio(int tauler[],QUADRE valorsinicials[],int nvalorsinicials);

int main(int argc, char **argv) {

int POSICIO_MAXIMA= MAX_FILES*MAX_COLUMNES;

int tauler[POSICIO_MAXIMA];
QUADRE *valorsinicials;
int i,k,j, nvalors_inicials;

if (argc<2) {
 printf("S'ha d'especificar com a mínim un paràmetre: %s valorsinicials\n",argv[0]);
 exit(1);
}

nvalors_inicials= atoi (argv[1]);

valorsinicials= (QUADRE*) malloc(sizeof(QUADRE)*nvalors_inicials);

if (argc!=(2+nvalors_inicials*3)) {
 printf("S'han d'especificar 3 valors/paràmetres (posició x i y + valor) per cada valor inicial\n");
 exit(0);		
}

for (i = 0; i < nvalors_inicials; ++i) {
 valorsinicials[i].posicio=atoi(argv[2+i*3])*MAX_COLUMNES+atoi(argv[3+i*3]); //posicio=fila*nquadresxcolumna+columna
 valorsinicials[i].valor=atoi(argv[4+i*3]);
}

//iniciar el tauler:
for (k = 0; k < POSICIO_MAXIMA; ++k) {
 tauler[k]=0;
}

//Colocar els valors inicials
for (j = 0; j < nvalors_inicials; ++j) {
 int pos= valorsinicials[j].posicio;
 tauler[pos]=valorsinicials[j].valor;
}

printf("Sudoku a resoldre:\n");
mostrarSolucio(tauler,valorsinicials,nvalors_inicials);
sleep(5);

sudoku(0,valorsinicials,nvalors_inicials, tauler);
free(valorsinicials);

exit(0);
}

void sudoku(int posicio,QUADRE valorsinicials[], int nvalorsinicials, int tauler[]){
 //Declaració de variables
 int i;
 int POSICIO_MAXIMA= MAX_FILES*MAX_COLUMNES;
	
 //Saltar els valors que ja ens venen donats
 if (esValorInicial(posicio, valorsinicials, nvalorsinicials)) {
  //Condició final
  if (posicio==POSICIO_MAXIMA-1) {
   //Solució.
   mostrarSolucio(tauler,valorsinicials,nvalorsinicials);
  }
  sudoku(posicio+1,valorsinicials,nvalorsinicials,tauler);
  return;
 }

 //Valors possibles 1-9
 for (i = 1; i < 10; ++i) {
  if (esValorValid(i,posicio,tauler)) {
   tauler[posicio]=i;
   //Condició final
   if (posicio==POSICIO_MAXIMA-1) {
    //Solució.
    mostrarSolucio(tauler,valorsinicials,nvalorsinicials);
   }
   sudoku(posicio+1,valorsinicials,nvalorsinicials,tauler);
   //Si arriba aquí és que el valor era valid però no porta a una solució
   tauler[posicio]=0;
  }
  //Si arriba a qui és que no hi ha cap valor que sigui possible. No fem res--> desfa 
 //la pila de crides a la funció sudoku
 }
}

boolean esValorInicial(int posicio,QUADRE valorsinicials[], int nvalorsinicials){
 int i;
 for (i = 0; i < nvalorsinicials; ++i) {
  if (valorsinicials[i].posicio==posicio)
   return TRUE;
  }
  return FALSE;
}
 
boolean esValorValid(int valor,int posicio,int tauler[]){
 //Obtenir valors de fila i columna per a la posició donada
 int fila,columna,i,j,k,l;
 int nquadre33Horizontal,nquadre33Vertical;

 fila=posicio/MAX_COLUMNES;
 columna=posicio%MAX_COLUMNES;
   
 //Buscar si hi ha alguna fila amb el mateix valor
 for (i = 0; i < MAX_FILES; ++i) {
  if (valor==tauler[MAX_COLUMNES*fila+i]) {
   return FALSE;
  }
 }
 //Buscar si hi ha alguna columna amb el mateix valor
 for (j = 0; j < MAX_FILES; ++j) {
  if (valor==tauler[columna+j*MAX_FILES]) {
   return FALSE;
  }
 }
   
 //Buscar si hi ha algun quadre amb el mateix valor dins del subquadre 3x3
 nquadre33Horizontal=columna/3;
 nquadre33Vertical=fila/3;    
 for (k = 0; k < 3; ++k) {
  for (l = 0; l < 3; ++l) {
   int fila=k+nquadre33Vertical*3;
   int columna=l+nquadre33Horizontal*3;
   if (valor==tauler[fila*MAX_COLUMNES+columna]) { 
    return FALSE;
   }
  }
 }   
 return TRUE;
}

void mostrarSolucio(int tauler[],QUADRE valorsinicials[],int nvalorsinicials){
int i,j,posicio;
for (i = 0; i < MAX_COLUMNES; ++i) {
 for (j = 0; j < MAX_FILES; ++j) {
   posicio=i*MAX_COLUMNES+j;
   //Si és valor inicial pintar en negreta (només vàlid en Linux)
   if (esValorInicial(posicio,valorsinicials,nvalorsinicials)) {
    printf("\033[1m%d\033[0m ",tauler[i*MAX_COLUMNES+j]);
   }
   else {
    printf("%d ",tauler[i*MAX_COLUMNES+j]);
   }
  }
  printf("\n");
 }
 printf("\n");
 printf("\n");
}

Salt del cavall

#include <stdlib.h>
#include <stdio.h>


#ifndef MAX_FILES
 #define MAX_FILES 8
 #define MAX_COLUMNES 8 
#endif

#ifndef TRUE
 #define TRUE 1
 #define FALSE 0
#endif

typedef int boolean;
typedef struct posicio POSICIO;
struct posicio{
 int x;
 int y;
};

boolean posiciovalida(POSICIO pos);
//void saltcavall(POSICIO *pos,int num_posicio,POSICIO *recorregut[],int tauler[][MAX_COLUMNES]);

void saltcavall(POSICIO pos, int num_posicio, POSICIO recorregut[], int tauler[][MAX_COLUMNES]);
void mostrarsolucio(POSICIO *recorregut[]);
void mostrarsolucio1(POSICIO recorregut[]);
void mostrarsolucio2(POSICIO recorregut[],int files, int columnes);
void visualitza(int files,int columnes,int *p);
void visualitza2(int files,int columnes,int *p);

int main(int argc, char **argv) {
 //inicialització
 int x,y,num_posicio;
 //Paràmetres
  // argv[1] --> x inicial
  // argv[2] --> y inicial
  // argv[3] --> files del quadrat
  // argv[4] --> columnes del quadrat

 POSICIO pos_inicial;
 
 if (argc!=3) {
  printf("Utilitza %s x_inicial y_inicial\n", argv[0]);
  exit (1);
 }

pos_inicial.x=atoi(argv[1]);
pos_inicial.y=atoi(argv[2]);

printf("Valor inicial (%d,%d) \n", pos_inicial.x,pos_inicial.y);
if ((pos_inicial.x>=MAX_FILES) || (pos_inicial.y>=MAX_COLUMNES)) {
 printf("Valor inicial (%d,%d) fora de rang\n", pos_inicial.x,pos_inicial.y);
 exit(1);
}
	
POSICIO recorregut[MAX_FILES*MAX_COLUMNES];
//struct posicio recorregut[MAX_FILES*MAX_COLUMNES];
//Inicialitza recorregut:
int k;
for (k = 0; k < MAX_FILES*MAX_COLUMNES; ++k) {
 recorregut[k].x=-1;
 recorregut[k].y=-1;	
}
	
int tauler[MAX_FILES][MAX_COLUMNES];

for (x = 0; x < MAX_FILES; ++x) {
 for (y = 0; y < MAX_COLUMNES; ++y) {
  tauler[x][y]=-1;
 }
}
	
num_posicio=0;
saltcavall(pos_inicial,num_posicio,&recorregut[0],tauler);
 	
 
void saltcavall(POSICIO pos, int num_posicio, POSICIO recorregut[], int tauler[][MAX_COLUMNES]) {
 //Afegir la posicio a recorregut
 int x= pos.x;
 int y= pos.y;
 recorregut[num_posicio].x = x;
 recorregut[num_posicio].y = y;
 
 tauler[x][y]=num_posicio;
 //printf("num_posicio:%d\n",num_posicio);
 //visualitza2(MAX_FILES,MAX_COLUMNES,&tauler[0][0]);
 //printf("\n");
 //printf("\n");
 //mostrarsolucio2(recorregut,MAX_FILES, MAX_COLUMNES);

 //Condició frontera
 if(num_posicio==(MAX_FILES*MAX_COLUMNES -1)) {
  //Solució
  printf("Trobada una solució:\n");
  mostrarsolucio2(recorregut,MAX_FILES, MAX_COLUMNES);
  visualitza2(MAX_FILES,MAX_COLUMNES,&tauler[0][0]);
 }

 //Posicions següents
 POSICIO next_pos;
   int j;
   for (j = 0; j < 8; ++j) {
    switch (j) {
     case 0:
       next_pos.x=pos.x+2;
       next_pos.y=pos.y-1;
       break;
     case 1:
       next_pos.x=pos.x+2;
       next_pos.y=pos.y+1;			
       break;
     case 2:
       next_pos.y=pos.y+2;
       next_pos.x=pos.x-1;										
       break;
     case 3:
       next_pos.y=pos.y+2;
       next_pos.x=pos.x+1;			
       break;
     case 4:
       next_pos.x=pos.x-2;
       next_pos.y=pos.y+1;										
       break;
     case 5:
       next_pos.x=pos.x-2;
       next_pos.y=pos.y-1;							
       break;
     case 6:
       next_pos.y=pos.y-2;
       next_pos.x=pos.x+1;									
       break;
     case 7:
       next_pos.y=pos.y-2;
       next_pos.x=pos.x-1;										
       break;
     default:
       break;
     }
    if (posiciovalida(next_pos) && tauler[next_pos.x][next_pos.y]==-1) {
     saltcavall(next_pos,num_posicio+1,recorregut,tauler);
     //si arriba aquí és que el possible no era bó --> Desfer
     recorregut[num_posicio+1].x = -1;
     recorregut[num_posicio+1].y = -1;
     tauler[next_pos.x][next_pos.y]=-1;
    }
   }
}

void mostrarsolucio1(POSICIO recorregut[]) {
 int i;
 for (i = 0; i < (MAX_FILES*MAX_COLUMNES); ++i) {
  printf("(%d,%d) ",recorregut[i].x,recorregut[i].y);
 }
 printf("\n");
}

void mostrarsolucio2(POSICIO recorregut[],int files, int columnes) {
 int i;
 for (i = 0; i < (files*columnes); ++i) {
  printf("(%d,%d) ",recorregut[i].x,recorregut[i].y);
 }
 printf("\n");
}

void mostrarsolucio(POSICIO* recorregut[]) {
 int i;
 for (i = 0; i < (MAX_FILES*MAX_COLUMNES); ++i) {
	printf("(%d,%d) ",recorregut[i]->x,recorregut[i]->y);
 }
}

boolean posiciovalida(POSICIO pos) {
 if ((pos.x>=0)&&(pos.x<MAX_FILES)&&(pos.y>=0)&&(pos.y<MAX_COLUMNES))
  return TRUE;
 else
  return FALSE;
} 

/* SUBRUTINA QUE VISUALITZA UNA MATRIU */
void visualitza(int files,int columnes,int *p) {
 int i=0;
 int j=0;
 for (i=0;i<files;i++) {
  for(j=0;j<columnes;j++) {
   printf("\t%d",*p);
    if((i!=files) && (j!=columnes)) {
     p++;
    }
   }
  printf("\n");
 }
}  

void visualitza2(int files, int columnes,int *p) {
  int i;
  int j;
  for(i=0; i<files; i++) {
   for(j=0; j<columnes; j++) {
	printf("\t%d",p[i*columnes+j]);
   }
  printf("\n");
  }
 }

Programa per resoldre les xifres del programa de TV "Cifras y Letras"

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

#ifndef TRUE
 #define TRUE 1
 #define FALSE 0
#endif

typedef int boolean; 

//ArbreBinari 

#ifndef SUMA
 #define SUMA -1
 #define RESTA -2
 #define MULTIPLICACIO -3
 #define DIVISIO -4
#endif

typedef int tipusDada;  

/*
 * 0 < tipusDada < 1000
 * Operacions:
 * SUMA -1
 * RESTA -2
 * MULTIPLICACIO -3
 * DIVISIO -4
 */

typedef struct arbre ARBRE;

struct arbre {
 tipusDada valor;
 int acumulat;
 ARBRE *esquerre;
 ARBRE *dreta;
} ;

void mostrarResultat(ARBRE *resultat);  

int calcularResultat(ARBRE *resultat); 

char obtenirOperador(int valor); 

void buscarResultat(ARBRE *resultat, int valorBuscat,int nvalors,int valors[]);

int main(int argc, char **argv) {
    
/*Exemple senzill per a comprovar les operacions
 
 ARBRE resultat1;
 ARBRE resultat2;
 ARBRE resultat3;
 ARBRE resultat4;
 ARBRE resultat5;
 
 resultat1.valor=3;
 resultat1.esquerre=NULL;
 resultat1.dreta=NULL;
 resultat1.acumulat=0;
 
 resultat2.valor=3;
 resultat2.esquerre=NULL;
 resultat2.dreta=NULL;
 resultat2.acumulat=0;
  
 resultat3.valor=-1;
 resultat3.esquerre=&resultat1;
 resultat3.dreta=&resultat2;
 resultat3.acumulat=0;
 
 resultat4.valor=3;
 resultat4.esquerre=NULL;
 resultat4.dreta=NULL;
 resultat4.acumulat=0;
 
 resultat5.valor=-2;
 resultat5.esquerre=&resultat3;
 resultat5.dreta=&resultat4;
 resultat5.acumulat=0;
  */
 
 ARBRE primernode;
 int valorBuscat,nvalors,i;
 int *valors;
 
 if (argc<4) {
  printf("Cal passar com a mínim 4 paràmetres: %s valorBuscat nvalors valor1 valor2 ...\n",argv[0]);
 }
 
 valorBuscat=atoi(argv[1]);
 nvalors=atoi(argv[2]);
 
 if (argc!=(3+nvalors)) {
  printf("Número de pàrametres incoherent...\n");
 }
 
 valors = (int*) malloc(sizeof(int)*nvalors);
 
 //Inicialitzem valors
 for (i = 0; i < nvalors; ++i) {
  valors[i]=atoi(argv[3+i]);
 }
 
 primernode.acumulat=0;
 primernode.valor=valors[0];
 primernode.esquerre=NULL;
 primernode.dreta=NULL;
 
 valors[0]=-1;
 buscarResultat(&primernode,valorBuscat,nvalors,valors);
 
 free(valors);
 exit(0);
}  

void buscarResultat(ARBRE *resultat, int valorBuscat,int nvalors,int valors[]) {
 
 int i,j,valoractual,resul;
 
 //Condició final
 resul=calcularResultat(resultat);
 valoractual=resul;
 if (resul==valorBuscat) {
  //Trobada solució
  printf("Trobada una solució:\n");
  mostrarResultat(resultat);
  printf(" = %d\n",resul);
  //Si no volem mostrar més solucions:
  //exit(0);
 }
 
 //mostrarResultat(resultat);
 //printf(" = %d\n",resul); 
 
 ARBRE tmp_resultat;
 ARBRE new_resultat;
 ARBRE node_dret;
 
 for (i = 0; i < nvalors; ++i) {
  if (valors[i]!=-1) {
   int valor;
   valor=valors[i];
   for (j=-1;j>-6;j--) {
    switch (j) {
     case SUMA:
      tmp_resultat.valor=valor;
      tmp_resultat.esquerre=NULL;
      tmp_resultat.dreta=NULL;
      new_resultat.valor=SUMA;
      new_resultat.esquerre=resultat;      
      new_resultat.dreta=&tmp_resultat;
      valors[i]=-1;
      buscarResultat(&new_resultat,valorBuscat,nvalors,valors);
      //Si arriba aqui és torna enrere
      valors[i]=valor;
      break;
     case RESTA:
      if (valor<valoractual) {
       tmp_resultat.valor=valor;
       tmp_resultat.esquerre=NULL;
       tmp_resultat.dreta=NULL;
       new_resultat.valor=RESTA;
       new_resultat.esquerre=resultat;      
       new_resultat.dreta=&tmp_resultat;
       valors[i]=-1;
       buscarResultat(&new_resultat,valorBuscat,nvalors,valors);
       //Si arriba aqui és torna enrere
       valors[i]=valor;
      }
      break;
     case MULTIPLICACIO:
      //Totes les multiplicacions són vàlides
      tmp_resultat.valor=valor;
      tmp_resultat.esquerre=NULL;
      tmp_resultat.dreta=NULL;
      new_resultat.valor=MULTIPLICACIO;
      new_resultat.esquerre=resultat;      
      new_resultat.dreta=&tmp_resultat;
      valors[i]=-1;
      buscarResultat(&new_resultat,valorBuscat,nvalors,valors);
      //Si arriba aqui és torna enrere
      valors[i]=valor;
      break;
     case DIVISIO:
      if (valor%valoractual==0) {
       tmp_resultat.valor=valor;
       tmp_resultat.esquerre=NULL;
       tmp_resultat.dreta=NULL;
       new_resultat.valor=MULTIPLICACIO;
       new_resultat.esquerre=resultat;      
       new_resultat.dreta=&tmp_resultat;
       valors[i]=-1;
       buscarResultat(&new_resultat,valorBuscat,nvalors,valors);
       //Si arriba aqui és torna enrere
       valors[i]=valor;
      }
      break;
      case -5:
      //No utilitzar el valor actual
      if (resultat->esquerre==NULL && resultat->dreta==NULL) {
       //FULLA
       new_resultat.valor=valors[i];
       new_resultat.acumulat=valors[i];
       new_resultat.esquerre=NULL;
       new_resultat.dreta=NULL;
      }
      else {
       node_dret.valor=valors[i];
       node_dret.acumulat=valors[i];
       node_dret.esquerre=NULL;
       node_dret.dreta=NULL;              
       new_resultat.valor=resultat->valor;
       new_resultat.acumulat=resultat->acumulat;
       new_resultat.esquerre=resultat->esquerre;
       new_resultat.dreta=&node_dret;
      }
      valors[i]=-1;      
      buscarResultat(&new_resultat,valorBuscat,nvalors,valors);
      valors[i]=valor;
     default:
     break; 
    }
    }
   }
  }
}  

int calcularResultat(ARBRE *resultat) {
 if (resultat==NULL) {
  return 0;
 }
 //Recorregut postordre de l'arbre
 int esquerre,dreta;
 if (resultat->esquerre!=NULL)
  esquerre= calcularResultat(resultat->esquerre);
 if (resultat->dreta!=NULL)
  dreta= calcularResultat(resultat->dreta);
 //Operació
 switch (resultat->valor) {
  case SUMA:
   resultat->acumulat=esquerre+dreta;
   return esquerre+dreta;
   break;
  case RESTA:
   resultat->acumulat=esquerre-dreta;
   return esquerre-dreta;
   break;
  case MULTIPLICACIO:
   resultat->acumulat=esquerre*dreta;
   return esquerre*dreta;  
   break;
  case DIVISIO:
   resultat->acumulat=esquerre/dreta;
   return esquerre/dreta; 
   break;
  default:
   //Estem en un node valor
   resultat->acumulat=resultat->valor;
   return resultat->acumulat;
   break;
 }
}

void mostrarResultat(ARBRE *resultat) {
 if (resultat==NULL) {
  return;
 }
 //RECORREGUT INORDRE de l'arbre 
 if (resultat->esquerre!=NULL) {
  printf("(");
  mostrarResultat(resultat->esquerre);
 }
 //Operació
 if (resultat->esquerre==NULL && resultat->dreta==NULL) {
  //FULLA --> valor
  printf("%d ",resultat->valor);
 }
 else { //operació
  printf("%c ",obtenirOperador(resultat->valor));
 }
 
 if (resultat->dreta!=NULL) {
  mostrarResultat(resultat->dreta);
  printf(")");
 } 
}  

char obtenirOperador(int valor) {
switch (valor) {
 case SUMA:
  return '+';
  break;
 case RESTA:
  return '-';  
  break;
 case MULTIPLICACIO:
  return '*';  
  break;
 case DIVISIO:
  return '/'; 
  break;
 default:
  return 'e';
  break;
}
}