Tours de Hanoï

[Valentaline]

Bonjour j'ai ce dm à faire sur les suites mais je suis bloquée. Pour la question 1 j'ai trouver =1 ; =3 ; =7 car j'ai reproduit la tour mais je ne vois pas comment justifier 7 ?
S'il vous plait je suis bloquée :triste:


(désolé pour les photos mais je ne me voyais pas recopier tout ça :look2: )

[paquito]

C'est un bon exemple de raisonnement par récurrence:
S'il n'y a qu'un disque, la solution est évidente

supposons une solution trouvée pour une tour de n disques et considérons une tour de n+1 disques;
d'après l'hypothèse de récurrence, nous savons déplacer les n premiers disques sur un autre pilier, déplaçons le (n+1)°disque sur le 3° pilier et enfin déplaçons la tour de n disques sur ce 3°pilier pour obtenir la tour de n+1 disques voulu.

Nombres de coups:

Par exemple; : je mets le disque supérieur sur un 2° pilier, le disque qui reste sur le 3° pilier puis je superpose à ce disque le petit disque qui était sur le 2° pilier. Donc pour n=2, il me faut 3 coups.

n=3: je commence par déplacer les 2 disques supérieur sur un 2°pilier (3 coups) puis je déplace le plus grand disque sur le 3° pilier (1 coup) enfin je déplace la tour de 2 disques du 2° pilier sur le le 3° pilier ou se trouve déjà le plus grand disque (3 coups); donc en tout 3+1+3=7 coups .

[Valentaline]

Merci beaucoup, j'ai comprus le principe mais comment demontrer que =2 +1 ?

[paquito]

Merci beaucoup, j'ai comprus le principe mais comment demontrer que =2 +1 ?

Pour déplacer n+1 disques tu as besoin de déplacer 2 fois n disques + une fois le plus grand, ce qui te donne

[Valentaline]

Merci beaucoup, pour l'algorithme, je dois faire entrer a l'utilisateur un nombre n ? Et apres faire faire à l'algorithme =2 +1 ?

[Valentaline]

J'essaie de faire la question 4.a) mais je ne vois pas quoi rentrer dans le tableur car je n'ai pas l'expression de puisque c'est ce que je dois trouver

[Tiruxa]

J'essaie de faire la question 4.a) mais je ne vois pas quoi rentrer dans le tableur car je n'ai pas l'expression de puisque c'est ce que je dois trouver

Bonjour, utilise la relation de récurrence de la suite

Par ex:
Si tu as mis U0 dans la cellule B1 pour calculer U1 dans la cellule B2 tu écris la formule =2*B1+1

Il reste à recopier vers le bas sur les 8 lignes suivantes pour obtenir u3, u4...u10

[Valentaline]

Merci beaucoup je vais essayer pouvez vous m'aider pour l'algorithme s'il vous plait ? Je suis perdu, j'ai trouvé un algorithme sur internet mais il est vraiment trop compliqué

[Valentaline]

j'ai rempli le tableur mais je n'arrive pas a trouvé une conjecture ? Je pense à -1 parce que j'ai essayé de calculer à la main mais comment le démontrer ?

[Tiruxa]

[IMG]Je pense à -1 parce que j'ai essayé de calculer à la main mais comment le démontrer ?

En effet c'est bien cela, mais il faut le démontrer par récurrence (initialisation, hérédité, conclusion)

[Tiruxa]

Merci beaucoup je vais essayer pouvez vous m'aider pour l'algorithme s'il vous plait ? Je suis perdu, j'ai trouvé un algorithme sur internet mais il est vraiment trop compliqué

Quel type de calculatrice as tu ?

Le principe est le suivant (au 3a)

Saisir n
u prend la valeur 0
Faire de i = 1 à n
u prend la valeur 2u+1
Fin Faire
Afficher u

au (3c)

Saisir T
u prend la valeur 1
n prend la valeur 1
Faire jusqu'à avoir 2u>T
u prend la valeur 2u+1
n prend la n+1
Fin Faire
Afficher n

[paquito]

Tu peux le faire sur une calculatrice TI par exemple; pour (évident); ensuite tu doit programmer ; ce n'est pas très difficile.
Je te donne le programme:


rompt N
:1->U
:For(k,2,N)
:2U+1->U
:End
isp U

Pour n=10, on obtient 1023; je préfère te donner le programme sur calculatrice car ce sera ton outil le jour du bac.

Maintenant, pour démontrer que , tu dois d'abord vérifier au rang ; ça marche, puis sous l'hyopthèse que pour un entier , montrer que .

Or ; ça marche.

En TS tu dois savoir faire une démonstration par récurrence pas trop compliquée; c'est un des (rares) objectifs du programme!

[Valentaline]

Je n'ai pas de TI mais une calculatrice casio et j'ai le programme récurrence, j'ai entrer =2 +1 et j'ai les bons resultats merci beaucoup