Tours de hanoï: introduction aux algos récursifs.

Soyez le premier à donner votre avis sur cette source.

Snippet vu 24 702 fois - Téléchargée 28 fois

Contenu du snippet

La puissance du récursif !!! Nicolas ne me contredirait pas.
Aujourd'hui, beaucoup d'étudiants (surtout ceux dans les maths) apprennent en premier lieu la programmation récursive et déclarative (Scheme, Prolog,...).
Le but du récursif est de programmer de façon intuitive et courte. Cela permet de faire marcher des "automates intelligents". Le programme est cours, pas toujours son temps d'exécution.
Un programme (resp. fonction) récursif est un programme (resp. fonction) qui s'appele par lui même. Par exemple, pour trouver le n-ième élément d'une liste, on dit c'est le (n-1)i-ème élément du reste de la liste. Et on fait ça jusqu'à une CONDITION d'ARRET, c'est un dire un état que l'on connait: exemple trouver l'élément 1 d'une liste.
Il existe d'autres exemple (factorielle (n)= n* factorielle (n-1) avec 0!=1; puissances, etc...).

Je vais proposer un exemple qui montrera la puissance de la programmation récursive: les tours de Hanoï.

Chaque problème peut, dans une certaine mesure, être divisé en sous problèmes.
Dans la cas de Hanoï, le problème général est le suivant:
nous disposons de trois piliers. Sur l'un d'eux, nous avons N disques en pyramide. Le but du jeu est de faire passer tout les disques sur un autre pilier. Mais attention: pas le droit de mettre un grand disque sur un petit, ni de déplacer plusieurs disque à la fois.
(* trois piliers: départ, intermédiaire, final)
Décomposons ce problème:
ss prb1: faire passer N-1 disques sur le pilier intermédiaire;
ss prb2: faire passer le Ni-ème disque sur le pilier final;
ss prb3: faire passer les N-1 disques du pilier intermédaire sur le pilier final.

On voit alors la récursivité apparaître: pour N-1 disque du départ à l'intermédiaire représente un problème décomposable:
ss prb1: faire passer N-2 sur le nouveau pilier intermédiaire,
ss prb2: faire passer....
ETC.

On résoud donc le problème facilement:
le ss prob deux demande de ne déplacer qu'un seul disque, évident (surtout que ce doit être le plus gros des disques non placés) !
Ensuite, la condition d'arrêt est lorsque le probleme est réduit à un seul disque, on le déplace, c'est tout.

Source / Exemple :


// Ce code est partiellement recopié d'un prof (M Samir Akkouche prof d'informatique à l'université Lyon1).

#include <iostream.h>
#include <conio.h>

void hanoi(char dep, char dest, char temp, int n)
{
	if(n==1)
	{
		cout << "deplacez "<< dep << "  vers  " << dest << endl;
		getch();
	}
	else
	{
		hanoi( dep, temp, dest, n-1);	// ss-problème 1
		hanoi( dep, dest, temp, 1);	// ss-problème 2
		hanoi(temp, dest,  dep, n-1);	// ss-problème 3
	}
}

int main()
{
	int nb = 8;		// Nombre de paliers à résoudre.
	hanoi( 'a','c','b',nb);
                return 0;
}

Conclusion :


dans le main:
nb est le nombre de disques à déplacer.
on appele hanoi avec 'a', 'b', 'c' les noms des trois piliers. On souhaite faire passer les disque du pilier a en c en utilisant b.

Je n'explique pas le fonctionnement du reste, car c'est déjà expliqué là haut.

Enfin, comme je suis pas du tout le pro pour les explications et si ca vous intérresse, vous pouver poser des questions, je m'efforcerais d'y répondre :)

P.S: si on regarde le nombre d'appel à la fonction et plus précisément le cas où l'on aura un seul disque à déplacer; on calculera que pour N disques il faut faire (2^N)-1 mouvements pour résoudre le problème. Il n'existe pas de solution plus optimale.

A voir également

Ajouter un commentaire

Commentaires

cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
comprends pas que ça compile, c'est iostream, pas iostream.h et il faut mettre using namespace std; en dessous des include, ou bien utiliser std::cout.

vala ;-)
cs_zmc
Messages postés
151
Date d'inscription
vendredi 26 avril 2002
Statut
Membre
Dernière intervention
26 avril 2008
-
bon exemple, 8/10

kirua : je vois que tu perd rarement une occasion de te faire remarquer...
J'imagine que le but de cette source est avant tout de demontrer une technique de programmation, pas de faire un tutorial sur les namespace...

zmc
TeLeTUbIz
Messages postés
215
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
25 septembre 2010
-
lol
d'autant plus que moi et les namespace,...
c'est pas que j'aime pas, c'est plutôt que je connais pas des masses; mais bon, je fais une lecture de mise à niveau (la prog à la fac, c'est pas appris très rigoureusement; alors faut lire des bouquins à la norme)
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
n'empeche, je maintiens que c t pas la peine d'être agressif (j'ai bien essayé de régler ça via PM avec zmc mais il a répondu ?, en postant ici il vera peut ê de quoi je parle)
TeLeTUbIz
Messages postés
215
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
25 septembre 2010
-
oula, y'a de la tension...
Enfin, engueulez vous chez moi, tant que vous cassez rien, ca me gène pas ;-D

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.