LA TOUR DE HANOÏ LA TOUR DE HANOÏ
(-; Vous avez lu les conventions ? Il vaudrait mieux !... ;-)
Ce célèbre jeu a une histoire. En ce qui concerne l'informatique,
il a été utilisé comme test dans les laboratoires de
recherches sur l'I.A.
Son principe est le suivant : nous avons 3 Tours nommées respectivement
Départ, Intermédiaire et Arrivée (ou A, B et C). Sur
la Tour A sont empilés un certain nombre (N) de Disques, du plus
grand au plus petit, de sorte à former comme une Pyramide.
Le but est de passer les Disques de la Tour A à la Tour C - en s'aidant
de l'Intermédiaire B - de manière à obtenir exactement
la même Pyramide.
La règle est que l'on ne peut placer un plus grand Disque sur un
plus petit et, évidement, ailleurs que sur une Tour.
Le problème est : comment parvenir à ce but, en suivant la
règle, en un minimum de coups (déplacement) ?
En Logo, nous aurons une procédure effectuant le travail avec
2 différents appels récursifs (le raisonnement ci-dessous
étant dit "par récurrence" : qui revient en arrière)
et le programme de présentation laissant libre le nombre (N) de Disques
avec lequel l'on désir jouer.
Toujours en Logo, si l'on veut montrer, selon le nombre (N ou n ici) de
Disque(s) choisi(s) combien de coup(s) minimum (X ici) sont nécessaire,
l'on a la solution de passer par le traitement de listes en créant
une Base de Données, ou celle de créer un compteur à
placer à l'endroit idoine sans oublier de le remettre à 0
au moment opportun !...
Alors, justement, suivant le nombre de Disque, combien de fois doit-on
effectuer de déplacement(s) ?
Soit la liste N (nombre de Disques) :
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 (...)
Nous avons la liste (certifiée exacte !) X (nombre de coups minimum)
correspondante :
0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095 (...)
Remarquable, n'est-il pas ?!... Oui, justement, mais : en quoi ?
Nous voyons que (exprimé en "franco-logo", les [] se lisant
Alors) :
SI N = N + 1 [X = X * 2 + 1]
Ce qui donne, comme première "traduction" possible :
Une "autre" approche, toujours en "franco-logo" (raisonnement avec exemple où N=2 et, donc, X=3) :
Vous désirez réellement gagner au jeu de la Tour de Hanoï ? Alors, voici un autre élément remarquable à connaître :
Si N est impair, le premier coup se fait de A en C ; si N est pair, il doit se jouer de A en B.
POUR HANOI :N :DEP :ARR :INT ;;départ, arrivée,
intermédiaire, dans cet ordre : hé-hé !...
SI EGAL? :N 0 [STOP]
HANOI - :N 1 :DEP :INT :ARR ;;ha !
EC PH PH PH PH PH [JE DEPLACE LE DISQUE] :N !
[DE LA] :DEP [A LA] :ARR
HANOI - :N 1 :INT :ARR :DEP ;;ho-ho !
FIN
POUR TOUR :N
HANOI :N [TOUR A] [TOUR B] [TOUR C]
FIN
Lancer TOUR 3 ...
Ce programme est écrit pour le Logo (LCSI) d'APPLE II+ (!...) ; il est donc indispensable de le "traduire" pour les autres versions du langage qui ne connaissent pas (la primitive ?!...) ORDINATEUR. Du coup, voir ce qu'il faut supprimer (procédures comprises) ...
Ici encore, il existent des règles précises, un but et un raisonnement mathématique remarquable (une "équation" plus classique que celle de la TOUR de HANOÏ) ; il suffit de bien lire et analyser chacune des procédures pour les subodorer, d'une part ; d'autre part ... il en existe plusieurs que je ne mentionnerais qu'en silence ...
Enfin, cette version doit tout à Cynthia SOLOMON et Seymour PAPERT (cf. Bibliographie).
POUR JEU :BAT :JOU :ADV ;;bâtonnets, joueur, adversaire
EC PH [LE NOMBRE DE BATONNETS EST :] :BAT
EC PH :JOU [, A TOI DE JOUER. QUE JOUES-TU ?]
DONNE "NOUBAT :BAT - (CAPTECOUP :JOU :BAT)
TEST :NOUBAT = 0
SIVRAI [EC PH :JOU [A GAGNE !] STOP]
JEU :NOUBAT :ADV :JOU
FIN
POUR CAPTECOUP :JOU :ADV
TEST :JOU = [ORDINATEUR] ;;computer, bilgisayar
SIVRAI [DONNE "COUP INTEL]
SIFAUX [EC PH :JOU [PRENDS 1, 2 OU 3 BATONNETS.]
SIFAUX [DONNE "COUP LISNOMBRE]
TEST MEMBRE? :COUP [1 2 3] ;;ciao les tricheurs !
SIFAUX [RETOURNE CAPTECOUP :JOU :BAT]
TEST :COUP > :BAT ;;logique : si j'ai 3 bonbons, je ne puis en
manger 7.
;;D'autant que 7 n'est pas Membre de [1 2 3]. Et toc !
SIVRAI [RETOURNE CAPTECOUP :JOU :BAT]
RETOURNE :COUP
FIN
POUR INTEL ;;pas celui des pupuces ...
DONNE "RES RESTE :BAT 4 ;;elle est là "l'astuce"
!...
SI :RES = 0 [RETOURNE 1]
RETOURNE :RES
FIN
POUR LISNOMBRE ;;Primitive dans d'autres Logo
RETOURNE PREMIER LISLISTE
FIN
POUR NIM ;;à titre d'exemple
JEU 9 "TOI "MOI
FIN
"..., cela va mieux en le disant." Sur les plans 'philosophique' et informatique, cette suite de procédures comportent bien des 'tricheries'. Il est aussi possible de rendre ce programme plus 'élégant'. Ce "Socrate" n'était qu'un amusement faisant suite à un "défi" précis. La démarche (à décrypter ; soyez patient : il faut tout lire pour suivre ! Moi même, en recopiant, j'ai eu du mal et me suis souvenu du casse-tête lors de la création de ces procédures !...) peut ouvrir sur des idées ; ce qui est un des buts de cette Compilation. Merci à Brigitte qui se souviendra avoir fréquenté le Hall du CMIRH dans les années 80 !...
POUR SAC ;;bases de données
DONNE "A [BRIGITTE OLIVIER [UNE CHAISE] SNOOPY TITI [UN SAPIN] !
[UNE ROSE]]
DONNE "A1 [1 1 4 2 2 3 3]
DONNE "B [HUMAIN ANIMAL VEGETAL OBJET]
DONNE "B1 [1 1 1 2]
DONNE "C [[MORTEL(LE)] [IMMORTEL(LE)]]
FIN
POUR SUITE :X
SI EGAL? ITEM :X :A :N [] [SUITE :X + 1 STOP]
DONNE "N1 ITEM :X :A1
DONNE "N1 ITEM :N1 :B
EC PH PH :N [EST UN] :N1
SUITE1 1
EC PH PH PH [ET UN] :N1 [EST] :N2
EC PH PH PH [DONC] :N1 [EST] :N2
FIN
POUR SUITE1 :Y
SI EGAL? ITEM :Y :B :N1 [] [SUITE1 :Y + 1 STOP]
DONNE "N2 ITEM :Y :B1
DONNE :N2 ITEM :N2 :C
FIN
POUR DEPART
SAC
EC [VOICI UNE LISTE DE SUJETS :]
EC :A
EC [ENTREZ UN NOM DE LA LISTE]
DONNE "N PREMIER LISLISTE
SI MEMBRE? :N :A [SUITE 1] [EC [CE NOM N'EST PAS DANS LA LISTE] !
DEPART]
FIN
POUR SOCRATE
VT
EC [SACHANT QUE SOCRATE EST UN HUMAIN ET QUE TOUT]
EC [HUMAIN EST MORTEL ; alors, philosophons un peu ...]
DEPART
FIN
 |
 |
 |
 |