Bonsoir,
Je dois réaliser un algorithme qui doit calculer le nombre de coups minimum pour gagner une partie du jeu des tours de Hanoi.
J'ai trouvé la formule qui permet de calculer le nombres de coups minimum cependant je ne comprend pas totalement la logique de ce calcul:
Voici ce que je sais:
(2puissance_nombre_anneaux) - déplacement = nombre_coups_minimum
un exemple:
2³ - 1 = 7
Que représente 2 dans cette formule ?
Merci et désolé si c'est pas super clair.
Ps: je sais pas si c’est le forum approprié mais je savais pas trop ou demander çà.
formule =/= algorithme.
L'algo en récursif c'est ça :void deplacer (int n, int t1, int t2, int t3)
{
if ( n == 1 )
printf("De la tour %d à la tour %d\n", t1, t2) ;
else
{
deplacer (n-1, t1, t3, t2) ;
deplacer ( 1 , t1, t2, t3) ;
deplacer (n-1, t3, t2, t1) ;
}
}
La formule c'est 2^n -1. Ça se démontre trivialement par récurrence cf : https://fr.wikipedia.org/wiki/Tours_de_Hanoï