Chargement de l'audio en cours
Plus

Plus

Les tours de Hanoï
P.29

Mode édition
Ajouter

Ajouter

Terminer

Terminer

TP / TICE 2


Les tours de Hanoï




Énoncé

Selon la légende, dans le temple de Bénarès sont plantées trois aiguilles de diamant. Le Dieu Brahmā a enfilé 64 disques d’or du plus grand au plus petit sur l’une des tiges. Les prêtres doivent déplacer ces disques d’une tige à l’autre en ne déplaçant qu’un disque à la fois sans jamais le poser sur un plus petit. La fin du monde arrivera lorsque les prêtres auront fini de déplacer ces 64 disques.

Tours de Hanoï

Questions préliminaires :
On note nn le nombre total de disques. Au départ, tous les disques sont sur la tige de gauche.
1. Pour n=1n =1 et n=2n =2, déterminer le nombre minimal de coups permettant de déplacer les disques de la tige 1 à la tige 3 .


2. Pour n=3n =3, déterminer le nombre minimal de coups en complétant les schémas ci-dessous, en indiquant le nombre de coups nécessaires pour passer d’une étape à l’autre.

Schéma tour de Hanoï


3. Pour nn \geqslant 1, on note dnd_n le nombre de déplacements nécessaires pour déplacer nn disques d’une tige à une tige voisine. En complétant le schéma ci-dessous, en déduire que dn+1=2dn+1.d_{n+1}=2d_n+1.

Schéma tour de Hanoï

Voir les réponses

Objectif

Déterminer le nombres de coups nécessaires pour déplacer les 64 disques à l’aide d’une des deux méthodes.
MÉTHODE DE RÉSOLUTION 1
CALCULATRICE

1. À l’aide de la calculatrice, donner une valeur approchée de d64.d_{64}.


Capture d'écran de calculatrice, TP tour de Hanoï

2. Sachant qu’il faut une seconde pour déplacer un disque, en déduire le nombre d’années nécessaires pour déplacer les 64 disques.


3. On définit pour tout entier n1n \geqslant 1, vn=dn+1.v_n = d_n +1.
a. Exprimer vn+1v_{n+1} en fonction de vn.v_n.

b. En déduire la nature de la suite (vn).(v_n).

c. Exprimer vnv_n puis dnd_n en fonction de n.n.

d. En déduire la valeur exacte de d64.d_{64} .
Voir les réponses
MÉTHODE DE RÉSOLUTION 2
PYTHON

On souhaite programmer un algorithme qui permet de calculer le nombre de déplacements nécessaires en fonction du nombre nn de disques.

1. Compléter le programme ci-contre permettant de répondre à l’objectif.

def Deplacement(n):
  d = 1
  if n == 1:
    return(...)
  else:
    for i in range(...):
      d = ...
    return(...)

2. Sachant qu’il faut une seconde pour déplacer un disque, exécuter le programme pour déterminer le nombre d’années nécessaires pour déplacer les 64 disques (on pourra compléter le programme précédent ou créer une autre fonction pour calculer le temps nécessaire en secondes puis en années pour déplacer nn disques).


3. On définit pour tout entier n1n\geqslant 1, vn=dn+1.v_n=d_n+1.
a. Exprimer vn+1v_{n+1} en fonction de vn.v_n .

b. En déduire la nature de la suite (vn).(v_n).

c. Exprimer vnv_n puis dnd_n en fonction de n.n.

d. Retrouver la valeur de d64d_{64} à l’aide de cette formule et vérifier qu’elle correspond bien à la valeur donnée par le programme.

Voir les réponses
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.