ALGORITHMES RÉCURSIFS VS ALGORITHMES ITÉRATIFS

/*
  Université des sciences et de la technologie Houari Boumadiane(USTHB)                   
  Faculté d'Electronique & d'Informatique                                            
  Département informatique                                                                                 
  Spécialité : Master 1 Réseaux et système distribués
  Module : Algorithmique avncée et complexité                                                   
  Auteur: ZERROUKI Boualam
  Date: 27/11/2011 00:00
  Description : Mini-projet
                Les tours de Hanoi
                Algorithmes récursifs vs Algorithmes itératifs

  _______________________________________________________________________________________________
                                                                                               
   Inclusion des bibliothèques nécessaires                                                       
  _______________________________________________________________________________________________
*/

#include <stdio.h>
#include <malloc.h>
#include <time.h>

/*Définition d'une pile */
typedef struct element 
        {
               int numeroDisque;
               int rayonDisque;
               struct element *suivant;
        }pile;
        
/*les prototypes */
       
/*fonction initpile */
void initpile(pile**);

/*fonction pilevide */
unsigned pilevide(pile*);

/*fonction sommetpile */
void sommetpile(pile**,int*);

/*fonction empiler */ 
void empiler(pile**,int,int);

/*fonction depiler */
void depiler(pile**,int*,int*);

/*affichage d'une pile*/
void affichePile(pile*);

/*
  fonctions tours de Hanoi 
  fonction tours de Hanoi recursive 
*/
void tourDeHanoiRec(int,pile**,pile**,pile**);

/*
  fonction deplacer
  _______________________________________________________________________________________________
                                                                                               
   Retourne le numéro de l'élément à déplacer selon le numéro de coups et le nb total d'éléments  
  _______________________________________________________________________________________________
                                                                                                 
   Paramètres :                                                                                  
   - numéro du coup précédent                                                                    
   - numéro du coup actuel                                                                       
   - nombre total d'éléments                                                                     
  _______________________________________________________________________________________________
*/
int deplacer(int,int,int);

/*
  fonction position
  _______________________________________________________________________________________________
                                                                                                
   Retourne le numéro de la pile contenant l'élément à déplacer                                  
  _______________________________________________________________________________________________
                                                                                               
   Paramètres :                                                                                  
   - numéro de l'élément à déplacer                                                              
   - 3 pointeurs vers les 3 piles d'éléments                                                                        
  _______________________________________________________________________________________________
*/
int position(int,pile**,pile**,pile**);

/*fonction tours de Hanoi itérative */
void tourDeHanoiIte(int,pile**,pile**,pile**);


/*la fonction principalle
  debut main*/
int main(void)
{
    printf("      *----------------------------------------------------------*\n");
    printf("      *                 USTHB, FEI, INFORMATIQUE                 *\n");
    printf("      *                       Master 1 RSD                       *\n");
    printf("      *                  Mini projet complexite                  *\n");
    printf("      *                    Les tours de Hanoi                    *\n");
    printf("      *      Algorithmes recursifs vs Algorithmes iteratifs      *\n");
    printf("      *                                                          *\n");
    printf("      *----------------------------------------------------------*\n\n");
    
    pile *pileA,*pileB,*pileC,*pileD;
    int nbDisque=0,i,numeroDisque,rayonDisque;
    char nMenu;
    clock_t debut,fin;
    float delta;
    
    /* Initialise les piles */
    initpile(&pileA);
    initpile(&pileB);
    initpile(&pileC);
    while(nbDisque<1)
    {
              printf("Entrez le nombre des disques : ");
              scanf("%d",&nbDisque);
    }
    
    /* Tous les éléments sont sur la pile A au début */
    for(i=0;i<nbDisque;i++)empiler(&pileA,i+1,nbDisque-i);
    
     printf("\n\n*---------------------------*\n");
     printf("*                           *\n");
     printf("*  Menu :                   *\n");
     printf("*                           *\n");
     printf("*    1 Methode recursive    *\n");
     printf("*    2 Methode iterative    *\n");
     printf("*    3 Quitter              *\n");
     printf("*                           *\n");
     printf("*---------------------------*\n");
      m :
      printf("\n\nEntrez un numero de menu : ");scanf("%s",&nMenu);
      switch(nMenu)
      {
                   case '1' : goto a;
                   break;
                   case '2' : goto b;
                   break;
                   case '3' : goto c;
                   default : printf("\nVous avez pas introduit un numero de menu...");
                   goto m;
      }
      
    a:
    debut=clock();
    tourDeHanoiRec(nbDisque,&pileA,&pileC,&pileB);
    fin=clock();
    goto d;
    b:
    debut=clock();
    tourDeHanoiIte(nbDisque,&pileA,&pileB,&pileC);
    fin=clock();
    d:
    delta=(float)(fin-debut)/CLOCKS_PER_SEC;
    printf("\nLe temps d'execution est : %f\n",delta);
    printf("\n");
    system("pause");
    c:         
    return 0;
}
/*fin main*/  
                 
