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

Commenter

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

S'inscrire maintenant

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.

Du même auteur (TeLeTUbIz)