begin process at 2012 02 13 05:34:15
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > TOURS DE HANOÏ: INTRODUCTION AUX ALGOS RÉCURSIFS.

TOURS DE HANOÏ: INTRODUCTION AUX ALGOS RÉCURSIFS.


 Information sur la source

Note :
8 / 10 - par 1 personne
8,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths & Algorithmes Niveau :Débutant Date de création :05/02/2004 Date de mise à jour :26/04/2004 10:23:32 Vu :12 568
Auteur : TeLeTUbIz

Ecrire un message privé
Commentaire sur cette source (27)
Ajouter un commentaire et/ou une note

 Description

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

  • // 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;
  • } 
// 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.


 Sources du même auteur

[STL] CONNAITRE LA TAILLE D'UN FICHIER ET COPIER DANS UN STR...
Source avec Zip TRI PAR TAS GÉNÉRIQUE. RAPIDE ET EFFICACE.
Source avec Zip 1 000 000 DE NOMBRES PREMIERS EN 0.062 SECONDES ?
POINTEURS SUR FONCTIONS
Source avec Zip Source avec une capture CRIBLE D'ERATOSTENE ET GÉNÉRATION DE PAGES WEB.
Toutes les sources de TeLeTUbIz

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel
Toutes les sources de la catégorie Maths & Algorithmes

Commentaires et avis

Commentaire de Kirua le 06/02/2004 17:38:03

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 ;-)

Commentaire de zmc le 09/02/2004 21:40:41

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

Commentaire de TeLeTUbIz le 09/02/2004 22:38:00

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)

Commentaire de Kirua le 09/02/2004 22:55:04

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)

Commentaire de TeLeTUbIz le 09/02/2004 23:10:24

oula, y'a de la tension...
Enfin, engueulez vous chez moi, tant que vous cassez rien, ca me gène pas ;-D

Commentaire de dominion le 11/02/2004 15:25:08

Peace and love les gars !

Pour info, le cotoyant tous les jours, Kirua est un grand puriste. Il est du genre à m'emmerder parce que j'ai oublié de mettre le return 0; à la fin de ma fonction int main() écrite à la craie sur un tableau !

Je suis d'accord avec zmc : du moment qu'on a l'idée... De plus, mon compilo (BCB) accepte #include &lt;iostream.h&gt; sans #using namespace std mais si je met #include &lt;iostream&gt; alors #using namespace std est nécessaire (me demandez pas pourquoi j'en sait rien)

Commentaire de Kirua le 11/02/2004 15:34:31

si tu mets #using namespace std ton compilo va rien dire parce qu'il sera même pas appelé, c'est le préprocesseur qui va gueuler ;-)

et puis faut pas dire grand puriste O_o j'essaye de respecter les standards, voilà tout. et d'ailleurs je vous enjoints tous à me le faire remarquer qd je ne respecte pas une norme.

Commentaire de dominion le 11/02/2004 15:40:55

Oui mais de là a me faire ch*** pour un return 0; sur un tableau... Enfin la rigueur toujours la rigueur... ;-)

Commentaire de zmc le 11/02/2004 18:20:40

salut dominion,
avant tout, je suis pour le code propre et le respet des standards. Je trouve simplement que c'est pas très cool de poster un commentaire uniquement pour critiquer un code, sans meme donné son avis dessus.
C'est tout.

zmc

Commentaire de TeLeTUbIz le 11/02/2004 18:36:24