void initpile(pile **sommet)
{
     *sommet=NULL;
}
unsigned pilevide(pile*sommet)
{
         if(sommet==NULL)return 1;
         else return 0;
} 
void sommetpile(pile**sommet,int*numeroDisque)
{
     *numeroDisque=(*sommet)->numeroDisque;
}                                    
void empiler(pile**sommet,int numeroDisque,int rayonDisque)
{
     pile *p;
     
     p=(pile*)malloc(sizeof(pile));
     p->numeroDisque=numeroDisque;
     p->rayonDisque=rayonDisque; 
     p->suivant=*sommet;
     *sommet=p;
} 
void depiler(pile**sommet,int*numeroDisque,int*rayonDisque)
{
     pile *p;
     
     p=*sommet;
     *numeroDisque=p->numeroDisque;
     *rayonDisque=p->rayonDisque;
     *sommet=p->suivant;
     free(p);p=NULL;
}
void affichePile(pile*sommet)
{
     pile *r,*p;
     int rayonDisque=0;
     int numeroDisque=0;
     
     initpile(&p);
     initpile(&r);
     p=sommet;
     while(!pilevide(p))
     {     
             depiler(&p,&numeroDisque,&rayonDisque);
             empiler(&r,numeroDisque,rayonDisque);
     }
     while(!pilevide(r))
     {
            depiler(&r,&numeroDisque,&rayonDisque);
            printf("%d",rayonDisque);
            empiler(&p,numeroDisque,rayonDisque);
     }
     sommet=p;                
}      
void tourDeHanoiRec(int nbDisque,pile**pileA,pile**pileB,pile**pileC)
{
     int rayonDisque=0;
     int numeroDisque=0;
     
     if(nbDisque == 1)
     {
                 depiler(pileA,&numeroDisque,&rayonDisque);
                 empiler(pileB,numeroDisque,rayonDisque);
     }
     else
     {
         tourDeHanoiRec(nbDisque-1,pileA,pileC,pileB);
         depiler(pileA,&numeroDisque,&rayonDisque);
         empiler(pileB,numeroDisque,rayonDisque);
         tourDeHanoiRec(nbDisque-1,pileC,pileB,pileA);
     }
}
int deplacer(int coupPrecedent,int coupActuel,int nbDisque)
{
	int i;
	int masque=0x0001;

	for(i=0;i<nbDisque;i++,masque<<=1)if(!(coupPrecedent&masque)&&(coupActuel&masque))return(nbDisque-i);
	return 0;
}
int position(int dep,pile**pileA,pile**pileB,pile**pileC)
{
	int numeroDisque=0;
	if(pilevide(*pileA)!=1){sommetpile(pileA,&numeroDisque);if(dep==numeroDisque)return 1;}
	if(pilevide(*pileB)!=1){sommetpile(pileB,&numeroDisque);if(dep==numeroDisque)return 2;}
	if(pilevide(*pileC)!=1){sommetpile(pileC,&numeroDisque);if(dep==numeroDisque)return 3;}
	
	return 0;
}                  
void tourDeHanoiIte(int nbDisque,pile**pileA,pile**pileB,pile**pileC)
{
     int coupTotal,coupPrecedent,coupActuel,dep,pos,numeroDisque,rayonDisque;
     
     /* Calcule le nombre de coups nécessaires */
     coupTotal=(1<<nbDisque)-1;
     /* Coup initial */
     coupPrecedent=0;
     
     if(nbDisque<7)
     {
                   printf("\n");  
                   printf("|");affichePile(*pileA);
                   printf("\n");
                   printf("|");affichePile(*pileB);
                   printf("\n");
                   printf("|");affichePile(*pileC);
                   printf("\n\n");
     }
     
     for(coupActuel=1;coupActuel<=coupTotal;coupActuel++)
	 {
             /* Récupère le numéro de l'élément à déplacer */                                                
             dep=deplacer(coupPrecedent,coupActuel,nbDisque);
             /* Trouve la pile contenant cet élément */
             pos=position(dep,pileA,pileB,pileC);
             if(dep%2==1)
		     {
 	         /* Déplacement circulaire vers la gauche */
             switch(pos)
		    	{
				case 1 :
                    depiler(pileA,&numeroDisque,&rayonDisque);
                    empiler(pileC,numeroDisque,rayonDisque);
					break;
				case 2 :
					depiler(pileB,&numeroDisque,&rayonDisque);
                    empiler(pileA,numeroDisque,rayonDisque);
					break;
				case 3 :
					depiler(pileC,&numeroDisque,&rayonDisque);
                    empiler(pileB,numeroDisque,rayonDisque);
					break;
		    	}
	    	}
	    	else
	    	{
            /* Déplacement circulaire vers la droite */
			switch(pos)
			{
				case 1 :
					depiler(pileA,&numeroDisque,&rayonDisque);
                    empiler(pileB,numeroDisque,rayonDisque);
					break;
				case 2 :
					depiler(pileB,&numeroDisque,&rayonDisque);
                    empiler(pileC,numeroDisque,rayonDisque);
					break;
				case 3 :
					depiler(pileC,&numeroDisque,&rayonDisque);
                    empiler(pileA,numeroDisque,rayonDisque);
					break;
			}
	    	}
  	    /* Mémorise le numéro du coup */
		coupPrecedent=coupActuel;
	    if(nbDisque<7)
        {
	                	printf("|");affichePile(*pileA);
		                printf("\n");
		                printf("|");affichePile(*pileB);
		                printf("\n");
		                printf("|");affichePile(*pileC);
		                printf("\n\n");
        }
	}
}