Le problème 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.