★ 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 10
Par 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

TOURS D'HANOI

(c) MICROSTRAD

AUTEUR: Helene Dinard

★ ANNÉE: 1986
★ LANGAGE:
★ GENRE: BASIC , REFLEXION
★ LiCENCE: LISTING

★ AMSTRAD CPC ★ DOWNLOAD ★

Aucun fichier de disponible:
» Vous avez des fichiers que nous ne possédons pas concernent cette page ?
Je participe au site:
» Vous avez des infos personnel, des fichiers que nous ne possédons pas concernent ce jeu ?
» Vous avez remarqué une erreur dans ce texte ?
» Aidez-nous à améliorer cette page : en nous contactant via le forum ou par email.

CPCrulez[Content Management System] v8.7-desktop
Page créée en 577 millisecondes et consultée 1426 fois

L'Amstrad CPC est une machine 8 bits à base d'un Z80 à 4MHz. Le premier de la gamme fut le CPC 464 en 1984, équipé d'un lecteur de cassettes intégré il se plaçait en concurrent  du Commodore C64 beaucoup plus compliqué à utiliser et plus cher. Ce fut un réel succès et sorti cette même années le CPC 664 équipé d'un lecteur de disquettes trois pouces intégré. Sa vie fut de courte durée puisqu'en 1985 il fut remplacé par le CPC 6128 qui était plus compact, plus soigné et surtout qui avait 128Ko de RAM au lieu de 64Ko.