Algorithmes récursifs vs algorithmes itératifs

Soyez le premier à donner votre avis sur cette source.

Vue 4 170 fois - Téléchargée 420 fois

Description

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) {
  • 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"); } } }

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Copro76
Messages postés
2
Date d'inscription
mercredi 11 février 2009
Statut
Membre
Dernière intervention
23 janvier 2012
-
Code intéressant, mais je mets un gros bémol sur la présence de "goto" dans le code.
En C, et dans beaucoup de langage c'est totalement inutile et désuet.
yvesB87
Messages postés
12
Date d'inscription
samedi 18 octobre 2008
Statut
Membre
Dernière intervention
15 mai 2015
-
j'ai met ce code montrer la puissance de l'algorithme récursif par rapport au algorithme itératif, en pratique je ne sais pas beaucoup choses de langage C, mais beaucoup en théorie de l'algorithmique, merci pour la remarque.

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.