Difference between revisions of "Tours de Hanoï"

From GCompris
Jump to: navigation, search
 
Line 20: Line 20:
 
Ce problème a toujours une solution. Il faut pour cela utiliser la troisième tour, comme lieu de
 
Ce problème a toujours une solution. Il faut pour cela utiliser la troisième tour, comme lieu de
 
stockage temporaire.
 
stockage temporaire.
Soit U le nombre de coups, n le nombre de disques, on calcule U par : <math>U = 2^n - 1</math>.
+
Soit U le nombre de coups, n le nombre de disques, on calcule U par : U = 2<sup>n</sup> - 1.
 +
 
 
Ce qui donne pour résultats :
 
Ce qui donne pour résultats :
 
{|
 
{|

Revision as of 14:43, 8 August 2006

Le problème original

FIG. 6.2 – Tours de Hanoï : le problème classique

Problème

Ce problème a été inventé par le mathématicien Edouard LUCAS, d’après une légende hindoue. Selon cette légende, des moines sont gardiens de trois tours. 64 disques d’or concentriques, de plus en plus petits, sont empilés dans une des tours. Les moines doivent les transférer dans une autre tour, avec une règle unique : aucun disque ne doit être posé sur un plus petit. Quand il auront terminé, ce sera la fin du monde.

Une autre légende assure que ce puzzle était utilisé dans un temple pour la discipline mentale des aspirants à l’éveil. . . C’est plutôt dans cette optique que nous l’utiliserons aussi !

Régles

  • 3 poteaux ;
  • un certain nombre de disques ;
  • un déplacement à la fois ;
  • aucun disque ne peut être posé sur un disque plus petit.

Résolution

Ce problème a toujours une solution. Il faut pour cela utiliser la troisième tour, comme lieu de stockage temporaire. Soit U le nombre de coups, n le nombre de disques, on calcule U par : U = 2n - 1.

Ce qui donne pour résultats :

Disques Nombre de coups
1 1
2 3
3 7
4 15
5 31
... ...
64 18 446 744 073 709 551 615