Combien de déplacements pour Hanoï ?

Combien de déplacements pour Hanoï ?

On reprend la fonction hanoi du cours, qui déplace une tour de $n$ disques. On note $u_n$ le nombre de déplacements qu'elle effectue.

• Que valent $u_0$ et $u_1$ ? Justifier que $u_n=2u_{n-1}+1$ pour $n\ge 1$.
• Écrire une fonction récursive nb_deplacements(n) qui calcule $u_n$ grâce à cette relation, puis vérifier que $u_n=2^n-1$ pour $n$ de $0$ à $10$.
• Démontrer que $u_n=2^n-1$ pour tout $n$.
• La légende parle de $64$ disques, déplacés à raison d'un par seconde. Combien de temps faudrait-il ?