Kirua a raison de respecter les normes; toutefois, la norme ne précise pas d'utilier using namespace std; seulement le standart conseil cette forme et déconseille la forme #include &lt;iostream.h&gt;
Par contre, c'est pas en dehors de la norme. On a le droit de le faire mais pour des raisons de compilation ou autre, c'est pas conseillé c'est tout.
(et ouai, depuis le post de Kirua, je suis allé me renseigné dans des bouquins sur ces using namespace, et j'ai lu un peu la norme actuelle)

Commentaire de TeLeTUbIz le 11/02/2004 18:36:40

M'enfin, sinon, le tuto, il est bien ?

Commentaire de Kirua le 11/02/2004 18:56:04

critiquer c'est pas forcément négatif, y a svt méprise là dessus. et puis pq il faut tjs donner un avis positif? armf, c une discussion qui survient trop souvent sur CS, c'est énervant. moi j'ai pas voulu être méchant enfin, relisez mon premier poste, il est agressif ??

Commentaire de zmc le 11/02/2004 19:39:25

Visiblement tu comprends pas ce que je veux dire, autant en rester la...

TeLeTUbIz &gt;&gt; ouais, sympa l'exemple

zmc

Commentaire de dominion le 11/02/2004 20:02:53

Je suis tout à fait d'accord : il faut que le code soit correctement écrit. Mais celui-ci compile et using namespace ou pas, le résultat apparent est le même. Donc dans ce cas-ci, ce n'était pas grave.

Commentaire de TeLeTUbIz le 11/02/2004 20:26:59

nan, mais Kirua à un peu raison, cela m'a permis d'apprendre ce qu'était ces fameux using namespace. Je savais pas et maintenant je sais. Ca m'avance... ;-)
Puis en fait, je l'ai pas pris comme une critique du prog, même si c'était pas le cas.

Commentaire de Hylvenir le 23/02/2004 18:08:48

Pour info, le "return 0;" à la fin du main en C++ n'est pas obligatoire.
Et c'est dans le standard. ;-)

Commentaire de surfeurnet le 08/04/2004 15:56:01

D'accord c'est l'exemple de base d'un algo récursif mais de là à ce qu'il soit niveau 3 !

Commentaire de TeLeTUbIz le 08/04/2004 18:16:40

ouai bon, je me suis peut être un peu emporté sur ca.
Mais ca reste à un niveau conceptuel plus élevé que la programmation impérative classique. Je sais plus trop pourquoi j'ai mis expert. À l'époque je devais avoir un prétexte.

Commentaire de nEUrOne le 26/04/2004 08:49:41

C'est un des premiers exemples que l'on voit en structure de données ... c'est du niveau 1 !

Commentaire de TeLeTUbIz le 26/04/2004 10:21:37

Ouai, c'est même le premier exemple que j'ai vu en Intelligence Artificielle. Mais ici tout le monde n'a pas fait d'AI ou bien de DB.
La plupart des gens qui n'en ont pas fait restent cantoné en itératif.
Alors il vaut niveau 2. Bon 3 je sais pas pourquoi j'ai mis ça, mais je reconnais que c'était trop.

Commentaire de TeLeTUbIz le 26/04/2004 10:24:16

Bon bah j'ai quand même mis niveau 1 pour faire plaisir... ;-)

Commentaire de coucou747 le 17/07/2004 20:29:41 administrateur CS

moi, je trouve ça pas mal pour aprendre comment faire une fonction ia,
Quelqu'un sait-il comment je peux implenter un truc de ce style dans un programme d'échec sans aucune struct, l'échiquier est placé dans un tableau, les fonctions d'interdit et d'autorisé sont gérés, c[x+y*8] est une case de l'échiquier, cette case vaut 1 si il y a une tour sur cette case, 2 si il y a un caval ect

C'est pas mal pour aprendre, mais ça m'aide pas directement...

Commentaire de dominion le 17/07/2004 22:56:35

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;
}

Commentaire de dominion le 17/07/2004 22:57:30

NOTE : a mon avis c'est débile comme fonction ya bcp plus simple, mais c du récursif :-D

Commentaire de coucou747 le 17/07/2004 23:06:42 administrateur CS

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é...

Commentaire de TeLeTUbIz le 18/07/2004 10:38:46

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.

Commentaire de Kirua le 19/07/2004 23:51:13

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)

 Ajouter un commentaire

Nos sponsors


Sondage...

Comparez les prix


Acer Liquid (noir) (XP.H480Q.013)
Entre 300€ et 346€

Visiter le guide achat

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode

Photothèque

Photo Green Energy Solutions With Light Bulb Morphed Into LandscapePhoto Renewable Energy is Within Reach
Photo DSLR Camera Taking a Photograph of a Sunflower Field 

Visiter la photothèque
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 5,741 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)