TP / TICE 2


Les tours de Hanoï





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

É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ï

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.

Connectez-vous pour ajouter des favoris

Pour pouvoir ajouter ou retrouver des favoris, nous devons les lier à votre compte.Et c’est gratuit !

Se connecter

Livre du professeur

Pour pouvoir consulter le livre du professeur, vous devez être connecté avec un compte professeur et avoir validé votre adresse email académique.

Votre avis nous intéresse !
Recommanderiez-vous notre site web à un(e) collègue ?

Peu probable
Très probable

Cliquez sur le score que vous voulez donner.

Dites-nous qui vous êtes !

Pour assurer la meilleure qualité de service, nous avons besoin de vous connaître !
Cliquez sur l'un des choix ci-dessus qui vous correspond le mieux.

Nous envoyer un message




Nous contacter?