★ AMSTRAD CPC ★ GAMESLIST ★ TOURS D'HANOI (c) MICROSTRAD ★ |
MICROSTRAD |
Un programme récursif pour imiter les moines boudhistes de la légende qui empilaient et dépilaient des disques en attendant la fin du monde. Les tours de Hanoï est le nom d'un célèbre casse-tête dans lequel il s'agit de faire passer, d'un support à un autre, un certain nombre de disques de tailles différentes. La principale règle consiste à ne jamais placer un disque sur un plus petit que lui. Pour y parvenir, on a le droit d'utiliser une pile intermédiaire, une seule. Si vous l'avez déjà essayé, vous avez compris que la résolution de ce casse-tête répond à un algorithme des plus « informatisables ». Nous avons donc écrit un programme dans lequel le rôle de l'utilisateur se réduit à celui d'observateur : les disques se déplacent rapidement d'une pile à une autre et essaient de résoudre tout seuls le problème. Si la vitesse des échanges vous paraît excessive, vous pouvez modifier la ligne 820 en supprimant la première apostrophe qu'elle contient, ce qui ralentira sensiblement le débit. Pour une exécution en pas à pas, ne laissez sur cette ligne que le call & BB18 : vous aurez alors une progression au rythme de vos pressions sur les touches du clavier. L'intérêt de ce programme réside essentiellement dans la façon dont il a été rédigé : son fonctionnement est récursif. L'observation des lignes 600 à 900 vous montrera un sous-programme (il commence en ligne 630) qui s'appelle lui-même (lignes 680 et 880)... C'est là un élément visible de la récursivité. Notez que les lignes 700 à 820 ne sont là que pour les dessins à l'écran, et qu'il n'est pas utile d'en tenir compte pour comprendre comment ça marche. Sachez donc profiter du côté didactique du programme. Vous pouvez connaître la profondeur de la pile de récursion du Basic des CPC à l'aide d'une seule ligne de Basic : 10 p=p+1 : print p : gosub 10Par comparaison, celle d'un Commodore 64 n'admet que 24 niveaux de récursion. Cette profondeur intéressante permet à notre programme de résoudre le problème des tours avec près de 80 disques, ce qui représente un nombre de mouvements de disques si confortable que la vie de plusieurs générations de moines - ou de programmeurs de CPC - serait insuffisante pour en voir la fin, à la vitesse de travail du CPC. A l'écran, on ne peut visualiser plus de neuf disques, ce qui signifie tout de même 2^9-1 (soit 511) mouvements de disques. Ce nombre peut-être augmenté en supprimant les lignes 330 à 530, et les lignes 700 à 790, et en modifiant la ligne 310. MICROSTRAD n°4 |
|
|