La tour de Hanoï est un jeu inventé par le mathématicien français Édouard Lucas.
Les règles sont simples :
le jeu est organisé autour de trois bâtons de bois que l'on nommera \(a\), \(b\) et \(c\) ;
sur ces bâtons on glisse des pièces circulaires de diamètres différents. Le nombre de pièces est appelé \(n\) ;
les pièces doivent toujours être empilées dans un ordre décroissant : il est interdit de poser une grande pièce sur une petite ;
à chaque étape on déplace une pièce d'un bâton à l'autre ;
initialement, les pièces sont sur le bâton \(a\). Le but du jeu est de les amener sur le bâton \(c\).
Un stratégie de résolution optimale, qui résout le problème en un nombre minimal de déplacements, repose sur l'observation suivante. Transporter \(n\) pièces du bâton \(a\) vers le \(c\) nécessite de :
transporter les \(n - 1\) pièces du dessus du bâton \(a\) vers le \(b\) ;
déplacer la plus grande pièce du bâton \(a\) vers le \(c\) ;
transporter les \(n - 1\) pièces du bâton \(b\) vers le \(c\).
L'illustration ci-dessous1 illustre la résolution du problème dans le cas \(n = 4\) :
On cherche dans cet exercice à calculer le nombre de coups minimal permettant de résoudre le problème à \(n\) pièces. On note appelle \((u_n)\) la suite définie pour \(n > 0\) et donnant le nombre de coups nécessaires à l'exécution de la stratégie proposée dans le cas de \(n\) pièces.
Écrire la fonction nb_coups qui prend en paramètre l'entier n représentant le nombre de pièces à déplacer (n>0) et renvoie le nombre de coups permettant de résoudre le problème en appliquant la stratégie décrite.
On peut montrer qu'il existe une formule permettant de calculer directement \(u_n\) à l'aide de la seule valeur de \(n\) et ce, sans utiliser par la formule de récurrence de la question précédente.
On ne fournit pas cette formule explicite, il est demandé de la conjecturer.
Écrire la fonction nb_coups qui prend en paramètre l'entier n représentant le nombre de pièces à déplacer (n>0) et renvoie le nombre de coups permettant de résoudre le problème en appliquant la stratégie décrite.
Grandes valeurs de \(n\)
La fonction demandée doit calculer explicitement la valeur cherchée sans utiliser de boucle ni de formule de récurrence.
Les tests secrets portent sur de très grandes valeurs de \(n\). Ainsi, un algorithme structuré autour d'une boucle aura pour conséquence de bloquer le navigateur.
# Tests(insensible à la casse)(Ctrl+I)