Les Tours de Hanoi en JavaScript

Philippe | 17 février 2013 | Programmation | Un commentaire

Voici un petit Script Javascript utilisant la récursivité permettant de résoudre le problème des tours de Hanoï.

Quel est le principe des tours de Hanoï ?

Les tours de Hanoï sont un casse tête dans lequel il faut faire passer des disques d’une tour à une autre en respectant la condition suivante : « Un disque ne peut être posé que sur un disque plus large que lui ».

Résoudre se problème avec un raisonnement procédural est extrêmement compliqué, pourtant en utilisant la récursivité le problème devient très simple.

Sans rentrer dans le détail, la récursivité est basée sur le principe d’une fonction qui s’appelle elle-même. La difficulté est d comprendre ce que cela va faire et si cela aura une fin.

La fonction qui nous concerne, fait la chose suivante :

Déplacer le premier disque et le mettre sur la dernière tour puis déplacer le deuxième disque et le mettre sur la deuxième tour.

Et ensuite me direz-vous ?

Ensuite, c’est à la récursivité de jouer. Quelle se débrouile :). Magique non. Ici elle s’appelle 2 fois avec permutation des tours.

Le code Javascript récursif des tours de Hanoi.

Pour tester le code ci-dessous, vous pouvez utilisez les éditeurs et interpréteurs de JavaScript en ligne.

<html><head><title>Tours de Hanoi</title></head>
<body>
<h1>Tours de Hanoi</h1>
<script language="JavaScript" type="text/javascript">

// Fonction deplacer
// 4 paramètres en entrée N : nombre de disques
// tour1 tour2 tour3 le nom des trois tours supportant les disques

function deplacer( N, Tour1, Tour2, Tour3 ) {
if ( N==1 )
document.write( "Déplacer le disque de la tour " + Tour1 + " vers la tour " + Tour2 + "<br>" );
else {
// appels récurssif

deplacer( N-1, Tour1, Tour3, Tour2 );

deplacer( 1, Tour1, Tour2, Tour3 );

deplacer( N-1, Tour3, Tour2, Tour1 );
}
}

// Appel de la fonction

deplacer( 5, "A", "B", "C" );
</script>
</body></html>

J’espère que ce petit bout de code vous aura intéressé.

Share on Tumblr

Digg Digg