Tours de hanoi !

Soyez le premier à donner votre avis sur cette source.

Snippet vu 6 042 fois - Téléchargée 32 fois

Contenu du snippet

Pour ceux qui ne connaissent pas encore ce casse tete :

IL s'agit de déplacer un certain nombre de disques d'un piquet à un autre en utilisant un troisième piquet comme lieu de transfert temporaire, mais il ya 2 contraintes : on ne peut déplacer qu'un seul disque à la fois , et un disque de diamètre superieur ne peut se retrouver au dessus d'un disque de diamètre inférieur , la soluce simple pour résourdre ce problèmee st d'utiliser une fonction récursive parceque sinon si on choisit la methode itérative ça devient vite le bordel !

Source / Exemple :


// Auteur : Amokrane Chentir
// Programme de résolution du problème des TOURS DE HANOI !
// Algo utilisé : fonction recursive 

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

void hanoi(int ,int ,int ,int);

int main()
{
	int a,b,c,d,fin;
        

	cout<<"Programme de r\202solution du probl\212me des tours de hanoi !"<<endl;
    cout<<endl;
	cout<<"Combien y'a t'ils de disques \205 d\202placer ?"<<endl;
	cin>>a;

    cout<<"Il ya 3 piquets : 1-2-3 !"<<endl;

	cout<<"Quel est le piquet ou les disques sont initialement plac\202s ?"<<endl;
	cin>>b;

	cout<<"Quel est le piquet ou cette pile de disque va \202tre d\202plac\202 ?"<<endl;
	cin>>c;

	cout<<"Quel est le piquet servant de lieu de transfert temporaire ?"<<endl;
	cin>>d;

	hanoi(a,b,c,d);
cout<<endl;     
cout<<"Tapez une touche pour sortir !"<<endl; // Au lieu de mettre un Sleep
cin>>fin;                                     // Une manière élegante de sortir d'un programme
	return 0;
}

void hanoi(int nombre,int depart,int arrive,int transfert)
{
	if  (nombre==1)  // Le problème de base !  
	{
     	cout<<depart<< " -> " <<arrive<<endl;
		
	}

    else     // Tout le truc est la !!!
	{
		hanoi(nombre - 1,depart,transfert,arrive);
        cout<<depart<<' '<<"->"<<' '<<arrive<<endl;
		hanoi(nombre - 1,transfert,arrive,depart);

	}  // La fonction recursive quoi !

}

Conclusion :


A partir d'un certain nombre de disques , 20 par exemple il sera impossible à l'ordinateur de résoudre le problème !
Hmmm , alors imaginez un peu les pretres de l'extrême orient qui tentent de déplacer 64 disques !!!
Il leurs faudrait quoi ... euh quelques millions d'années ... et encore comme ça et c'est pas gagné pour eux !

A voir également

Ajouter un commentaire Commentaires
badrivix
Messages postés
1
Date d'inscription
lundi 27 novembre 2006
Statut
Membre
Dernière intervention
27 novembre 2006

27 nov. 2006 à 17:34
Et si on veut la methode itterative?
manta7
Messages postés
105
Date d'inscription
samedi 25 janvier 2003
Statut
Membre
Dernière intervention
13 décembre 2008

29 juin 2003 à 13:47
Merci pour ces explications.
cs_AmK
Messages postés
368
Date d'inscription
jeudi 13 mars 2003
Statut
Membre
Dernière intervention
27 janvier 2010
1
28 juin 2003 à 18:31
le but étant d'arriver à l'etat de base qui est :

if (nombre==1) // Le problème de base !
{
cout<<depart<< " -> " <<arrive<<endl;

}
cs_aardman
Messages postés
1905
Date d'inscription
mercredi 22 janvier 2003
Statut
Membre
Dernière intervention
17 septembre 2012
3
28 juin 2003 à 16:34
Salut,
Une fonction recursive c'est une fonction qui s'appelle elle meme lors de sa déclaration (dans ce programe, c'est hanoi qui est recursive).
Au debut, on appelle la fonction avec le premier paramettre egal a "nombre".
Dans la fonction, on rapelle cette meme fonction avec nombre-1, qui elle meme va se rapeller avec nombre-1 (donc ca fera nombre-2) et ainsi de suite...
Par exemple, pour 20 disques, la fonction s'appellera 20 fois.
manta7
Messages postés
105
Date d'inscription
samedi 25 janvier 2003
Statut
Membre
Dernière intervention
13 décembre 2008

28 juin 2003 à 11:08
Salut Amk, tres bien ta source mais il y a un truc que je ne comprends pas c'est la fonction recursive, pourrait tu m'expliquer stp.

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.