Bonjour j'ai du mal à commencer cet t exercice (DM).
Pouvez-vous m'aider pour les questions 1a, 1b et 2 s'il vous plaît?n'y
Pouvez-vous m'aider pour les questions 1a, 1b et 2 s'il vous plaît?n'y
More Questions From This User See All
Copyright © 2024 ELIBRARY.TIPS - All rights reserved.
Lista de comentários
Verified answer
1a) Il faut 15 manipulations pour déplacer une tour de 4 étages1b) Il faut 31 manipulations pour une tour de 5 étages
1c) On peut conjecturer que pour une tour de n étages, il faut 2^n-1 manipulations.
2) En effet, une tour de n étages est une tour de n-1 étages posée sur un disque.
Il faut donc 2^(n-1)-1 manipulations pour déplacer la tour de n-1 étages + 1 manipulation pour déplacer le dernier disque puis à nouveau 2^(n-1)-1 manipulations pour déplacer la tour de n-1 étages. Ca fait donc 2 x (2^(n-1)-1)+1= 2^n-2+1=2^n-1
En formalisant la démonstration par récurrence. a1=1=2^1-1=1 c Ca marche pour n=1.
Supposons que au rang n, an=2^n-1. Pour une tour de n+1 étage il faut déplacer la tour de n étage soit 2^n-1 déplacement puis déplacer le n+1 ème disque puis déplacer à nouveau la tour de n étages soit 2^n-1+1+2^n-1 déplacement soit 2^(n+1)-1 manipulations. Donc an+1=2^(n+1)-1