Une fois encore, notre solution est fonctionnelle, mais elle est loin d'être optimale. Nous utilisons l'algorithme classique de déplacement des tours, celui inventé pour la situation avec trois piquets, alors que nous avons quatre piquets. Bien entendu, on ne peut pas disposer librement de ce quatrième piquet puisqu'il contient l'autre pile, mais nous pouvons toujours placer le plus petit disque au sommet de l'autre pile avant d'en déplacer une.
Pour cela, il faut écrire une nouvelle fonction hanoi_rapide(hauteur,
src, libre, plein, dst)
qui déplace une pile depuis src
vers dst
en utilisant libre
pour le stockage
temporaire, après avoir placé le plus petit disque sur le piquet
plein
.
hanoi_rapide(hauteur, src, libre, plein, dst)
n'est
pas récursive. Elle place le petit disque, puis appelle la fonction
hanoi()
classique.
Ce changement améliore considérablement les performances, comme vous pouvez le constater dans le tableau. Bien entendu, cette astuce pourrait être utilisée pour l'algorithme d'interclassement, ce qui boosterait les performances exactement de la même façon.
Nombre de disques | Interclassement | Séparation lente | Séparation rapide |
5 paires | 62 mouvements | 88 mouvements | 46 mouvements |
6 paires | 126 mouvements | 183 mouvements | 82 mouvements |
7 paires | 254 mouvements | 374 mouvements | 150 mouvements |
En conclusion, nous nous contentons souvent d'une solution fonctionnelle, et nous manquons souvent des occasions d'améliorer la décomposition du problème. Vous ne devriez pas faire cela ;)