Les tours de Hanoï linéaires

Voici une variante classique des tours de Hanoï où certains mouvements sont interdits. Plus précisément, les disques ne peuvent plus passer directement du piquet le plus à gauche au piquet le plus à droite. Le piquet central doit être utilisé dans tous les déplacements.

À part cela, le problème reste inchangé : vous devez déplacer toute la pile de disques d'une extrémité à une autre. Vous ne pouvez déplacer qu'un seul disque à la fois, et il est interdit de placer un grand disque sur un disque plus petit.

Comme dans la version classique, ce problème se résout plus facilement de manière récursive, et vous êtes tout à fait capable de trouver cette solution récursive si vous y réfléchissez suffisamment.

L'algorithme récursif habituel pour le problème classique des tours de Hanoï est de complexité 2^n-1 tandis que l'algorithme récursif habituel pour cette variante est de complexité 3^n-1.
L'algorithme récursif habituel pour le problème classique des tours de Hanoï implique deux appels récursifs enveloppant un mouvement du grand disque. L'algorithme récursif habituel pour les tours linéaires de Hanoï implique trois appels récursifs enveloppant deux mouvement de ce disque.