3.1. Introduction
Les algorithmes décrits dans le chapitre précédent
étaient très simples et une calculatrice aurait
suffi pour leur exécution. En effet, pour l'instant, nous
sommes seulement en mesure de décrire une suite d'opérations,
chacune devant être exécutée une et une seule
fois. Nous ne pouvons par exemple utiliser notre algorithme de
calcul d'intérêt avec différents taux d'intérêt.
Pour faire cela, il nous faut introduire de nouvelles structures.
Il a été démontré que pour représenter
n'importe quel algorithme, il faut disposer des trois possibilités
suivantes:
3.2. La structure alternative.
Voici les règles d'un jeu très simple: deux joueurs
A et B se cachent la main droite derrière le dos. Chacun
choisit de tendre un certain nombre de doigts (de 0 à 5),
toujours derrière le dos. Les deux joueurs se montrent
la main droite en même temps. Si la somme des nombres de
doigts montrés est paire, le premier joueur a gagné,
sinon c'est le second. Le problème est de faire prendre
la décision par l'ordinateur.
Exprimé en français, l'algorithme se présente
comme suit:
En langage de description d'algorithme, l'algorithme s'écrira:
REMARQUES
(1) La structure alternative se présente en général
sous la forme
où expression conditionne le choix d'un des deux
ensembles d'instructions. Cette expression peut être
soit vraie soit fausse. Si l'expression est vraie, la première
séquence d'instruction sera exécutée et la
seconde sera ignorée; si l'expression est fausse, seule
la seconde séquence d'instructions sera effectuée.
Le mot sinon indique où se termine la première
séquence d'instructions et où commence la seconde.
Le mot fsi (abrégé de "fin de
si") indique où se termine la seconde séquence
d'instructions.
(2) Dans certains cas, lorsque l'expression est fausse, aucune
instruction ne doit être exécutée. La condition
s'exprime alors plus simplement sous la forme:
(3) Quelle que soit la séquence choisie et exécutée,
les instructions qui suivent fsi seront exécutées.
(4) Chacune des séquences d'instructions d'un si
... fsi peut contenir des si...fsi.
On dit alors que les structures sont imbriquées.
(5) Pour faire apparaître plus clairement la structure,
on écrit les séquences d'instructions légèrement
en retrait des mots-clefs (si, alors,
sinon, fsi). On dit qu'on indente
le texte de l'algorithme.
Considérons l'exemple suivant écrit sans indentation
et où les fins de si (fsi) ne sont pas indiquées:
Cet algorithme peut aussi bien être une mauvaise écriture
de:
(2.1)
(2.2)
Dans (2.1), si a est négatif, aucun traitement n'est effectué
et dans (2.2) si a est négatif, c vaut a-b.
3.3.Expressions logiques et variables booléennes.
Expressions logiques.
Les expresssions logiques se construisent à partir d'affirmations
qui sont soit vraies soit fausses. Une condition telle que "reste=0"
n'impose pas à la variable reste d'être nulle.
Il ne s'agit en effet pas d'une assignation mais de l'expression
d'une condition qui ne sera réalisée (et n'aura
donc la valeur "vrai") que si la variable reste
a été assignée à 0. Dans les autres
cas, cette condition prendra la valeur "faux".
On peut combiner des affirmations à l'aide d'opérateurs
logiques ,à savoir: ou, et
et non, les deux premiers portent sur deux opérandes
et le dernier sur un seul. Il est évident que ces opérandes
ne peuvent prendre que deux valeurs: vrai ou faux.
Par définition:
op1ou op2 n'a la valeur faux
que si les deux opérandes ont la valeur faux, sinon
l'expression a la valeur vrai.
op1et op2 n'a la valeur vrai
que si les deux opérandes ont la valeur vrai, sinon
l'expression a la valeur faux.
non opérande a la valeur vrai
si l'opérande a la valeur faux et inversement.
Supposons par exemple qu'on exécute les assignations suivantes:
alors
(b > 8) ou (c < 1) a la valeur faux
Les relations d'égalité ou d'inégalité
ci-dessus font comparer des nombres ou des variables à
valeur numérique.
On peut également comparer des lettres: l'affirmation "b"
précède "x" dans l'ordre alphabétique
a pour valeur vrai. De même, si la variable car
contient le caractère "v", l'affirmation car
suit "w" dans l'ordre alphabétique
a pour valeur faux.
Comme nous l'avons déjà vu, pour ramener des nombres
à la seule représentation que connaissent les ordinateurs
(le binaire), il suffit de faire un changement de base et passer
de la base 10 à la base 2. Par contre, il n'existe pas
de manière naturelle pour représenter un caractère
sous forme binaire. On associe donc arbitrairement un code à
chaque caractère connu par l'ordinateur, à savoir
les signes du clavier (lettres, chiffres décimaux, signes
de ponctuation et caractères spéciaux) et les caractères
de contrôle. Le code importe peu mais l'ordre de classement
(collating sequence) qu'il définit est par contre
très important. Le code ASCII, le plus fréquemment
utilisé sur les micro-ordinateurs, respecte l'ordre croissant
des caractères "0", "1", ..., "9"
et l'ordre alphabétique des 26 lettres de l'alphabet, et
ceci sans mêler aucun autre caractère dans ces séquences.
Afin de simplifier les notations, on convient d'utiliser les symboles
"<" pour signifier "précède
dans la collating sequence", "" pour "suit
dans la collating sequence ou est égal",...
Variables booléennes.
Il est possible de stocker la valeur d'une expression logique
dans une variable (comme le résultat d'une opération
arithmétique est stocké dans une variable numérique).
Cette variable ne peut prendre que les valeurs vrai et
faux. Ces variables sont appelées variables logiques
ou booléennes.
En LDA, elles se déclarent comme ceci:
booléen: OK, pair
et en Pascal par:
VAR BOOLEAN: OK, pair;
El l'assignation d'une variable booléenne se fait de la
manière suivante:
3.4. Exercices.
Pour voir les exercices et les solutions, cliquez ici.
3.5. L'alternative en Pascal.
En Pascal, l'exemple du jeu décrit en 2 se traduit par:
La structure alternative se traduit presque mot à mot de
LDA en Pascal: si se traduit par IF, alors
par THEN et sinon par ELSE. Les séquences
d'instructions à exécuter dans le cas où
la condition est vraie (cette séquence suit le mot alors)
et dans le cas où la condition est fausse (cette séquence
suit le mot sinon) doivent être encadrées
par le mots BEGIN et END qui en indiquent le début
et la fin. Dans le cas où ces séquences se réduisent
à une seule instruction, les mots BEGIN et END
peuvent être omis (comme dans l'exemple ci-dessus).
Ainsi, en ajoutant le message WRITELN('Bravo pour le gagnant!')
juste après avoir indiqué le nom du vainqueur, nous
serions obligés d'utiliser les BEGIN et END:
La forme:
si expression alors
séquence d'instructions
se traduit en Pascal par:
Il est interdit de mettre un ; après le END
indiquant la fin de la séquence d'instructions qui suit
le THEN.
Et la forme:
se traduit en Pascal par:
Remarques:
(1) La traduction en Pascal de (2.1) est:
En effet, en Pascal, le ELSE se rapporte toujours au IF
... THEN le plus proche.
Pour traduire (2.2), il faut soit modifier les alternatives pour
que le sinon se rapporte au alors le plus proche:
Il existe deux remèdes à ce problème. La
première consiste à effacer l'écran après
que A ait tapé son nombre. Ceci se fait en Pascal par l'instruction
CLRSCR qui nécessite le chargement d'une librairie.
Celui-ci est activé par la ligne: USES Crt; écrite
juste en-dessous de PROGRAM Jeu;
La deuxième solution est de saisir le caractère
(le chiffre dans ce cas) tapé au clavier sans l'afficher.
Cela se fait grâce à la fonction READKEY qui
scrute en permanence le clavier et qui capte la touche qui vient
d'être enfoncée. Cependant cette fonction ne peut
être employée que pour l'affectation à une
variable de type caractère.
Dans ce cas notre programme deviendrait:
3.6. Le choix multiple.
Supposons que l'on veuille demander à l'utilisateur de
choisir dans un menu une des 3 possibilités offertes. Le
choix présenté ne se limite pas à une alternative
(soit - soit).
Nous nous trouvons en présence d'un choix multiple qui
s'écrit en LDA:
La structure de choix multiple peut, comme l'alternative, prendre deux formes:
Si la i ème expression logique a la valeur vrai,
la i ème séquence d'instructions est exécutée
puis il y a passage aux instructions qui suivent le mot fselon.
Si toutes les expressions logiques ont la valeur faux,
on exécute dans le premier cas la séquence d'instructions
qui suit le mot autrement , dans le deuxième
cas on passe directement à ce qui suit fselon.
Afin d'éviter toute ambiguïté, on exige que
les différentes expressions logiques soient mutuellement
exclusives.
3.7. Le choix multiple en Pascal.
La traduction de selon que ...fselon
en Pascal n'est pas très commode parce que la structure
du choix multiple y est très restrictive: Il est seulement
possible de traduire un selon que ... fselon
pour lequel l'expression prend les valeurs prises par une variable
de type énuméré (dont les valeurs appartiennent
à un ensemble; par exemple entier, caractère).
La forme générale du choix multiple est:
Pour traduire en Pascal un selon que plus général,
il faut utiliser des IF imbriqués. Par exemple,
se traduit par:
1) Lire 3 nombres a, b et c. Déterminer si l'équation
ax+by+c=0 représente l'équation d'une droite
parallèle à l'un des axes (et si oui, lequel) ou
une droite oblique par rapport aux axes. Tenir compte du fait
qu'on pourrait avoir a=b=0.
2) Lire 3 nombres a, b et c où a est différent de
0. Déterminer si la parabole d'équation y=ax²+bx+c coupe l'axe des x en 0, 1 ou 2 points.
3) Demander et lire les valeurs de R en Ohm, I en Ampère
et t en seconde. Déterminer un algorithme qui proposerait
de calculer la différence de potentiel, la puissance et
l'énergie.
Jusqu'à présent, nous avons décrit la structure
de séquence. Nous décrirons dans ce chapitre les
structures de choix: l'alternative et le choix multiple.
- prendre connaissance du nombre de doigts de A
- prendre connaissance du nombre de doigts de B
- calculer la somme de ces deux nombres
- si la somme est paire, A est le gagnant
- si la somme est impaire, B est le gagnant.
Pour déterminer si un nombre est pair ou impair, il suffit
de calculer le reste de la division par 2 (.. modulo 2): il vaut
0 dans le premier cas et 1 dans le second.
entier na,nb,reste
lire na,nb
reste <-- (na + nb) mod 2
si reste = 0 alors écrire "Le joueur A a gagné."
sinon écrire "Le joueur B a gagné."
fsi
écrire "Bravo pour le gagnant!"
si expression alors première séquence d'instructions
sinon deuxième séquence d'instructions
fsi
si expression alors séquence d'instructions
fsi
si a > 0 alors
si b > 0 alors
c <-- a+b
sinon
c <-- a-b
si a > 0 alors si b > 0 alors c <-- a+b
sinon c <-- a-b
fsi
fsi
que de:
si a > 0 alors si b > 0 alors c <-- a+b
fsi
sinon c <-- a-b
fsi
a <-- 1
a <-- 1
b <-- 2
c <-- 3
(b > 0) ou (c > 1) a la valeur vrai
(b > 9) ou (c > 1) a la valeur vrai
(b > a) et (c > b) a la valeur vrai
(b > a) et (c < 0) a la valeur faux
non (c < a) a la valeur vrai
non ((b > a) et (c > b)) a
la valeur faux
((b > a) et (c > b)) ou (a
< 0) a la valeur vrai
OK <-- Vrai
PROGRAM Jeu;
VAR NA, NB, Reste:INTEGER;
BEGIN
WRITE('Introduisez le nombre de doigts montrés par le joueur A');
READLN(NA);
WRITE('Introduisez le nombre de doigts montrés par le joueur B);
READLN(NB);
RESTE := (NA + NB) MOD 2;
IF RESTE=0 THEN WRITELN('Le joueur A a gagné.')
ELSE WRITELN('Le joueur B a gagné.');
WRITELN('Bravo pour le gagnant!')
END.
PROGRAM Jeu;
VAR NA, NB, Reste:INTEGER;
BEGIN
WRITE('Introduisez le nombre de doigts montrés par le joueur A');
READLN(NA);
WRITE('Introduisez le nombre de doigts montrés par le joueur B);
READLN(NB);
RESTE := (NA + NB) MOD 2;
IF RESTE=0 THEN BEGIN
WRITELN('Le joueur A a gagné.');
WRITELN('Bravo pour le gagnant!')
END
ELSE BEGIN
WRITELN('Le joueur B a gagné.');
WRITELN('Bravo pour le gagnant!')
END
END.
sinon séquence d'instructions
fsi
IF expression THEN BEGIN
séquence d'instructions
END
ELSE BEGIN
séquence d'instructions
END;
si expression alors séquence d'instructions
fsi
IF expression THEN BEGIN
séquence d'instructions
END;
IF A>0 THEN IF B>0 THEN C:=A+B
ELSE C:=A-B;
si NOT (a=0) alors c <-- a - b
sinon si b > 0 alors c <-- a + b
fsi
fsi
ou faire apparaître que le sinon de la première
condition est absent:
IF A>0 THEN IF B>0 THEN C:=A+B
ELSE
ELSE C:=A-B;
(2) Le programme de jeu listé ci-dessus a un gros défaut:
lorsque le premier joueur tape au clavier son nombre stocké
dans NA, celui-ci reste affiché et le deuxième joueur
peut choisir NB de façon à être certain de
gagner.
PROGRAM Jeu;
USES Crt;
VAR NA, NB, Reste, Err : INTEGER;
A, B : CHAR;
BEGIN
CLRSCR;
WRITE('Introduisez le nombre de doigts montrés par le joueur A');
A:=READKEY;
VAL(A, NA, Err);
IF Err<>0 THEN WRITELN('Erreur de format numérique!')
ELSE BEGIN
WRITE('Introduisez le nombre de doigts montrés par le joueur B);
B:=READKEY;
VAL(B, NB, Err);
IF Err<>0 THEN WRITELN('Erreur de format numérique!')
ELSE BEGIN
RESTE := (NA+NB) MOD 2;
IF RESTE=0 THEN WRITELN('Le joueur A a gagné.')
ELSE WRITELN('Le joueur B a gagné.');
WRITELN('Bravo pour le gagnant!')
END
END.
La procédure VAL(Chaine, Nombre, Erreur)
permet de convertir Chaine en sa valeur numérique.qui
sera stockée dans Nombre. La variable Erreur
contiendra la valeur 0 si la conversion s'est faite sans problème
ou la position du premier caractère inadéquat. Erreur
doit être du type INTEGER, Chaine du type
STRING ou CHAR et Nombre d'un type numérique
(entier ou réel).
entier i
lire i
selon que
i=1 faire bloc1
oq i=2 faire bloc2
oq i=3 faire bloc3
autrement écrire "Mauvais choix"
fselon
Le mot oq est l'abréviation de "ou
que".
selon que
première expression logique faire première séquence d'instructions
oq deuxième expression logique faire deuxième séquence d'instructions
...
oq n ème expression logique faire n ème séquence d'instructions
autrement (n+1) ème séquence d'instructions
fselon
et
selon que
première expression logique faire première séquence d'instructions
oq ...
oq n ème expression logique faire n ème séquence d'instructions
fselon
La première forme généralise le si
... alors ... sinon ... fsi,
la seconde le si ... alors ... fsi.
CASE <expression> OF
valeur1: première séquence d'instructions;
valeur2: deuxième séquence d'instructions;
...
valeurN: Nème séquence d'instructions;
ELSE (N+1) ème séquence d'instructions;
END;
Il est à noter que les différentes séquences
d'instructions sont délimitées par BEGIN
et END qui peuvent seulement être omis si une séquence
se résume à une seule instruction.
...
lire x
selon que
x<0 faire écrire x,"est négatif"
oq x=0 faire écrire x,"est nul"
autrement écrire x,"est positif"
fselon
...
...
READLN(x);
IF x<0 THEN WRITELN(x, ' est négatif.')
ELSE IF x=0 THEN WRITELN(x, ' est nul.')
ELSE WRITELN(x, ' est positif.');
3.8. Exercices.