Bookmark and Share

Liens sponsorisés

Login Form



Tours de Hanoï Print E-mail
Written by Administrator   

Source : Classique (illustration : wikipedia)

Le problème des tours de Hanoï est un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de « départ » à une tour d'« arrivée » en passant par une tour « intermédiaire » et ceci en un minimum de coups, tout en respectant les règles suivantes :

  • on ne peut déplacer plus d'un disque à la fois,
  • on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

On suppose que cette dernière règle est également respectée dans la configuration de départ.

On se propose de programmer ceci de manière récursive. Vous lisez un entier n correspondant au nombre de disques et vous affichez les coups à faire pour résoudre le problème.

Exmple

  • Entrée : 3
  • Sortie :
    1 -> 3
    1 -> 2
    3 -> 2
    1 -> 3
    2 -> 1
    2 -> 3
    1 -> 3

Illustration (pour n=4):

Tours de Hanoï avec 4 disques

 

Correction : Par Ahmed Fessi

La solution de ce problème est assez claire si l’on pense à raisonner de façon récursive. Si l’on suppose que l’on
sait déjà déplacer des piles de n − 1 disques, on se rend compte que l’on sait déplacer des piles de n disques.

En Pascal
program hanoi;
(* déplacement de ’nombre’ élements du piquet ’depart’ vers le piquet
’arrivee’ en utilisant comme pivot le piquet ’intermediaire’ *)
procedure mouvement(depart, arrivee, intermediaire: char; nombre: integer);
begin
if nombre<>0 then
begin
(* on déplace les (n-1) premiers éléments vers le piquet intermédiaire *)
mouvement(depart, intermediaire, arrivee, nombre-1);
(* on déplace l’élément du dessous vers le piquet d’arrivée *)
writeln(depart, ’ -> ’, arrivee);
(* on déplace les (n-1) éléments du piquet intermédiaire vers l’arrivée *)
mouvement(intermediaire, arrivee, depart, nombre-1);
end;
end;
(* programme principal de test *)
var
n:integer;
begin
readln(n);
mouvement(’a’,’b’,’c’,n);
end.

 

En C :

#include <stdio.h>
void deplacePile(int taille, int debut, int fin, int autre)
{
   if (taille == 0)
      return;
   deplacePile(taille - 1, debut, autre, fin);
   printf("%d -> %d\n", debut, fin);
   deplacePile(taille - 1, autre, fin, debut);
}

int main()
{
   int taille;
   scanf("%d", &taille);
   deplacePile(taille, 1, 3, 2);
   return 0;
}

En PHP

function hanoi($nbr, $dep, $fin, $int)
{
  if($nbr > 0)
  {
    hanoi($nbr - 1, $dep, $int, $fin);
    echo "D".$nbr.":".$dep."->".$fin." ";
    hanoi($nbr - 1, $int, $fin, $dep);
  }
 }


En Python

def hanoi(n,de,a,par):
        if n>0:
            hanoi(n-1,de,par,a)
            print str(de),"-->",str(a)
            hanoi(n-1,par,a,de)
print """
jeu de hanoi
il s'agit de deplacer des disques
de la tour 1 vers la tour 2
"""
n=input("donner le nombre de disques : ")
hanoi(n,1,2,3)

 
 

 

Liens sponsorisés