Salut, j'ai plusieurs exercices pourriez vous m'aider à faire ce DM, je n'arrive pas du tout à comprendre !




TD 4 - Le Jeu des tours du Hanoi. Programmation

1-Regles du Jeu. Exemple

On dispose de trois piquets avec socle, numérotés 1, 2 et 3, et de n disques sont empilés sur le piquet n°1. Le but du jeu est déplacer ces n disques du piquet n°1 sur un autre, par exemple sur le piquet n°3, en respectant les règles suivantes :
-On ne déplace qu'un seul disque à la fois et le disque déplacé doit l'être sur l'un des deux autres piquets ; c'est ce que nous appellerons un déplacement ;
- Un disque ne doit jamais être placé au-dessus d'un disque plus petit que lui.
Nous désignerons pas Un le nombre minimal de déplacement nécessaires pour resoudre le probléme. Rappelons que n est le nombre de disques.

Verifiez que U1 = 1, U2 = 3 , U3 = 7

2 - Cas General

Pour resoudre le problème général, qui est de trouver Un quelque soit le nombre n de disques, on peut faire le raisonnement suivant:
Pour déplacer les n disques du piquet n°1 sur le piquet n°3, il faudra bien, à un moment donné, déplacer le plus grand du piquet n°1 au piquet n'°3.
A cet instant, les n-1 autres disques seront le piquest n°2 dans la position indiquée sur la figure.
On voit bien que le probleme peut se résoudre en trois phases :
-les n-1 premiers disques ont été places sur le piquest n°2 avec un minimum de deplacements. On aboutit à la situation de la figure ;
-on deplace le grand disque du piquet n°1 vers le n°3
-les _n-1 disques de piquet n°2 sont empilés sur le piquet n°3 avec un minimum de déplacements.

1-Expliquez pourquoi on obtient alors Un = 2U_n-1+1.
2- L'objectif est maintenant d'écrire un programme qui demande n et qui fournit Un.
Ecrivez ce programme. Ici le programme ne demande pas le premier terme, il suffit donc d'affecter 1 dans U ("1->U").
3- Calculez "à la main" U₄, U₅, U₆, U₇ et verifiez vos resultats avec votre calculatrice.

4- a) Calculez U₃₀
b) On suppose qu'il faut 5 secondes pour déplacer un disque. Combien de temps le jeu durera-t-il avec trente disques en travaillant jour et nuit ?

5- (V_n) est la suite définie pour tout entier naturel non nul n par V_n = U_n +1.
Prouvez que (V_n est une suite géometrique.
6- Exprimez V_n, puis U_n, explicitement en fonction de n.





Je posterai la suite du DM car il faut un exercice par topic !
Merci d'avance !
West Side Coast !