L?objet de ce travail est l?étude des deux méthodes de conception des algorithmes, la méthode récursive et la méthode itérative.
Source / Exemple :
/*
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)
{
}
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;
}
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");
}
}
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.