2.3. Le probleme de Comar
2.3.1 But du chapitre
Nous allons traiter un (petit) problÉme complÉtement.
Nous appliquerons les conseils des chapitres prÅcÅdents
pour en faire une analyse approfondie avant de traduire
les algorithmes en Rexx, Pascal et Prolog. Les
premiÉres solutions Rexx et Pascal seront
"naturellement" non rÅcursives, la solution Prolog sera
forcÅment rÅcursive. Toutefois, pour bien montrer que
la rÅcursivitÅ est un mode de programmation et non pas
un "gadget", nous rÅÅcrirons les solutions Rexx et
Pascal en mode rÅcursif.
Un lecteur attentif pourra au passage (re)dÅcouvrir
Pascal, rÅflÅchir È l'ordre de prÅsentation des
programmes (maquettage en Rexx, reprise en Pascal etc.),
essayer de dÅfinir ce qui est spÅcifique È Prolog, se
faire une idÅe de l'importance des idÅes algorithmiques
et des dÅtails dus aux langages...Si l'intÅrÁt pratique
de cet exercice est limitÅ (si ce n'est d'utiliser des
chaines de caractÉres), il n'en va pas de mÁme pour la
culture et le recul qu'il est censÅ apporter sur les
langages et les modes de p rogrammation rÅcursif et
itÅratif. Nous avons choisi cet exemple parce qu'il
traite de chaines de caractÉres. Il est donc
comprÅhensible par tous, contrairement aux exercices
rÅputÅs "simples" d'algorithmique numÅrique
traditionnels. Un exercice d'arithmÅtique "ÅlÅmentaire"
comme "tester si un nombre est parfait" n'est pas
compris par qui a depuis longtemps oubliÅ les diviseurs,
les nombres premiers...
D'autre part, la gestion des chaines de caractÉres et
des mots posent des problÉmes escamotÅs par la
reprÅsentation des nombres : "oË commence et ou finit
un mot ?", "comment reconnaitre qu'un mot est valide ?"
sont des questions qui mettent en lumiÉre l'orientation
des langages : Rexx et Awk sont clairement orientÅs
texte, Pascal est orientÅ numÅrique, Prolog n'est ni
l'un ni l'autre mais plutÂt orientÅ "symbole". Les
autres traductions (en Apl,C,Dbase, Cobol, Lisp* etc.)
sont donnÅes en fin de chapitre.
2.3.2 Position du problÉme
2.3.2.1 EnoncÅ
Le problÉme de Comar consiste È Åcrire un programme qui demande une phrase et qui la "no‰lise", c'est-È-dire qui la rÅÅcrit en "arbre de No‰l" avec des mots inversÅs. Voici un exemple du dÅroulement du programme
Quelle est votre phrase ?
ceci est un test simple.
Merci. Voici son arbre de No‰l:
nu
tse tset
icec .elpmis
2.3.2.2 Remarques sur l'ÅnoncÅ
Un problÉme bien posÅ est souvent presque rÅsolu, ce qui n'est pas le cas ici ! Il faut donc bien avoir compris
- que chaque mot doit Átre retournÅ sur lui-mÁme
- que la phrase est Åcrite È partir du mot central puis de ses voisins immÅdiats,
puis des voisins des voisins etc.
- qu'on Åcrit sur la premiÉre ligne le mot central, et ensuite deux mots seulement par
ligne et en descendant.
On ne sait pas ce qu'il faut faire s'il y a un nombre pair de termes ; nous utiliserons un deuxiÉme exemple pour prÅciser ce qu'on attend alors du programme :
Quelle est votre phrase ?
quand on a un nombre pair de termes
Merci. Voici son arbre de No‰l:
erbmon
nu riap
a ed
no semret
dnauq
Le "flou" de l'ÅnoncÅ fait partie du problÉme (y compris la notion de mot, de phrase...). En fait, l'ÅnoncÅ complet Åtait "comment rÅsoudriez-vous ce problÉme si vous deviez l'enseigner en classe d'informatique (sans prÅcision du niveau des Åtudiants ou ÅlÉves) ?". Ce problÉme faisait partie d'une thÉse de troisÉme cycle (de Monsieur Cyril Comar (d'oË le nom du problÉme) sur l'informatisation de l'enseignement, l'enseignement de l'informatique et l'enseignement assistÅ (ou surveillÅ ?) par ordinateur dans l
e cadre de travaux È l'Ecole Centrale de Paris.
2.3.3 Indication de solutions
2.3.3.1 IdÅes gÅnÅrales ("informelles")
Deux thÉmes semblent se dÅgager facilement, È savoir
RETOURNER chacun des mots de la phrase sur lui-mÁme
(c'est-È-dire remplacer "tse'c" par "c'est", "lÅon" par
"noÅl"), ECRIRE ces mots retournÅs en partant du MILIEU
(È la fois de l'Åcran et de la phrase), en DESCENDANT et
en ESPACANT vers la DROITE et vers la GAUCHE,
c'est-È-dire Åcrire le mot c puis les mots c-1 et c+1,
puis les mots c-2 et c+2 etc. En tous cas, c'est ce que
suggÉre le texte ; mais on pourrait se contenter de
retourner les mots juste avan t de les Åcrire dans un
premier temps. Si ces deux idÅes (qui rÅsument des
actions) s'expriment par des VERBES, elles ne sont sans
doute pas au mÁme niveau : le problÉme du placement des
mots est primordial, celui du retournement secondaire.
On peut donc se concentrer sur l'ESSENTIEL et ignorer
les DETAILS dans un premier temps, È moins que le but de
l'exercice ne soit de traiter ces deux problÉmes en
parallÉle, ou de faire dÅcouvrir la notion de HIERARCHIE
entre problÉme et sous-problÉme. La premiÉre partie du
travail È accomplir est donc d'Åcr ire l'arbre de No‰l
des mots normaux, la seconde sera de traiter les
retournements des mot sur eux-mÁmes.
On peut se restreindre È formuler la mÅthode de rÅsolution ainsi :
ECRIRE tous les mots de la phrase en partant du MILIEU, en DESCENDANT et en ESPACANT vers la DROITE et vers la GAUCHE.
En fait, dans un tout premier temps, on peut mÁme se contenter d'afficher des nombres en arbre de No‰l, donc essayer de rÅaliser
3
2 4
1 5
ou mÁme encore, si on a peur se s'embrouiller aussi avec les numÅros des mots
1
2 3
4 5
2.3.3.2 Discussion
Transformer ces idÅes en programmes (ou fonctions,
procÅdures, prÅdicats, car bien sÃr certains langages ne
connaissent pas la notion de programme) ne peut PAS se
faire sans "idÅe prÅconµue" ou au moins inconsciente du
langage sous-jacent. Mais il faut se mÅfier des
habitudes que l'on peut avoir acquises. Ainsi, le
problÉme de retourner un mot sur lui-mÁme peut Átre
considÅrÅ comme : instantanÅ, si on dispose d'une
fonction comme reverse en Rexx ; fastidieux, si on doit
se situer au niveau du caractÉre dans le mot.
DÅtaillons ce qu'on doit Åcrire dans ce cas. On peut
travailler : a) ÅlÅgamment, en Apl par exemple, car on
peut "swapper" (permuter) 2 caractÉres d'un mÁme tableau
en une affectation simple mais multiple, sans une tierce
variable de sauvegarde, ce qui s'Åcrit : MOT [ I,J ]
<-- MOT [
J,I ] ou en utilisant les indices gÅnÅrÅs par irMOT et
retournÅs par É. On retourne alors un mot entier sur
lui-mÁme par : MOT[ ÉINDICE ] <-- MOT[ INDICE irM OT ] ou, encore plus
simplement par ÉMOT car Apl sait renverser les mots ! b)
bÁtement en boucle, dans un langage plus classique ; il
faut alors un minimum de 3 instructions pour permuter
MOT[i] et MOT[j], comme en Pascal, par exemple en
Åcrivant :
(* permutons les caractÉres d'indice i et j
dansla chaine MOT : *)
sauvegarde := MOT [ i ] ;
MOT [ i ] := MOT [ j ] ;
MOT [ j ] := sauvegarde
et le problÉme est ensuite de calculer correctement la valeur de l'indice j en fonction de i (ce qui doit Átre prÅsentÅ comme "facile" car ces indices sont symÅtriques par rapport au milieu du mot ; "prÅsentÅ" comme facile seulement car l'idÅe est simple, mais l'Åcriture complÉte est plus calculatoire).
On Åcrit alors quelquechose comme :
(* retournons MOT sur lui mÁme en permutant les
caractÉres symÅtriques par rapport au milieu du
mot ; on utlise un caractÉre de sauvegarde et on
effectue une boucle qui va jusqu'au milieu du mot *)
longueur := length( MOT ) ;
milieu := longueur div 2 ;
for i := 1 to milieu do begin
j := 1 + longueur - i
sauvegarde := MOT [ i ] ;
MOT [ i ] := MOT [ j ] ;
MOT [ j ] := sauvegarde
end ; (* for i := 1 to milieu *)
Il ne faut pas oublier de remarquer pÅdagogiquement que pour un nombre impair de caractÉres, celui du milieu n'est pas modifiÅ.
c) plus lourdement, en utilisant non plus un caractÉre de sauvegarde mais une chaine entiÉre et avec une boucle plus longue, en recopiant les ÅlÅments È partir de la fin de la chaine :
for i := 1 to longueur do begin
j := 1 + longueur - i
MOT_RENVERSE [ i ] := MOT [ j ] ;
end ; (* for i := 1 to longueur *)
MOT := MOT_RENVERSE
d) rÅcursivement, si on est capable de le faire et surtout de l'expliquer. Pour cela, on peut dire dire que retourner un Mot c'est
permuter le Premier et le Dernier caractÉre de mot
(puis) retourner le Reste du Mot
On peut aussi rajouter : retourner un seul caractÉre, c'est ne rien faire. DÅtaillant ces actions et nommant les variables associÅes, on dira que retourner Mot en Tom
- c'est appeler DÅbut le premier caractÉre de Mot
- puis appeler Fin le dernier caractÉre de Mot
- puis retourner le reste du Mot en Etser
- et enfin concatÅner Fin, Etser et DÅbut en Tom
Une rÅsolution algorithmique correcte du problÉme secondaire du retournement d'un mot sur lui-mÁme est bien sÃr de supposer qu'on dispose d'une fonction Retourne(mot) qui renvoie le mot retournÅ et de repousser È plus tard sa traduction (ou sa dÅfinition si besoin est). Nous escamotons ici le fait qu'il semble plus "naturel" de choisir une fonction plutÂt qu'une procÅdure, selon une terminologie pascaliste. Toutefois, le point important est la dÅfinition de la notion de mot ; son retournement, pour techniqu
e qu'il soit reste comme nous l'avons indiquÅ en dÅbut de paragraphe, secondaire.
2.3.3.3 Niveaux de rÅsolution et registres de langues
Ces quelques indications de solution montrent un des problÉmes fondamentaux de l'analyse et de "l'algorithmisation" des solutions : le niveau de reprÅsentation et son expression en terme d'instructions, d'actions. Si on enseigne en 6Éme ou en Terminale, les ÅlÉves ne disposent pas des mÁmes outils intellectuels que des Åtudiants du SupÅrieur ( ainsi l'appel d'une procÅdure dans une boucle peut Átre perturbant ) ; c'est aussi le cas d'un programmeur dÅbutant ou peu È l'aise dans le langage considÅrÅ. Si les
ÅlÉves ont derriÉre eux un passÅ, une expÅrience informatique, programmatique de 10 h, 100 h... ils ne seront pas rÅceptifs au mÁme vocabulaire ; ainsi une solution fastidieuse mais simple se comprend en gÅnÅral mieux et se programme, se " dÅbogue " plus facilement qu'une solution rÅcursive pourtant plus intrinsÉque (ce qui d'ailleurs n'est pas toujours possible ou parfois long... ) mais difficile È vÅrifier "pas È pas È la main" ; ceci se rÅfÉre aussi aux habituÅs du Basic, du Pascal, en opposition aux pr
ogrammeurs en Lisp, en Prolog
Le travail de l'enseignant ou du programmeur qui va communiquer son programme doit donc se situer entre ces diffÅrents registres, simplifiant puis dÅtaillant... Le travail de l'algorithmicien aussi, puisqu'il doit procÅder de la mÁme dÅmarche pour rendre son programme accessible aux autres (et È lui-mÁme au fil des annÅes !). Par exemple, on peut (et nous l'avions dÅja dit) rÅsoudre le problÉme sans retourner les mots, rÅsoudre le probleme en supposant que le retournement se fait par appel d'une fonction di
sponible dans une bibliothÉque.
Pour un programmeur chevronnÅ, les mÁmes questions se posent, suivant que les algorithmes (et donc les programmes) devront Átre relus ou non par d'autres personnes, qu'ils doivent Átre facilement modifiables ou transportables, etc. Ce problÉme de transmission est bien sÃr extra informatique, comme la notion de mot. Il ne peut donc pas Átre rÅsolu par des mÅthodes strictement informatiques. Il faut, comme souvent un consensus, de faµon È ce que le programme "couvre" une bonne parie de la rÅalitÅ. Songeons, p
ar exemple, È tous les essais non encore transformÅs de faire lire, parler, voir et traduire les ordinateurs.
2.3.3.4 Progression dans la rÅsolution
Pour rÅsoudre le problÉme de Comar, nous Åcrirons donc de faµon progressive
- un algorithme principal
- un sous algorithme qui dÅcoupe une phrase en mots
- un sous algorithme qui retourne un mot sur lui-mÁme
- un sous algorithme qui trouve le XiÉme mot
- un sous algorithme qui noÅlise (affiche les mots comme demandÅ)
Suivant le temps dont on dispose et le niveau de programmation requis, on pourra corriger ou modifier l'algorithme pour plus de efficacitÅ, de robustesse, de gÅnÅralitÅ. On pourrait notamment gÅnÅraliser È un texte, introduire des sÅparateurs autres que l'espace blanc... DÅtaillons maintenant la mise en oeuvre d'un algorithme principal basÅ sur la mÅthode :
dÅcouper la phrase en mots
afficher chaque mot (retournÅ)
- È partir du milieu (de la phrase et de l'Åcran)
- en descendant
Il va de soi qu'il faut compter les mots pour connaitre le milieu de la phrase (ou plus exactement le mot du milieu de la phrase). On doit donc Åcrire un sous algorithme que l'on nommera Compter_les_Mots. L'idÅe "dÅcouper la PHRASE en MOTS" montre la variable d'entrÅe : PHRASE, qui sera une chaine de caractÉres. On suppose ici que le langage sous-jacent connait cette notion ; par exemple en Prolog ou en Lisp, on peut traiter et raisonner sur PHRASE en tant que liste, chaine ou symbole, mais cela ne change p
as l'idÅe d'accÅder et de traiter chaque ÅlÅment de la structure...)
La (ou les ???) variable de sortie peut Átre une matrice (une liste È double entrÅe) de caractÉres dans laquelle une ligne (un ÅlÅment) represente un mot (une chaine de caractÉres). Convenons d'appeler MOT cette structure. Ce pourrait Átre un tableau indicÅ par I et J par exemple et MOT[i,j] dÅsignera donc le JÉme caractÉre du IÉme mot. Cela pose dÅjÈ quelques petits problÉmes : ou est stockÅe la longueur de chaque mot ? Faut-il la recalculer È chaque fois ? On pourrait aussi dÅfinir MOT comme un tableau È
un seul indice I ; MOT[I] dÅsignerait alors le I-Éme mot. Ou encore on peut prendre une structure d'enregistrement : MOT[I].texte dÅsignera le I-Éme mot et MOT[I].longueur sera sa longueur. La encore, se pose le problÉme de dimension ....
Une fonction "professionnelle" comme word(str,n) en REXX peut aider È comprendre que renvoyer le niÉme mot de la chaine str peut se faire en "dynamique" au lieu de dÅcouper les mots puis de les utiliser. C'est cette solution que nous utiliserons, car elle semble la plus simple È mettre en oeuvre ; de plus, cela fera moins de discussions sur les variables en entrÅe, en sortie... car il n'y a alors plus de dÅcoupage explicite È faire ! Ce n'est certainement pas la solution la plus efficace car trouver le niÉm
e mot doit certainement repasser par l'exploration de la chaine, le passage et le redÅcoupage en mots numÅro 1,2...n-1.
Bien sÃr, peu de langages ont cette fonction en interne, mais rien n'empÁche de la rÅ-Åcrire : le -Éme mot est une suite de caractÉres commencant apres le premier caractÉre non blanc suivant le mot prÅcÅdent et finissant au prochain caractÉre blanc. Cette dÅfinition (peu comprÅhensible au premier abord) est plus correcte que "toute chaine dÅlimitÅe par des espaces blancs", ou que "un mot commence aprÉs une espace blanc". Le raffinement de ces dÅfinitions a pour but de traiter des cas particuliers qui ne se
rencontrent pas È l'oral. Le tableau suivant
Phrase Nombre de mots
"oui" 1
"^non^^" 1
"et^alors?" 2
"" 0
"^^^^" 0
n'est correctement rempli que si on utilise notre dÅfinition du mot (dans les phrases, le caractÉre ^ reprÅsente un espace blanc). Tout autre dÅfinition ne compte pas correctement les mots ; pourtant, le nombre de mots est "intuitivement Åvident" pour un humain.
LÈ encore, suivant le langage sous-jacent et aussi le but recherchÅ (trouver une solution, manipuler les chaines, utiliser la rÅcursivitÅ, faire une exercice, Åcrire une procÅdure parfaite" dans une bibliothÉque...), on ira plus loin, crÅant une fonction position ou en venant utiliser seulement une boucle de parcours...
2.3.3.5 Algorithme de rÅsolution
La version minimale de l'algorithme suppose qu'on connait le nombre de mots de la phrase ; on note nbm la variable associÅe. Elle suppose aussi qu'on connait le nombre de colonnes de l'Åcran en largeur et qu'on en dÅduit la valeur de me qui signifie milieu de l'Åcran. Pour ne pas s'encombrer avec la gestion des mots, la version minimale affichera les nombres 1,2,..nbm en descendant (voir le deuxiÉme arbre de No‰l prÅcÅdent).
De la mÁme faµon, on dispose de la fonction copies(c,n) qui renvoie n copies du caractÉre c ; ainsi copies('*',5) renvoie '*****' et copies(' ',me) positionne le curseur au milieu de la ligne. L'affichage en descente est automatiquement rÅglÅ par l'instruction Åcrire. Pour Åcarter l'affichage vers la droite et vers la gauche, on gÉre la colonne de dÅbut È gauche (notÅe cdg) et la distance entre les ÅlÅments È afficher (dee). D'oË la version succinte suivante.
{ version prÅliminaire }
m <-- nbm/2
cdg <-- me -1
Åcrire copies(' ',cdg) , "1"
dee <-- 1
pour j de 1 È m
cdg <-- cdg - 3
Åcrire copies(' ',cdg),2*j,copies(' ',dee),2*j+1
dee <-- dee + 3
fin pour j de 1 È m
L'Åtape suivante consiste È sophistiquer ce premier jet, grÀce È une fonction mot(phrase,i) qui renvoie le i-Éme mot de phrase :
- on doit amÅliorer le calcul de nbm/2 qui n'est pas forcÅment un entier
- il faut remplacer "1", 2*j et 2*j+1 respectivement par le mot du centre, le
mot voisin È gauche (mvg) et le mot voisin È droite (mvd).
- on doit mettre È jour dee en tenant compte de la longueur des mots voisins
È gauche et È droite
On obtient alors la version intermÅdiaire :
{ # 1. Initialisations }
m <-- 1 + partie_entiÉre(nbm/2)
cdg <-- me -1
mdc <-- mot(phrase,m)
dee <-- longueur(mdc)
Åcrire copies(' ',cdg) , mdc
{ # 2. Passage en revue des mots }
pour j de 2 È m
mvg <-- mot(phrase,m-j+1)
mvd <-- mot(phrase,m+j-1)
lmg <-- longueur(mvg)
cdg <-- cdg - 1 - lmg
Åcrire copies(' ',cdg),mvg,copies(' ',dee),mvf
dee <-- dee + lmd + 2 + longueur(mvd)
fin pour j
Enfin, il faut rendre les noms de variables explicites. On renommera donc
nbmots la variable nbm,
milieu la variable m,
milieu_ecran la variable me,
col_debut_mot_gauche la variable cdg,
premier_mot la variable mdc
mot_a_gauche la variable mvg
mot_a_droite la variable mvd,
distance_entre_deux_mots la variable dee
Il faut Ågalement prÅvoir la demande de la phrase et le comptage des mots. Nous supposerons qu'on dispose d'une fonction mots(p) qui renvoie le nombre de mots de la phrase p. Il reste ensuite, pour finir l'exercice, È Åcrire les fonctions que nous avons supposÅes existantes, si bien sÃr on sait qu'elles ne font pas partie du langage. La mÅthode que nous avons suivie est dite "programmation descendante". C'est une mÅthode sÃre, fiable et qui assure la cohÅsion de l'ensemble du programme, qui dÅfinit parfaite
ment chaque sous algorithme...On pourra chercher dans la littÅrature classique, comment les autres mÅthodes (programmaation ascendante, linÅaire, en arbre, systÉmique...) s'appliquent et pourquoi elles sont incorrectes. Un algorithme complet possible est donc
{ Version Finale : ALGORITHME COMAR }
{ 1. demande de la phrase }
Åcrire " quelle est votre phrase ? "
lire Phrase
Nbmots <-- mots(Phrase)
{ 2.1 on Åcrit le premier mot (celui du centre)
È partir du Milieu d'un Åcran avec 80 colonnes }
Milieu_Åcran <-- 40
Milieu <-- 1 + partie_entiÉre(Nbmots/2)
Col_dÅbut_Mot_gauche <-- Milieu_Åcran - 1
premier_mot <-- mot(Phrase,Milieu)
Åcrire copies(' ',Col_dÅbut_Mot_gauche,
renverse(premier_mot)
distance_entre_deux_mots <-- longueur(premier_mot)
{ 2.2 boucle principale : on rÅcupÉre le mot È droite et le
mot È gauche, on les Åcrit et on met È jour la
distance entre les 2 mots }
pour j de 2 È Milieu
Mot_È_gauche <-- mot(PHRASE,Milieu-j+1)
Mot_È_droite <-- mot(PHRASE,Milieu+j-1)
lmg <-- longueur(Mot_È_gauche)
Col_dÅbut_Mot_gauche <-- Col_dÅbut_Mot_gauche-1-lmg
Åcrire copies(' ',Col_debut_Mot_gauche),
renverse(Mot_È_gauche),
copies(' ',distance_entre_deux_mots),
renverse(Mot_È_droite)
distance_entre_deux_mots <-- distance_entre_deux_mots
+ lmg + longueur(Mot_È_droite) + 2
finpour { j de 2 È Milieu }
2.3.4 Programmes solutions
2.3.4.1 Solution Rexx version 1
Quelques remarques prÅliminaires : 15 lignes (si on ne tient pas compte des commentaires) suffisent en REXX si on utilise un programme de type procÅdural sans rÅcursivitÅ. Cela est du au fait que REXX dispose de nombreuses "fonctions professionnelles" (Åcrites en gras). Nous avons adaptÅ le nom des variables È cause des accents (milieu_Åcran est un nom de variable incorrect, par exemple ; nous avons donc mis milieu_ecran) et au lieu d'une lecture de la phrase. Nous avons prÅfÅrÅ le passage d'un argument car
cela est plus conforme È l'esprit de Rexx.
/************************************
le problÉme de COMAR - GH, Angers
RÅf. 03/05/1987 12:34
**************************************/
/* 1) on rÅcupÉre la PHRASE, on compte le nombre de mots */
arg PHRASE
nbmots = words(PHRASE)
/* 2.1) on Åcrit le premier mot È partir du milieu de
l'Åcran */
milieu_ecran = 40
milieu = 1 + trunc(nbmots/2)
col_debut_mot_gauche = milieu_ecran - 1
premier_mot = word(PHRASE,milieu )
say copies(' ',col_debut_mot_gauche) reverse(premier_mot)
/* 2.2) on initialise la distance entre 2 mots */
distance_entre_deux_mots = length(premier_mot )
/* 3) boucle principale : on rÅcupÉre le mot È droite et le
mot È gauche, on les Åcrit, on met È jour la distance
entre les 2 mots */
do j = 2 to milieu
mot_a_gauche = word(PHRASE,milieu + 1 - j )
mot_a_droite = word(PHRASE,milieu + j - 1 )
col_debut_mot_gauche = col_debut_mot_gauche - 1
- length(mot_a_gauche)
say copies(' ',col_debut_mot_gauche),
reverse(mot_a_gauche) ,
copies(' ',distance_entre_deux_mots) ,
reverse(mot_a_droite)
distance_entre_deux_mots = distance_entre_deux_mots ,
+ length(mot_a_gauche ) + length(mot_a_droite) + 2
end /* j = 2 to milieu */
Un lecteur attentif remarquera qu'entre l'algortithme et le programme il y a eu divergence. La variable lmg (pour longueur du mot gauche) n'a pas ÅtÅ introduite dans le programme Rexx, la numÅrotation des Åtapes n'est pas la mÁme non plus. Un tel dÅcalage (dà au dÅveloppement "È chaud" sans retour È l'algorithme) est une pratique malheureusement courante. Il faut se forcer È revenir sur l'algorithme pour Åcrire
{ 1. demande de la phrase }
Åcrire " quelle est votre phrase ? "
lire Phrase
Nbmots <-- mots(Phrase)
{ on peut aussi rÅcupÅrer la phrase en tant que paramÉtre }
et corriger le programme Rexx avec les lignes
lmg = length(mot_a_gauche)
col_debut_mot_gauche = col_debut_mot_gauche - 1 - lmd
say copies(' ',col_debut_mot_gauche),
reverse(mot_a_gauche) ,
copies(' ',distance_entre_deux_mots) ,
reverse(mot_a_droite)
distance_entre_deux_mots = distance_entre_deux_mots ,
+ lmg + length(mot_a_droite) + 2
end /* j = 2 to milieu */
Le temps qu'on passe È garantir l'identitÅ entre algorithme n'est ni du temps gÀchÅ, ni du temps perdu ; c'est un temps nÅcessaire car obligatoire È une relecture future. Le calcul de la longueur du mot È gauche est stockÅ dans une variable car elle est utilisÅe au moins deux fois et cela Åvite de la recalculer. Par contre, celle du mot È droite n'Åtant utilisÅe qu'une seule fois, la stocker dans une variable ne prÅsente aucun intÅrÁt.
2.3.4.2 Solution Turbo Pascal version 1
Le programme suivant est Åcrit en TurboPascal et utilise des fonctions bibliothÉques (ou fonctions de fichier incluses) appelÅes : compte_mots, mot, copies, renverse. Ces fonctions resemblent Åtrangement aux fonctions Rexx. Et on pourrait dire que ce programme Pascal ressemble au programme Rexx, È moins que ce ne soit l'inverse ou, comme on le verra plus tard, tout se ressemble dans la diffÅrence ! Cela tient, rappelons-le È l'origine commune de ces programmes qui est l'algorithme de rÅsolution. La version
1 de ce programme est Ågalement non rÅcursive.
PROGRAM TEACHER1 ; (*************************************)
(* ProblÉme de Comar - *)
(* Version 1 non rÅcursive *)
(*************************************)
CONST milieu_ecran = 40 ;
(* reprÅsente le milieu physique de l'ecran *)
TYPE chaine = string[130] ;
VAR PHRASE : chaine ; (* phrase È utiliser *)
nbmots : integer ; (* nombre de mots dans la phrase *)
milieu : integer ; (* numÅro du mot du milieu *)
VAR j : integer ; (* indice courant de la ligne *)
premier_mot : chaine ; (* self explanatory ...
n'est-ce pas ? *)
col_debut_mot_gauche : integer ;
(* colonne È partir de laquelle on doit Åcrire le mot
de gauche *)
distance_entre_deux_mots : integer ; (* ok ?? *)
mot_a_gauche,mot_a_droite : chaine ;
(*$I TEACHER.INC *)
{ contient la dÅfinition des fonctions utilisÅes }
BEGIN (* debut du programme principal *)
(* 1) on rÅcupÉre la PHRASE, on compte le nombre de mots *)
WRITE( ' Quelle est votre phrase ? ') ;
READLN(PHRASE) ;
nbmots := compte_mots(PHRASE) ;
(* 2) on Åcrit le premier mot au milieu de l'Åcran *)
milieu := 1 + trunc(nbmots/2) ;
col_debut_mot_gauche := milieu_ecran - 1 ;
premier_mot := mot(PHRASE,milieu ) ;
WRITELN ( copies(' ',col_debut_mot_gauche),
renverse(premier_mot) ) ;
(* on initialise la distance entre 2 mots *)
distance_entre_deux_mots := length(premier_mot ) + 1 ;
(* 3) boucle principale : on rÅcupÉre le mot È droite et le
mot È gauche, on les Åcrit, on met a jour la distance
entre les 2 mots *)
FOR j := 2 TO milieu DO BEGIN
mot_a_gauche := mot(PHRASE,milieu + 1 - j ) ;
mot_a_droite := mot(PHRASE,milieu + j - 1 ) ;
col_debut_mot_gauche := col_debut_mot_gauche - 1
- length(mot_a_gauche) ;
writeln( copies(' ',col_debut_mot_gauche),
renverse(mot_a_gauche) ,
copies(' ',distance_entre_deux_mots),
renverse(mot_a_droite) ) ;
distance_entre_deux_mots := distance_entre_deux_mots
+ length(mot_a_gauche) + length(mot_a_droite) + 2
END ; (* FOR j := 2 TO MILIEU *)
END. (* program TEACHER1 *)
Le fichier inclus comprend la dÅfinition des fonctions dans l'ordre oË elle sont rencontrÅes : la fonction compte_mots puis la fonction mot puis copie et enfin renverse. Le nom court et peu explicite des variables est criticable (i pour indice de boucle est "Åvidemment" un mauvais choix). C'est pourquoi nous avons documentÅ le rÂle de chacune de ces variables.
Bien sÃr, la fonction mot suit notre dÅfinition. On notera seulement qu'elle renvoie la chaÑne vide si le mot cherchÅ n'existe pas (par exemple le mot numÅro 5 d'une phrase ne comportant que 3 mots).
function compte_mots ( PHR : chaine ) : integer ;
(* compte le nombre de mots dans PHR *)
const sep = ' ' ;
(* le seul separateur valide est " LE BLANC " *)
var nb : integer ; (* compteur des mots *)
i : integer ; (* indice de caractere dans le mot *)
begin (* de la function compte_mots *)
nb := 0 ;
PHR := PHR + sep ;
for i := 1 to length(PHR) do begin
if (PHR[i]=sep) then begin
nb := nb + 1
end (* fin de si PHR[i]=sep) *)
end ; (* for i := 1 to length(PHR) *)
compte_mots := nb
end ; (* function compte_mots *)
function mot ( PHR : chaine ; X : integer) : chaine ;
(* renvoie le Xeme mot de PHR ou vide *)
const sep = ' ' ; (*seul separateur valide "LE BLANC *)
var nb : integer ; (* compteur des mots *)
i : integer ; (* indice de caractere dans le mot *)
L : integer ; (* longueur de la chaine PHR *)
debut_mot, fin_mot : integer ;
(* indice de dÅbut et de fin du mot dans PHR *)
begin (* de la function mot *)
nb := 0 ;
PHR := PHR + sep ;
L := length(PHR) ;
i := 1 ;
while (i <= L ) and ( NB < (X-1) ) do begin
if (PHR[i]=sep) then begin
nb := nb + 1
end ; (* finsi PHR[i]=sep) *)
i := i + 1
end ; (* while ( i <= L ) and ... *)
(* le dÅbut est donc trouvÅ ; cherchons la fin *)
debut_mot := i ;
while (i<=L ) do begin
if PHR[i] <> sep then i := i + 1
else begin fin_mot := i ;
i := L + 1
end ;
end ; (* i<= L *)
if fin_mot > debut_mot
then mot := copy(PHR,debut_mot,
fin_mot -debut_mot)
else mot := ''
end ; (* function mot *)
function copies(K : char ; N : integer) : chaine ;
(* renvoie N copies du caractÉre K *)
var i : integer ; (* indice de 1 a N *)
C : chaine ; (* variable locale de transfert qui
est remplie au fur et È mesure *)
begin (* de la function copies *)
C := '' ;
for i := 1 to n do C := C + K ;
copies := C
end ; (* function copies *)
function renverse( CH : chaine ) : chaine ;
(* retourne la chaine CH sur elle mÁme *)
var i : integer ; (* ira de 1 È N *)
C : chaine ; (* variable de transfert, locale,
remplie au fur et È mesure *)
L : integer ;
(* longueur de la chaine È retourner *)
begin (* de la function renverse *)
L := length(CH) ;
C := '' ;
for i := 1 to L do begin
C := C + CH[ L + 1 - i]
end ; (* for i := 1 to n *)
renverse := C
end ; (* function renverse *)
2.3.4.3 Solution Turbo Prolog
Si on entre maintenant dans le monde de la rÅcursivitÅ, parce qu'on doit Åcrire en Prolog notre programme) on peut utiliser le programme Turbo-Prolog suivant, avec lÈ encore des prÅdicats secondaires, È savoir :
ndm pour nombre de mot ;
pm pour premier mot ;
dm pour dernier mot ;
copies comme prÅcÅdemment
renverse aussi.
Le programme principal (sans ces prÅdicats) est le suivant :
/* le problÉme de COMAR en Turbo Prolog */
domains
Nombre, NombrePrecedent, Nmots, NbmoinsUn, Longueur,
LongueurMoins2, ColonneGauche, Distance, N, SousDistance,
SousLongueurGauche, LongueurGauche, SousLongueurDroite
= integer
Phrase, Reste, Fin, Debut, Chaine, Kar, ChainePrecedente,
Mot, RevMot, PremierCar, FinDuMot, SousMot, DernierCar,
RevSousMot, OKsaufUncar, MotGauche, MotDroit,
BlancsaGauche, BlancsEntre, MotSansBlanc, Tom,
PresqueMotDroit, SousPhrase, SousMotGauche, SousMotDroit,
GaucheMot,DroitMot
= string
predicates
/* compter le nombre de mots dans une chaine */
/* exemple : ndm(N,Phrase) */
/* N est le nombre de mots dans Phrase */
ndm(integer,string)
/* trouver le premier mot d'une chaine */
/* exemple : pm(Phrase,DebutFin) */
/* Debut est le premier mot de Phrase et Fin le reste */
/* c'est le prÅdicat turbo-prolog prÅdÅfini fronttoken */
/* avec un ordre diffÅrent pour les paramÉtres */
pm(string,string,string)
/* trouver le dernier mot d'une chaine qui en contient N */
/* exemple : dm(Fin,Phrase,Nbmots) */
/* Fin est le dernier mot de Phrase qui contient Nbmots */
dm(string,string,integer)
/* recopier Nb fois Kat (un caractÉre ou une chaine) */
/* exemple : copies(Chaine,Nb,Kar) */
/* Chaine contient Nb copies de Kar */
copies(string,integer,string)
/* retourner un mot */
/* exemple : renverse(RenvMot,Mot) */
/* RenvMot contient Mot renversÅ, ex leon pour noel ... */
renverse(string,string)
/* afficher 2 mots È partir d'une position gauche et
sÅparÅs par une distance de n caractÉres blancs */
/* exemple :
afficher(Col_Gauche,Motgauche,Distance,Motdroit) */
/* pour afficher Col_Gauche espaces blancs puis Motgauche,
puis Distance espaces blancs puis Motdroit */
afficher(integer,string,integer,string)
/* afficher tous les ÅlÅments d'une phrase : */
/* sert aussi È dÅcomposer une Phrase en ses composantes ;
exemple : */
/* aff_tle(Phrase,MotGauche,ColGauche,MotDroit,Distance) */
aff_tle(string,string,integer,string,integer)
/* bien Åcrire ou "noÅliser" une phrase entrÅe */
/* exemple : bienecrire(" voila leon et ada en noel") */
/* pour rÅpondre au problÉme TEACHER de Comar */
bienecrire(string)
clauses
afficher(ColonneGauche,MotGauche,Distance,MotDroit) :-
copies(BlancsaGauche,ColonneGauche," ") ,
write(BlancsaGauche,MotGauche) ,
copies(BlancsEntre,Distance," ") ,
write(BlancsEntre,MotDroit) , nl .
aff_tle(Mot,MotSansBlanc,40,"",0) :-
ndm(1,Mot) ,
frontstr(1,Mot,_,MotSansBlanc) ,
renverse(Tom,MotSansBlanc) ,
afficher(40,Tom,0,"") .
bienecrire("") :-
write( " Mais cette phrase est vide ! ") .
bienecrire(Phrase ) :-
aff_tle(Phrase,_,_,_,_) .
aff_tle(Phrase,MotGauche,ColonneGauche,MotDroit,Distance) :-
pm(MotGauche,Phrase,Reste) ,
ndm(N,Phrase) ,
dm(PresqueMotDroit,Phrase,N) ,
concat(SousPhrase,PresqueMotDroit,Reste) ,
frontstr(1,PresqueMotDroit,_,MotDroit) ,
aff_tle(SousPhrase,SousMotGauche,SousColonneGauche,
SousMotDroit,SousDistance) ,
str_len(SousMotGauche,SousLongueurGauche) ,
str_len(MotGauche,LongueurGauche) ,
ColonneGauche = SousColonneGauche - LongueurGauche ,
str_len(SousMotDroit,SousLongueurDroite) ,
Distance = SousDistance + SousLongueurGauche
+ SousLongueurDroite ,
renverse(GaucheMot,MotGauche) ,
renverse(DroitMot,MotDroit) ,
afficher(Colonnegauche,GaucheMot,Distance,DroitMot) .
Une personne qui n'a jamais programmÅ en Prolog doit Átre surprise È la lecture de ces lignes : on n'y voit aucun test explicite, ni aucune boucle. Et pourtant Prolog n'arrÁte pas d'en faire. Une instruction comme a,b,c,... correspond È si a alors si b alors si c...
De mÁme, Åcrire
x(a) :- y.
x(b) :- z.
indique È Prolog que si x(a) peut Átre rÅalisÅ, alors y doit Átre exÅcutÅ, ou que sinon il faut essayer de voir si x(b) peut Átre rÅalisÅ. L'exÅcution du programme est rÅalisÅ en Prolog par la recherche de la satisfaction du but principal, par exemple bienecrire("Ceci est un exemple".). Prolog essaie alors "d'unifier" la dÅfinition des prÅdicats avec les valeurs rÅelles du but.
Les clauses relatives aux prÅdicats secondaires peuvent Átre les suivantes :
ndm(0,"").
ndm(Nombre,Phrase) :-
fronttoken(Phrase,_,Reste) ,
ndm(NombrePrecedent,Reste) ,
Nombre = NombrePrecedent + 1 .
pm(Debut,Phrase,Fin) :-
fronttoken(Phrase,Debut,Fin).
dm("",_,0).
dm(Fin,Fin,1).
dm(Fin,Phrase,2):-
fronttoken(Phrase,_,Fin).
dm(Fin,Phrase,Nmots) :-
fronttoken(Phrase,_,Reste) ,
NbmoinsUn = Nmots - 1 ,
dm(Fin,Reste,NbmoinsUn) .
copies("",0,_).
copies(Chaine,1,Chaine).
copies(Chaine,Nombre,Kar) :-
trace(off) ,
NbmoinsUn = Nombre - 1 ,
copies(ChainePrecedente,NbmoinsUn,Kar),
concat(ChainePrecedente,Kar,Chaine) , trace(on).
renverse("","").
renverse(Mot,Mot) :- str_len(Mot,1).
renverse(RevMot,Mot) :-
frontstr(1,Mot,PremierCar,FinDuMot),
str_len(Mot,Longueur),
LongueurMoins2 = Longueur - 2 ,
frontstr(LongueurMoins2,FinDuMot,SousMot,DernierCar),
renverse(RevSousMot,SousMot),
concat(RevSousmot,PremierCar,OKsaufUnCar),
concat(DernierCar,OKsaufUnCar,Revmot).
2.3.4.4 Solution Turbo Pascal version 2
Et si maintenant nous essayons d'Åcrire un programme Pascal rÅcursif, on peut se servir de l'Åcriture des prÅdicats Prolog comme modÉles. Cela donne :
PROGRAM TEACHER2 ; (* version rÅcursive *)
type chaine = string[130] ;
var PHRASE : chaine ; (* phrase È utiliser *)
nombre : integer ; (* de mots *)
col_debut_mot_gauche : integer ;
(* colonne È partir de laquelle on doit
Åcrire le mot de gauche *)
distance_entre_deux_mots : integer ; (* ok ?? *)
(*$I TEACHER.INC *)
(*$I TEACHER.REC *) { contient la procÅdure bienecrire }
BEGIN (* dÅbut du programme principal *)
(* on recupere la PHRASE et on appele la procedure bienecrire *)
write( ' Quelle est votre phrase ? ') ;
readln(PHRASE) ;
nombre := compte_mots(PHRASE) ;
if ( nombre mod 2 ) = 1
then bienecrire(PHRASE)
else bienecrire(PHRASE+' ')
END. (* program TEACHER2 *)
La procÅdure rÅcursive est ici la procÅdure bienecrire, mise dans le fichier Teacher.Rec. On apprÅciera l'emploi des variables locales, globales et on comparera la facilitÅ È changer le contenu des variables par rapport È Turbo-Prolog. Les fonctions, par contre, n'ont peut Átre pas ÅtÅ rÅÅcrites en rÅcursif. Nous ne donnons volontairement pas le dÅtail de leur contenu qui est dans le fichier Teacher.Inc ; on peut, par exemple, reprendre le fichier associÅ È la version 1 du programme.
On pourrait croire que le langage Pascal est plus "riche" que le langage Prolog puisqu'il dispose des deux modes rÅcursif et itÅratif. Il n'en est rien. Prolog sait gÅrer des symboles alors que Pascal ne gÉre que nombres ou des chaines de caractÉre. De plus, prolog dispose d'un mÅcanisme de gestion (ou stratÅgie d'exploration) qui lui confÉre une autonomie dont ne dispose pas Pascal. Par contre, on peut facilement Åcrire un petit interprÅteur Pascal en Prolog et un petit interprÉte Prolog en Pascal, ce qui
montre bien la puissance des deux langages.
Enfin, un programme Turbo Pascal peut appeler un module compilÅ depuis Turbo Prolog et rÅciproquement de faµon È profiter des facilitÅs que chaque langage procure, au niveau du calcul ou du raisonnement. Cette interaction, facile puisque les deux langages sont produits par la mÁme sociÅtÅ, est parfois dure È rÅaliser. Il peut Átre plus dans certains cas plus intÅressant d'Åcrire un programme unificateur (ou mÁme un .Bat) qui appelle l'un et l'autre langage.
procedure bienecrire(PHRAZ:chaine) ;
const milieu_ecran = 40 ;
var nbmots : integer ; (* nombre de mots dans la phrase *)
milieu : integer ; (* numÅro du mot du milieu *)
premier_mot : chaine ; (* self explanatory ? *)
mot_a_gauche,mot_a_droite : chaine ;
longueur_droite,longueur_gauche : integer ;
(* longueur des chaines prÅcÅdentes *)
largeur : integer ; (* taille du mot *)
sous_phrase : chaine ;
(* phrase sans mot_droit ni mot_gauche *)
begin
(* 1) on compte le nombre de mots *)
nbmots := compte_mots(PHRAZ) ;
(* s'il n'y a qu'un seul mot, c'est le milieu de la
phrase qu'on Åcrit au centre de l'ecran *)
if (nbmots<=1) then begin
col_debut_mot_gauche := milieu_ecran - 1 ;
premier_mot := PHRAZ ;
writeln (copies(' ',col_debut_mot_gauche) ,
renverse(premier_mot)) ;
distance_entre_deux_mots:= length(premier_mot ) ;
end (* du alors *)
(* sinon, on rÅcupÉre le mot È droite et le mot È gauche
qu'on Åcrit, en mettant È jour la distance entre les
2 mots *)
else begin
mot_a_gauche := mot(PHRAZ,1) ;
mot_a_droite := mot(PHRAZ,nbmots) ;
longueur_droite := length(mot_a_droite) ;
longueur_gauche := length(mot_a_gauche) ;
largeur := length(PHRAZ) - longueur_droite
- longueur_gauche-2 ;
sous_phrase := copy(PHRAZ,longueur_gauche+2,
largeur) ;
bienecrire(sous_phrase) ;
col_debut_mot_gauche := col_debut_mot_gauche - 1
- length(mot_a_gauche) ;
writeln(copies(' ', col_debut_mot_gauche),
renverse(mot_a_gauche),
copies(' ',distance_entre_deux_mots),
renverse(mot_a_droite) ) ;
distance_entre_deux_mots := distance_entre_deux_mots
+ length(mot_a_gauche )
+ length(mot_a_droite) + 2
end (* finsi nbmots = 1 *)
end ; (* procedure bienecrire *)
2.3.4.5 Solution Rexx version 2
De mÁme, REXX est capable d'utiliser la version rÅcursive suivante :
/* COMAR : version 2 */
arg PHRASE
nombre = words(PHRASE)
if (nombre/2) <> trunc(nombre/2)
then call bienecrire PHRASE
else do ; PHRASE = PHRASE "."
call bienecrire PHRASE end
/* endif */
exit
Le sous-programme est alors :
/* procÅdure rÅcursive bienecrire*/
bienecrire : procedure expose col_debut_mot_gauche,
distance_entre_deux_mots
arg PHRAZ
nbmots = words(PHRAZ)
if nbmots <= 1
then do ; milieu_ecran = 40
col_debut_mot_gauche = milieu_ecran - 1
premier_mot = PHRAZ
say copies(' ',col_debut_mot_gauche),
reverse(premier_mot)
distance_entre_deux_mots = length(premier_mot )
end
else do
mot_a_gauche = word(PHRAZ,1)
mot_a_droite = word(PHRAZ,nbmots)
longueur_gauche = length(mot_a_gauche)
longueur_droite = length(mot_a_droite)
debut = longueur_gauche + 2
fin = length(PHRAZ) - longueur_droite
- longueur_gauche - 2 )
sous_phrase = substr(PHRAZ, debut , fin )
call bienecrire(sous_phrase)
col_debut_mot_gauche = col_debut_mot_gauche - 1
- length(mot_a_gauche)
say copies(' ',col_debut_mot_gauche)
reverse(mot_a_gauche) ,
copies(' ',distance_entre_deux_mots)
reverse(mot_a_droite)
distance_entre_deux_mots = distance_entre_deux_mots ,
+ length(mot_a_gauche ) + length(mot_a_droite) + 2
end
return
La rÅÅcriture rÅcursive en Pascal ou en Rexx est quasi-naturelle : les variables globales deviennent des paramÉtres, l'ordre des instructions de la boucle principale ne change pas. C'est en fait la faµon de contrÂler la boucle qui change.
2.3.4.6 Solutions en Apl, Awk, Dbase, Cobol, C, Lisp
Pour Átre complet, nous donnons aussi des solutions non fortement commentÅes du problÉme de Comar en Apl, Awk, Dbase, Cobol, C et Lisp. On pourra ainsi apprÅcier ressemblances et diffÅrences des traductions en divers langages È partir des mÁmes algorithmes. Par contre, comme nous l'avons dÅjÈ Åcrit, nous rÅservons la traduction en SmallTalk pour le chapitre sur les styles de programmation.
Pour Apl, nous pouvons adapter un algorithme non rÅcursif. Il serait possible de dÅfinir une fonctions copies(n) en Apl avec un rÅsultat explicite (ici la variable de transfert Z), par exemple en Åcrivant
[0] Z C COPIES N
[1] Z C N ‘ ' '
mais cela aurait allongÅ le temps de dÅveloppement et n'aurait rien apportÅ. Nous avons prÅfÅrerrÅ Åcrire directement N ‘ ' ' dans le texte.
COMAR ; Phrase ; NbMots ; MilieuEcran ; Milieu ;
ColDebutGauche ; DistanceEntre ; PremierMot ; J ;
Lmg ; Mot_a_Gauche ; Mot_a_Droite
„ 1. Demande de la phrase
O C 'Quelle est votre phrase ?'
Phrase C `
„ Admettant qu'un seul espace separe les mots ...
NbMots C 1 + +/' '=Phrase
'Il y a ',(rNbMots),' mots dans la phrase <<',Phrase,'>>'
„ 2.1 On ecrit le premier mot, celui du centre a
„ partir du milieu d'un ecran de 80 colonnes
MilieuEcran C 40
Milieu C 1 + ANbMotsö2
ColDebutGauche C MilieuEcran - 1
„ pour utiliser la fonction MOT, la syntaxe est
„ n MOT Phr au lieu de MOT(Phr,n)
PremierMot C Milieu MOT Phrase
DistanceEntre C 2 + ‘PremierMot
(ColDebutGauche ‘ ' '), ÉPremierMot
„ 2.2 Boucle principale : on Åcrit le mot a droite, le
„ mot a et on met a jour la distance entre les mots
DEBUT_DE_LA_BOUCLE_SUR_J:
J C 2
ECRITMOT:
Mot_a_Gauche C (Milieu+1-J) MOT Phrase
Mot_a_Droite C (Milieu+J-1) MOT Phrase
Lmg C ‘Mot_a_Gauche
ColDebutGauche C ColDebutGauche - (1 + Lmg)
(ColDebutGauche ‘ ' '), (ÉMot_a_Gauche),
(DistanceEntre ‘ ' '), ÉMot_a_Droite
DistanceEntre C DistanceEntre + Lmg + 2 + ‘Mot_a_Droite
D (Milieu 8 J C J + 1) / ECRITMOT
La fonction Mot dÅrive d'un agorithme prÅcÅdent ; les simplifications sont dues aux focntions de base Apl. Le symbole i correspond È la fonction position : P i ' ' donne le numÅro du premier caractÉre espace dans la chaine P ; k FTXT Âte k caractÉres en dÅbut de TXT, k ETXT vient extraire les k premiers caractÉres de TXT.
[0] R C MOT P ; NBM
[1] „ renvoie le mot numero N de la phrase P
[2] NBM C 1 + +/' '=P
[3] M C''
[4] D (N>NBM) / FIN
[5] D (N=1) / EXTRAIT_MOT
[6] NESP C 1
[7] RECHERCHE_DEBUT:
[8] POSESP C P i ' '
[9] P C POSESP F P
[10] D (N>NESPCNESP+1) / RECHERCHE_DEBUT
[11] D (N=NBM) / RENVOI_DE_P
[12] EXTRAIT_MOT: POSESP C P i ' '
[13] P C POSESP E P
[14] RENVOI_DE_P:
[15] M C P
[16] FIN: R C M
En Awk, par contre, on doit dÅfinir les fonctions copies et renverse. Par contre, on peut se dispenser de la variable Phrase, de la fonction nbmots et de la fonction mot car les variables prÅdÅfinies $0, NF et $i fournissent respectivement toute la phrase, le nombre de mots et le i-Éme mot.
# COMAR
BEGIN { ARGV[1] = ""
# 1. demande de la phrase
printf " quelle est votre phrase ? "
getline < "CON"
Nbmots = NF
# 2.1 on Åcrit le premier mot
Milieu_ecran = 40
Milieu = 1 + int(Nbmots/2)
Col_debut_Mot_gauche = Milieu_ecran - 1
premier_mot = $Milieu
print copies(" ",Col_debut_Mot_gauche) \
renverse(premier_mot)
distance_entre_deux_mots = length(premier_mot)
# 2.2 boucle principale
for (j=2;j<=Milieu;j++) {
Mot_a_gauche = $(Milieu-j+1)
Mot_a_droite = $(Milieu+j-1)
lmg = length(Mot_a_gauche)
Col_debut_Mot_gauche = Col_debut_Mot_gauche-1-lmg
print copies(" ",Col_debut_Mot_gauche) \
renverse(Mot_a_gauche) \
copies(" ",distance_entre_deux_mots) \
renverse(Mot_a_droite)
distance_entre_deux_mots = distance_entre_deux_mots \
+ lmg + length(Mot_a_droite) + 2
} # finpour j de 2 a Milieu
}
# Sous-Programmes
function copies(car,nbcop, i) { # i est locale
rtc = ""
for (i=1;i<=nbcop;i++) { rtc = rtc car }
return rtc
}
function renverse(chen, k,l) {
nehc = "" ; l = length(chen)
for (k=1;k<=l;k++) { nehc = nehc substr(chen,l-k+1,1)
}
return nehc
}
Pour Dbase, on utilise l'instruction @x,y pour positionner le curseur en ligne x, colonne y. Si cette instruction est agrÅable È manipuler, on peut lui reporcher de ne pas Átre trÉs portable, par exemple, en cas de redirection des sorties vers un fichier ou vers l'imprimante. Ce n'est pas le cas des fonctions Åcrire et copies de l'algorithme qui effectuent des affichages linÅaires et progressifs.
* ==================================================
* LE PROBLEME DE COMAR EN DBASE
*===================================================
* rÅf. Algorithme COMAR, ALS - 1993,
* (voir tout le chapitre 3)
* options d'exÅcution
clear all
set talk off
set echo off
set step off
set scoreboard off
set bell off
clear
* message d'accueil, saisie de la phrase au clavier
accept 'entrer votre phrase' to phrase
read
* initialisation de variables
store 0 to nbmot
store 40 to milieuecran
clear
@3,1 say 'Voici son arbre de No‰l :'
* dÅclaration du fichier des procÅdures
set procedure to modules
* appel de la procÅdure pour compter le nombre de mots
do Comptemot with phrase,nbmot
if nbmot>0
* on initialise les variables pour afficher
* le premier mot :
milieu=INT(nbmot/2)+1
cdg=milieuecran-1
mot=''
inverse=''
* on affiche le premier mot
do RenMOT with phrase, milieu,mot
do RENVERSE with mot,inverse
@5,cdg say inverse
* on initialise la distance entre deux mots :
dee=LEN(mot)+1
k=2 && compteur Åquivalent de la boucle pour
cd=milieu+1
cg=milieu-1
* indice de la ligne d'affichage sur l'Åcran
ligne=6
do while (k<= nbmot)
if (cg>=1)
* affichage du mot gauche
motgauche=''
inverseg=''
do RenMOT with phrase,cg,motgauche
do RENVERSE with motgauche,inverseg
cdg=cdg-LEN(motgauche)-1
@ligne,cdg say inverseg
endif
if (cd<=nbmot)
* affichage du mot droit
motdroit=''
inversed=''
DO RenMOT with phrase, cd,motdroit
do RENVERSE with motdroit,inversed
* initialisation de la colonne du mot È droite
cdd=cdg+LEN(motgauche)+dee+2
@ligne,cdd say inversed
* incrÅmentation des compteurs
dee=dee+LEN(motgauche)+LEN(motdroit)+2
endif
ligne=ligne+1
cd=cd+1
cg=cg-1
k=k+1
enddo * boucle tant que
endif * si nbmot > 1
close procedure
ligne = ligne + 1
@ligne, 1 say ""
return
clear all && fin du programme
Nous fournissons maintenant le dÅtail des procÅdures dans l'ordre oË elles sont apparues dans le corps du texte principal :
PROCEDURE Comptemot
PARAMETERS chaine,nbmot
* Ålimination des espaces inutiles en dÅbut et en fin
* de chaine :
chaine=RTRIM (chaine)
chaine=LTRIM (chaine)
i=1
chaine = chaine + ' '
IF chaine=' '
nbmot=0
* cela veut dire que la chaine n'est constituÅe
* que de l'espace introduit volontairement
ELSE
DO WHILE (i<=LEN(chaine))
IF ( SUBSTR(chaine,i,1)=' ')
nbmot=nbmot+1
i=i+1
ELSE
i=i+1
ENDIF
ENDDO
ENDIF
RETURN
PROCEDURE RenMOT
* renvoie le mot numÅro n de chaine
PARAMETERS chaine,n,mot
c=0
STORE LEN(chaine) TO l
i=1
DO WHILE (i<=l) .and. (c<(n-1))
IF (SUBSTR(chaine,i,1)=' ')
c=c+1
ENDIF
i=i+1
ENDDO
STORE i TO debut
DO WHILE (i<=l) .and. (SUBSTR(chaine,i,1)<> ' ')
i=i+1
ENDDO
fin=i
IF (fin>debut)
mot=SUBSTR(chaine, debut, fin-debut)
ENDIF
RETURN
PROCEDURE Renverse
PARAMETERS chaine,inverse
STORE LEN(chaine) TO j
* on concatÉne chacune des lettres en partant de la
* derniÉre et en allant È la premiÉre :
DO WHILE (j>0)
inverse=inverse+SUBSTR(chaine,j,1)
j=j-1
ENDDO
RETURN
En langage Cobol, le programme devient presque un problÉme de gestion. Ce programme, comme le prÅcÅdent en Dbase est trÉs lisible et long, car il utilise des mots qu'on pourrait qualifier d'usuels. Ainsi, les symboles cabalistiques comme := ou <-- sont remplacÅs par des MOVE ou des COMPUTE.
* Comar en COBOL
*
IDENTIFICATION DIVISION.
PROGRAM-ID. COMAR.
AUTHOR. GH.
DATE-COMPILED.
*
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
SOURCE-COMPUTER. IBM.
OBJECT-COMPUTER. IBM.
*
DATA DIVISION.
WORKING-STORAGE SECTION.
77 PHRASE PIC X(80) .
77 CHAINE PIC X(80) .
77 PHRASE2 PIC X(80) .
01 CHAINEVIDE .
02 ELT OCCURS 80 TIMES PIC X.
01 MOT-PHRASE.
02 MOT1 OCCURS 80 TIMES PIC X(80).
02 MOT2 OCCURS 80 TIMES PIC X(80).
01 MT.
02 CHMT OCCURS 80 TIMES PIC X .
01 INVERSE.
02 CHINV OCCURS 80 TIMES PIC X.
01 MOTGAUCHE.
02 CHMG OCCURS 80 TIMES PIC X .
01 MOTDROIT.
02 CHMD OCCURS 80 TIMES PIC X .
01 PREMIERMOT.
02 CH1 OCCURS 80 TIMES PIC X .
01 ESPACES.
02 ESPACE OCCURS 80 TIMES PIC X .
77 MOTCOUR PIC X(80) .
77 NB PIC 99 .
77 NESPA PIC 99 .
77 LONG PIC 99 .
77 I PIC 99 .
77 N PIC 99 .
77 J PIC 99 .
77 ME PIC 99 VALUE 40 .
77 MILIEU PIC 99 .
77 CDG PIC 99 .
77 CDD PIC 99 .
77 DEE PIC 99 .
77 COLONNE PIC 99 .
77 CG PIC 99 .
77 CD PIC 99 .
77 NBITER PIC 99 .
*
PROCEDURE DIVISION.
PRINCIPAL.
* saisie de la phrase entrÅe par l'utilisateur
DISPLAY "ENTRER VOTRE PHRASE" .
ACCEPT CHAINE .
DISPLAY "VOICI SON ARBRE DE NOEL :".
MOVE " " TO PHRASE .
STRING CHAINE "-" DELIMITED BY ' ' INTO CHAINE.
STRING PHRASE CHAINE DELIMITED BY " " INTO PHRASE.
MOVE 1 TO I.
PERFORM INITIALISE 80 TIMES.
PERFORM NBMOT.
IF NB > 0
PERFORM AFFICHAGE.
STOP RUN.
Ce programme Cobol a lui aussi des sous-programmes :
NBMOT.
* module permettant de compter le nombre de
* mots dans une phrase
MOVE 0 TO NESPA.
MOVE 0 TO NB.
INSPECT PHRASE TALLYING NB FOR ALL SPACE BEFORE "-" .
INSPECT CHAINE TALLYING NESPA FOR ALL SPACE.
IF NESPA EQUAL 79
COMPUTE NB = 0.
MOT.
* module renvoyant le n-iÉme mot d'une phrase
MOVE CHAINEVIDE TO MOT1(1).
IF N = 0 OR N = 1
UNSTRING CHAINE DELIMITED BY SPACE OR "-"
INTO MOT1(1)
ELSE
MOVE CHAINEVIDE TO PHRASE2.
MOVE "-" TO PHRASE2
STRING PHRASE2 PHRASE DELIMITED BY "-"
INTO PHRASE2
PERFORM DECOUPAGE N TIMES.
DECOUPAGE.
* sous_module du module mot servant È dÅcouper
* une phrase en deux
UNSTRING PHRASE2 DELIMITED BY SPACE OR "-"
INTO MOT1(2) MOT1(1).
INSPECT PHRASE2 REPLACING FIRST SPACE BY "@" .
RENVERSE.
* renverse les lettres d'un mot
MOVE CHAINEVIDE TO INVERSE.
MOVE CHAINEVIDE TO MT.
MOVE MOT1(1) TO MT.
MOVE 0 TO LONG.
INSPECT MT TALLYING LONG FOR CHARACTERS
BEFORE INITIAL SPACE.
MOVE 1 TO I .
MOVE LONG TO J .
PERFORM RENVERSE1 LONG TIMES.
RENVERSE1.
* boucle servant È inverser les lettres
MOVE CHMT(J) to CHINV(I).
COMPUTE J = J - 1.
COMPUTE I = I + 1.
INITIALISE.
MOVE SPACE TO ELT(I).
COMPUTE I = I + 1.
COPIES.
MOVE "~" to ESPACE(colonne).
STRING ESPACES MOTCOUR DELIMITED BY "~" INTO ESPACES.
AFFICHAGE.
* fonction principale (de l'affichage no‰lisÅ)
COMPUTE MILIEU ROUNDED = (NB + 1) / 2 .
MOVE MILIEU TO N.
COMPUTE CDG = ME - 1.
PERFORM MOT .
PERFORM RENVERSE.
MOVE INVERSE TO PREMIERMOT.
MOVE CDG TO COLONNE.
MOVE PREMIERMOT TO MOTCOUR.
MOVE CHAINEVIDE TO ESPACES.
PERFORM COPIES.
DISPLAY ESPACES .
COMPUTE DEE = LONG.
COMPUTE CDD = ME .
COMPUTE CG = MILIEU .
COMPUTE CD = MILIEU .
COMPUTE NBITER = MILIEU - 1.
PERFORM SAISIE NBITER TIMES.
Il reste enfin È donner le dÅtail du module de saisie. Nous avons Åcrit celui-ci comme les autres, avec peu de connaissances en Cobol, ce qu'auront remarquÅ les professionnels de ce langage. En particulier, nous n'avons utilisÅ aucune astuce, mais nous avons plutÂt voulu rester fidÉle aux algorithmes et concevoir un programme lisible.
SAISIE.
COMPUTE CDD = CDD + DEE + 1
MOVE CHAINEVIDE TO ESPACES.
COMPUTE CG = CG - 1.
MOVE CG TO N.
PERFORM MOT.
PERFORM RENVERSE.
MOVE INVERSE TO MOTGAUCHE.
COMPUTE CDG = CDG - LONG - 2.
MOVE CDG TO COLONNE.
MOVE CHAINEVIDE TO MOTCOUR.
MOVE MOTGAUCHE TO MOTCOUR.
PERFORM COPIES.
COMPUTE DEE = DEE + LONG.
COMPUTE CD = CD + 1.
IF CD < NB OR CD = NB
MOVE CD TO N
PERFORM MOT
PERFORM RENVERSE
MOVE INVERSE TO MOTDROIT
MOVE CDD TO COLONNE
MOVE CHAINEVIDE TO MOTCOUR
MOVE MOTDROIT TO MOTCOUR
PERFORM COPIES
MOVE LONG TO DEE .
DISPLAY ESPACES.
L'Åcriture en C itÅratif nous ramÉne È une traduction plus proche des algorithmes :
/*************************************/
ProblÉme de Comar en C - Version 1 non rÅcursive
/*************************************/
#include
#include
#include
#define milieu_ecran 40
typedef char chain[80] ;
/* reprÅsente le milieu physique de l'ecran */
chain PHRASE ; /* phrase È utiliser */
int nbmots ; /* nombre de mots dans la phrase */
int milieu ; /* numÅro du mot du milieu */
int j ; /* indice courant de la ligne */
chain premier_mot ; /* self explanatory ...*/
int col_debut_mot_gauche ;
/* colonne È partir de laquelle on doit Åcrire
le mot de gauche */
int distance_entre_deux_mots ;
chain mot_a_gauche,mot_a_droite ;
void main()
{ /* 1) on rÅcupÉre la PHRASE, on compte ses mots */
printf(" Quelle est votre phrase ? ") ;
gets(PHRASE) ;
nbmots = Compte_Mots(PHRASE) ;
/* 2) on Åcrit le premier mot au milieu de l'Åcran */
milieu = 1 + nbmots/2 ;
col_debut_mot_gauche = milieu_ecran - 1 ;
premier_mot[0] = '\0' ;
strcat(premier_mot,mot(PHRASE,milieu)) ;
printf("\n%s%s", Copies(" ",col_debut_mot_gauche),
strrev(premier_mot)) ;
/* on initialise la distance entre 2 mots */
distance_entre_deux_mots = strlen(premier_mot ) + 1 ;
/* 3) boucle principale : on rÅcupÉre le mot È droite et
le mot È gauche, on les Åcrit, on met a jour la
distance entre les 2 mots */
for (j = 2 ; j <= milieu ; j++) {
mot_a_gauche[0] = '\0' ;
strcat(mot_a_gauche,mot(PHRASE,milieu + 1 - j) ) ;
mot_a_droite[0] = '\0' ;
strcat(mot_a_droite,mot(PHRASE,milieu + j - 1) ) ;
col_debut_mot_gauche = col_debut_mot_gauche - 1
- strlen(mot_a_gauche) ;
printf("\n%s %s",Copies(" ",col_debut_mot_gauche),
strrev(mot_a_gauche)) ;
printf("%s %s",Copies(" ",distance_entre_deux_mots),
strrev(mot_a_droite)) ;
distance_entre_deux_mots = distance_entre_deux_mots
+ strlen(mot_a_gauche) + strlen(mot_a_droite) + 2 ;
} ; /* FOR j := 2 TO MILIEU */
printf("\n") ;
} /* program TEACHER1 */
Les fonctions (sous-programmes) utilisÅes sont ici :
char* SousChaine(chain chai,int debut,int lon){
/* renvoie une souschaine de longueur lon È
partir de la position debut */
chain substrg ;
int i ; /* indice courant dans chai */
int z ; /* indice courant dans substrg */
z=0 ;
i=debut ;
while ( (i<=(debut+lon)) && (i<=strlen(chai) ) ){
substrg[z]=chai[i] ;
++z ; ++i ;
} /* fin du while */
substrg[z] = '\0' ;
return substrg ;
} /* fin de la fonction SousChaine */
int Compte_Mots(PHR)
/* compte le nombre de mots de PHR */
chain PHR ;
{ /* le seul separateur valide est " LE BLANC " */
#define sep ' '
#define sepc " "
int nb ; /* compteur des mots */
int i ; /* indice de caractere dans le mot */
nb = 0 ;
strcat(PHR,sepc) ;
for (i = 1 ; i <= strlen(PHR) ; i++) {
if ((PHR[i]==sep)) { nb = nb + 1 ; }
/* fin de si PHR[i]=sep) */
} /* for i := 1 to length(PHR) */
return nb ;
} /* function Compte_Mots */
char* mot(chain PHR,int X)
{ /* renvoie le Xeme mot de PHR ou vide */
#define sep ' '
#define sepc " "
/*seul separateur valide "LE BLANC */
int nb ; /* compteur des mots */
int i ; /* indice de caractere dans le mot */
int L ; /* longueur de la chaine PHR */
int debut_mot, fin_mot ;
/* indice de dÅbut et de fin du mot dans PHR */
chain motr ; /* mot renovyÅ */
nb = 0 ;
strcat(PHR,sepc) ;
L = strlen(PHR) ;
i = 0 ;
while ((i <= L ) && ( nb < (X-1) ) ) {
if ((PHR[i]==sep)) { nb = nb + 1 ; }
/* finsi PHR[i]=sep) */
i = i + 1 ;
} /* while ( i <= L ) and ... */
/* le dÅbut est donc trouvÅ ; cherchons la fin */
debut_mot = i ;
while ((i<=L ) ) {
if (PHR[i] != sep) i = i + 1 ;
else { fin_mot = i ;
i = L + 1 ;
}
} /* i<= L */
motr[0]='\0' ;
if (fin_mot > debut_mot) {
strcat(motr,SousChaine(PHR,debut_mot,fin_mot-debut_mot)) ;}
return motr ;
} /* function mot */
char* Copies(char* K,int N){
/* crÅe une chaine de n fois la chaine k */
int i = 0 ; /* indice de 1 a N */
chain C ; /* variable locale de transfert qui est
remplie au fur et È mesure */
printf("%s",K) ;
C[0]='\0' ;
while (i!=N) { strcat(C,K) ; i++ ;
} /* fin du while */
C[i]='\0' ;
return C ;
} /* fin de la fonction Copies */
Une remarque, toutefois pour le choix des fonctions : nous n'avons pas rÅÅcrit la fonction renverse car elle existe dÉjÈ en Turbo C (mais aussi dans d'autres versions) ; elle se nomme strrev et se trouve dans le "header" string.h ; puisque le langage C permet une Åcriture rÅcursive, pourquoi nous priver d'une telle version ? Nous ne donnons ici que le corps du programme principal, puisque les autres fonctions sont les mÁmes.
/******************************************/
ProblÉme de Comar en C - Version 2 rÅcursive
/*****************************************/
#include
#include
#include
typedef char chain[80];
#define milieu_ecran 40 /* reprÅsente le milieu physique de l'ecran */
chain PHRASE; /* phrase È utiliser */
int nombre; /* de mots */
int col_debut_mot_gauche;
/* colonne È partir de laquelle on doit
Åcrire le mot de gauche */
int distance_entre_deux_mots; /* ok ?? */
/*$I Comarc.Inc*/
/* on y trouve : SousChaine CompteMots mot Copies */
void bienecrire(chain PHRAZ)
{ int nbmots; /* nombre de mots dans la phrase */
int milieu; /* numÅro du mot du milieu */
chain premier_mot; /* self explanatory ? */
chain mot_a_gauche,mot_a_droite;
int longueur_droite,longueur_gauche;
/* longueur des chaines prÅcÅdentes */
int largeur; /* taille du mot */
chain sous_phrase;
chain rep ;
chain PHRZ ;
/* phrase sans mot_droit ni mot_gauche */
/* 1) on compte le nombre de mots */
nbmots = Compte_Mots(PHRAZ) ;
/* s'il n'y a qu'un seul mot, c'est le milieu de la
phrase qu'on Åcrit au centre de l'ecran */
if ((nbmots<=1)) {
col_debut_mot_gauche = milieu_ecran - 1 ;
premier_mot[0] = '\0' ;
strcat(premier_mot,PHRAZ) ;
printf("\n%s%s", Copies(" ",col_debut_mot_gauche),
strrev(premier_mot)) ;
distance_entre_deux_mots= strlen(premier_mot ) + 1 ;
} /* du alors */
/* sinon, on rÅcupÉre le mot È droite et le mot È
gauche qu'on Åcrit, en mettant È jour la distance
entre les 2 mots */
else {
mot_a_gauche[0] = '\0' ;
strcat(mot_a_gauche,mot(PHRAZ,1) ) ;
mot_a_droite[0] = '\0' ;
strcat(mot_a_droite,mot(PHRAZ,nbmots) ) ;
longueur_droite = strlen(mot_a_droite) ;
longueur_gauche = strlen(mot_a_gauche) ;
largeur = strlen(PHRAZ) - longueur_droite
- longueur_gauche - 2 ;
sous_phrase[0] = '\0' ;
strcat(sous_phrase,SousChaine(PHRAZ,longueur_gauche+1,
largeur-1)) ;
bienecrire(sous_phrase) ;
col_debut_mot_gauche = col_debut_mot_gauche - 1
- strlen(mot_a_gauche) ;
printf("\n%s%s", Copies(" ",col_debut_mot_gauche)
,strrev(mot_a_gauche)) ;
printf("%s%s" , Copies(" ",distance_entre_deux_mots)
,strrev(mot_a_droite)) ;
distance_entre_deux_mots = distance_entre_deux_mots
+ strlen(mot_a_gauche )+ strlen(mot_a_droite) + 2;
} /* finsi nbmots = 1 */
return ;
} /* procedure bienecrire */
void main()
{ /* dÅbut du programme principal */
/* on recupere la PHRASE et on appele la
procedure bienecrire */
printf(" Quelle est votre phrase ? ") ;
gets(PHRASE) ;
nombre = Compte_Mots(PHRASE) ;
if (( nombre % 2 ) == 1) bienecrire(PHRASE);
else bienecrire(strcat(PHRASE," ")) ;
} /* program TEACHER2 */
Continuons maintenant par un programme (on dit plutÂt lÈ encore une fonction) Lisp ; l'appel de cette fonction se fait simplement par (comar) :
; COMAR en LELisp
;
( de comar ()
( print "quelle est votre phrase ? " )
( setq phrase ( read ) )
( setq phrase ( catenate phrase ( readline ) " " ) )
( tycls)(tycursor 0 0)
( print "Merci. Voici votre phrase pour vÅrification")
( print phrase)
( print " Voici son arbre de no‰l")
( cond
( (= ( modulo (nb_mots phrase 0) 2 ) 1 )
(affich phrase ) )
( t (affich (catenate phrase " ")) )
) ; fin du cond
( print "")
) ; fin de la fonction principale
Les fonctions (sous-programmes) associÅes sont
; comptage du nombre de mots dans la phrase: È partir du
; nombre d'espaces on dÅtermine le nombre de mots
( de nb_mots (chaine i)
; si la fonction est utilisÅe sans la fonction (comar)
; il faut concatÅner un espace au dÅbut de la phrase
( cond
( ( = i ( slen chaine ) ) 0 )
( ( eqstring " " ( substring chaine i 1) )
(+ 1 (nb_mots chaine (+ i 1))) )
( t (nb_mots chaine (+ i 1)) )
) ; fin du cond
) ; fin de la fonction nb_mots
;
; dÅtermine s'il existe un espace dans la chaine
( de espace (chaine i )
( cond
( (= i (slength chaine) ) 0 )
( (eqstring " " (substring chaine i 1) ) (+ i 1) )
( t (espace chaine (+ i 1)) )
) ; fin du cond
) ; fin de la fonction espace
;
; position du premier caractÉre du niÉme mot d'une chaÑne
( de debut ( chaine n i )
( cond
(( = n 1 ) i )
(t (debut(substring chaine(espace chaine 0))(- n 1)
( + i ( espace chaine 0 ) ) ) )
) ; fin du cond
) ; fin de la fonction debut
; position du dernier caractÉre du niÉme mot d'une chaÑne
( de fin ( chaine n i )
( cond
(( = ( + n 1 ) 1 ) ( - i 1 ) )
(t (fin(substring chaine(espace chaine 0))(- n 1)
( + i ( espace chaine 0 ) ) ) )
))
;
; renvoie le niÉme mot d'une chaine
( de mot ( chain n )
(substring chain(debut chain n 0)
(- (fin (catenate chain " " ) n 0)
(debut chain n 0 ) ) )
) ; fin de la fonction mot
;
; renverse les lettres d'un mot
( de renverse ( ch )
( cond
(( = (slength ch ) 0 ) "" )
(t (catenate (substring ch (-(slength ch) 1) 1)
(renverse (substring ch 0 (- (slength ch )1)))))
) ; fin du cond
) ; fin de la fonction renverse
;
; crÅation de n espaces blancs
( de copies ( n )
( duplstring n " " ))
;
; affichage de la phrase no‰lisÅe
( de affich ( chaine )
(setq me 40) ; milieu de l'ecran
(cond ((<= (nb_mots chaine 0) 1)
(setq cdg (- me 1)) ; cdg= colonne de gauche
(setq mdc chaine ) ; mdc=mot du centre
(setq dee(+(slength mdc)2)) ; distance entre 2 mots
( print (copies cdg)(renverse mdc))
) ; fin de la premiÉre condition
(t (let ((motgauche (mot chaine 1))
(motdroit (mot chaine (nb_mots chaine 0) ) )
(lmg ( slen (mot chaine 1))); longueur du mot È gauche
(lmd ( slen (mot chaine (nb_mots chaine 0))))
; lmd : longueur du motÈ droite
) ; fin du let
(setq largeur (- (slen chaine ) lmg lmd 2))
(setq sous_ch (substring chaine (+ lmg 1) largeur))
(affich sous_ch) ; APPEL rÅcursiF
(setq cdg (- cdg lmg 1))
(print (copies cdg)(renverse motgauche)
(copies dee)(renverse motdroit))
(setq dee (+ dee (slength motdroit)
(slength motgauche)2)))
) ; fin de la seconde condition
) ; fin du cond
) ; fin de la fonction affich
AprÉs rÅflexion, il nous semble intÅressant ou pour le moins curieux d'essayer d'Åcrire le mÁme programme en Lisp mais en utilisant des fonctions non rÅcursives. Cet exercice de style que d'aucuns (puristes) trouveront "inÅlÅgante" montre cependant (et nous ne visons ici pas d'autre but) de montrer qu'on peut tout Åcrire avec un langage puissant, collant ainsi È un algorithme typique, mÁme si ce n'est pas dans l'esprit du langage.
; COMAR en LELisp itÅratif
( de comar ()
(print "quelle est votre phrase ? " )
(setq phrase (read) )
(setq phrase (catenate phrase ( readline) ) )
(affichage phrase ) ; appelle la fonction qui no‰lise
); fin de la fonction comar
De la mÁme faµon, on rÅÅcrit aussi les sous-programmes en itÅratif, car de nombreux Lisp possÉdent des boucles Pour, Tant que... :
( de nb_mots ( chaine )
; cette fonction n'est efficace que si la phrase est
; entr"e sans espace redondant entre les mots ou au dÅbut
; ou È la fin de la phrase
(setq chaine ( catenate " " chaine ) )
(setq i 0 )
(setq nombre 0 )
(for (i 0 1 (slen chaine ) )
(if (eqstring " " (substring chaine i 1) )
(setq nombre ( + 1 nombre) ) )
) ; fin du for
nombre
) ; fin de la fonction nb_mots
;
( de espace ( chaine pos_espace )
(setq souschaine ( substring chaine pos_espace ) )
(setq pos_espace 1 )
(while (and (not
(eqstring(substring souschaine pos_espace 1) " " ))
( <= pos_espace ( slen chaine ) ) )
( setq pos_espace ( + 1 pos_espace) )
) ; fin du while
pos_espace ) ; fin de la fonction espace
;
( de fin ( chaine n )
(cond ((= n (nb_mots chaine)) (setq i (slen chaine)))
(t (setq i 0 )
(setq compteur 0 )
(while (and (<> n compteur)
(<= i (slen chaine) ) )
( setq compteur ( + compteur 1 ) )
( setq i ( + i (espace chaine i ) ) )
) ; fin du while
)) ; fin du cond
i) ; fin : renvoi de la position du caractÉre
; position du premier caractÉre du niÉme mot d'une chaÑne
( de debut ( chaine n )
( fin chaine ( - n 1 ) )
; explication: le dÅbut d'un mot c'est en fait la fin
; du mot prÅcÅdent
) ; fin de la fonction debut
;
; renvoie le niÉme mot d'une chaine
( de mot ( chaine n )
( substring chaine (debut chaine n)
(- (fin chaine n) (debut chaine n) ) )
) ; fin de la fonction mot
;
; renverse les lettres d'un mot
( de renverse ( mot )
(setq inverse "" )
(setq j ( slen mot ) ) ; initialisation du compteur
(while ( <> j (- 1 ) )
; -1 est la condition d'arrÁt car la position du
; premier caractÉre d'une chaine de caractÉres est 0
(setq inverse (catenate inverse (substring mot j 1)))
( setq j (- j 1) )
) ; fin du while
inverse ; renvoie le mot renvers, sur lui-mÁme
) ; fin de la fonction renverse
;
; renvoie le milieu d'une chaine
( de milieu ( chaine )
( + ( div ( nb_mots chaine ) 2 ) 1 )
) ; fin de la fonction milieu
;
; crÅe une ligne de n espaces
( de copies ( n )
( duplstring n " " )
) ; fin de la fonction
;
; affichage dÅtaillÅ
( de affichage ( chaine)
(tycls )
(print "Merci.Voici votre phrase pour vÅrification" )
(print phrase )
(print " Voici son arbre de No‰l" )
(terpri )
; dÅclaration de variables
(setq m ( milieu chaine ) )
; m : mot du milieu de la chaine
(setq me 40 )
; me : milieu de l'ecran
(setq mdc ( mot chaine m ) )
; mdc : premier mot
(setq cdg ( - me 1 ) )
; cdg : colonne dÅbut du mot gauche
( setq dee (+ ( slen mdc ) 1 ) )
; dee : distance entre 2 mots
; partie principale de la fonction affichage
(print ( catenate ( copies cdg ) ( renverse mdc ) ) )
( setq m1 m )
( setq m2 m )
( repeat ( - m 1)
; affectation des variables
( setq mot_a_gauche ( mot chaine ( decr m1 ) ) )
( setq mot_a_droite ( mot chaine ( incr m2 ) ) )
( setq lmg ( slen mot_a_gauche ) )
( setq cdg ( - cdg 1 lmg ) )
; fin de l'affectation des variables
( print ( copies cdg ) ( renverse mot_a_gauche )
( copies dee ) ( renverse mot_a_droite ) )
( setq dee (+ dee lmg ( slength mot_a_droite ) 2 ) )
) ; fin du repeat
( print "" )
) ; fin de la fonction affichage
* sauf Smalltalk qui sera dÅtaillÅ dans le chapitre sur les styles de programmation.
{PAGE|35}