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

Soyez le premier à donner votre avis sur cette source.

Snippet vu 27 990 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

Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

cherche du côté des algos MiniMax et Alpha-Beta (alpha beta c'est une amélioration de minimax).

ça permet de faire remonter le meilleur mouvement à faire en prévoyant x coups à l'avance (le postulat de départ étant que l'adverseraire tentera lui aussi de tjs effecteur le meilleur coup, ce qui paraît logique, et de tte façon s'il ne le fait pas, ça augmente les chance de victoire de l'IA)
Messages postés
215
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
25 septembre 2010

Ben, on peux faire ca par force brute:
pour chaque pièce, faire chaque coup, tester si le coup est gagnant, perdant, stratégie gagnante, ou rien.
On fait ce procédé "récursivement" *.
*: bon, ici, on peux pas faire de la vraie récursion, parce que sinon le prog va bloqué comme il existe des parties infinies, donc on utilise un compteur pour la profondeur de recherche, pour chercher par exemple 10 coups d'avance.
Bon, c'est vraiment de la merde cet algo, parce que l'on sait pas déterminer si une position est mieux qu'une autre, etc...

C'est un problème vachement dur.
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
38
ah non, ça j'ai compris, mais vous avez dit que ça servais pour les ia, et en ce moment, je fais un jeu d'échec en C et un othello en javascript (il est finit mais nul, et un peu buggé)
Et donc, j'ai réussi a mettre une ia sur mon othello, mais pas sur mon jeu d'échecs, et parfois, je bat mon othello 60 a 4 ou 58 a 0 alors évodement, c'est pas récursif, il cherche juste sur un coup pour le othello, alors il est pas performant, j'aimerais savoir comment faire une ia en économisant le plus possible de mémoire. J'ai aussi fait un morpion en javascript, mais lui, est imbatable, et pas récursif, j'ai mis if (...) then joue(1) ect... il a plein de lignes comme ça, mais aux échecs, on ne peut évidement pas faire ça, étant donné le nombre de possibilitées, alors j'ai pensé a un minimax, ce qui oblige la récursivitée, (et donc, je demande de l'aide pour le placer dans le programme) J'ai vu un linux mag sur les ia de jeux d'échecs avec minimax, mais j'ai rien compris, et donc, coincé...
Messages postés
230
Date d'inscription
mardi 21 janvier 2003
Statut
Membre
Dernière intervention
15 mai 2008

NOTE : a mon avis c'est débile comme fonction ya bcp plus simple, mais c du récursif :-D
Messages postés
230
Date d'inscription
mardi 21 janvier 2003
Statut
Membre
Dernière intervention
15 mai 2008

c un peu simplifié

pour vérifier la case :

string typecase(int type, int pos)
{
string retour = "";

//tu check
if (type == 1)
retour = "cavalier";

if (type < 12) // = le nombre de pions possibles(pion, tour, cavalier, fou, roi, dame) x2 pour la couleur
{
type ++;
typecase(type, pos);
}
return retour;
}
Afficher les 27 commentaires

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.