© 1996 JMy

LES STRUCTURES REPETITIVES.


4. STRUCTURES REPETITIVES.

4.1. Introduction.

L'intérêt d'utiliser un ordinateur n'apparaît clairement que lors de la manipulation de données nombreuses ou traitées de manière répétitive.

Exemple 1: Chercher dans une liste de noms et d'adresses, l'adresse d'une personne à partir de son nom. Le nombre de fois qu'il faudra comparer le nom donné aux noms de la liste est dans ce cas inconnu.

Exemple 2 : Calculer la N ème puissance entière d'un nombre x par multiplications successives du nombre par lui-même. Ici, le nombre de répétition (N) de l'instruction de multiplication est connu.

S'il est théoriquement possible de se contenter d'une seule structure de répétition, bien choisie, pour exprimer tous les algorithmes, l'expérience a montré l'utilité d'en définir plusieurs, chacune bien adaptée à des circonstances particulières. Ce sont les boucles tant que, répéter ... jusqu'à et pour.

4.2. La boucle " tant que ".

Résolvons l'exemple 1:

 ...
 lire nom_donné
 lire nom1
 si nom1 = nom_donné alors écrire adresse1
 sinon lire nom2
       si nom2 = nom_donné alors écrire adresse2
       sinon lire nom3
             si nom3 = nom_donné alors ...

L'inconvénient de cet algorithme (en dehors de l'empiètement inévitable sur la marge de droite) tient au fait que l'auteur ne sait pas quand il doit s'arrêter d'écrire. Plus précisément, il lui est impossible de savoir combien de fois il doit écrire l'instruction de comparaison au nom_donné.

Un problème identique surgit dans l'écriture d'un algorithme qui décrit comment calculer le premier nombre premier qui soit plus grand qu'un nombre entier positif donné N.

 lire N
 i <-- N+1
 si i est premier alors écrire i
 sinon i <-- i+1
       si i est premier alors écrire i
       sinon i <-- i+1
            si i est premier alors écrire i
            sinon i <-- i+1
                  si ...
Le test "si i est premier alors" ne sera exécuté qu'une fois si N=4, il le sera quatre fois si N=13, mais combien de fois faudra-t-il réécrire le test si N=7394485?

Ces exemples montrent que la séquence et l'alternative ne sont pas en elles-mêmes suffisantes pour exprimer des algorithmes dont la longueur peut varier selon les circonstances. Il est donc nécessaire d'introduire le moyen de répéter certaines instructions d'un algorithme un nombre quelconque de fois. La structure qui permet cela est appelée structure répétitive.

En utilisant la boucle "tant que", l'exemple 1 (avec la liste) s'écrit:

 lire nom_donné
 i <-- 1
 lire nomi
 tant que NOT ((nomi = nom_donné) ou (fin de liste)) faire
   i <-- i+1
   lire nomi
 ftant
 si nomi = nom_donné alors écrire adressei
 sinon écrire "Le nom demandé ne se trouve pas dans la liste."
 fsi
L'exemple avec le nombre premier s'écrira:
 lire N
 i <-- N+1
 tant que NOT (i est premier) faire
   i <-- i+1
 ftant
 écrire i
Notons qu'il faudra exprimer autrement les conditions " (fin de liste) " et " (i est premier) ", ces formes n'étant pas compréhensibles par les compilateurs/interpréteurs.

Considérons aussi l'exemple suivant: étant donnés deux nombres entiers m et n positifs ou nuls, on demande d'en calculer le PGCD. L'algorithme d'Euclide permet de résoudre ce problème en prenant d'abord le reste de la division de m par n, puis le reste de la division de n par ce premier reste, etc jusqu'à ce qu'on trouve un reste nul. Le dernier diviseur utilisé est le PGCD de m et n. Pour m=1386 et n=140, on a successivement:

 1386 = 140 * 9 + 126  140 = 126 * 1 +  14   126 =  14 * 9 + 0
et le PGCD de 1386 et 126 est bien 14.

Remarquons que par définition, si un des nombres est nul, l'autre nombre est le PGCD .

Si nous avions pris m=140 et n=1386, nous aurions obtenu la suite de calculs suivants:

 140 = 1386 * 0 + 140    1386 =  140 * 9 + 126

 140 =  126 * 1 +  14     126 =  14 * 9 +   0

et le PGCD est le même. L'ordre de m et n n'a donc pas d'importance.

Dans cet exemple, nous devons répéter le calcul du reste de la division d'un nombre par un autre. Pour fixer les idées, appelons a le dividende, b le diviseur et r le reste. Le calcul du reste de la division de a par b se fait simplement au moyen de l'instruction :

 r <--  a mod b
L'algorithme s'écrit donc:
 entier m,n,a,b,r,PGCD
 lire m, n
 a <-- m
 b <-- n
 tant que NOT(b = 0) faire
   r <-- a mod b
   a <-- b
   b <-- r
 ftant
 PGCD <-- a
 écrire "Le PGCD de",m,"et",n,"est",PGCD
Commentaires

1) Les mots faire et ftant (abréviation de "fin de tant que") encadrent les instructions qui doivent être exécutées plusieurs fois. On indique entre tant que et faire les conditions dans lesquelles on doit exécuter le corps de la boucle.

2) Une boucle "tant que" se présente donc comme suit:

 tant que expression logique faire
    séquence d'instructions
 ftant

En premier lieu, l'expression logique est évaluée (il faut donc veiller à sa valeur lors de l'entrée dans la boucle): si sa valeur est vrai, le corps de la boucle est exécuté puis l'expression logique est réévaluée (il faut donc qu'elle puisse changer de valeur pour sortir de la boucle) et si elle a la valeur faux, on exécute l'instruction qui suit ftant.

3) Il est à noter qu'il est préférable d'exprimer l'expression logique sous la forme NOT (condition(s) d'arrêt). Il est en effet plus simple de déterminer les raisons d'arrêter le processus répétitif que celles de continuer.
La forme de ce type de boucle devient donc:

 tant que NOT condition(s) d'arrêt faire
    séquence d'instructions
 ftant

4.3. La boucle " pour".

Reprenons l'exemple 2 de l'introduction. Une boucle "tant que" permet de le résoudre:

 entier N, i
 réel x, puiss
 lire N, x
 puiss <-- 1
 i <-- 1
 tant que NOT(i > N) faire
   puiss <-- puiss * x
   i <-- i + 1
 ftant
 écrire "La puissance",N,"ème de",x,"est",puiss
Cependant, le nombre d' exécutions du corps de la boucle étant connu à l'avance, une boucle "pour" est d'un emploi plus simple:
 entier N, i
 réel x, puiss
 lire N, x
 puiss <-- 1
 pour i de 1 à N faire
    puiss <-- puiss * x
 fpour
 écrire "La puissance",N,"ème de",x,"est",puiss
Commentaires

1° Les mots faire et fpour (abréviation de "fin du pour") encadrent les instructions qui doivent être exécutées plusieurs fois. On précise entre pour et faire comment seront contrôlées les répétitions. On y définit une variable appelée variable de contrôle (i dans l'exemple) et les valeurs que prendra cette variable: une première valeur ou valeur initiale indiquée après le mot de, une dernière valeur ou valeur finale indiquée après le mot à. La variable de contrôle est initialisée à la première valeur. Avant chaque exécution du corps de la boucle, la valeur de la variable de contrôle est comparée à la valeur finale. Si la variable de contrôle ne dépasse pas cette valeur, on exécute le corps de la boucle, sinon on passe à l'instruction qui suit le mot fpour. Après chaque exécution du corps de la boucle, la variable de contrôle est augmentée d'une unité.

2° Dans l'exemple ci-dessus, la variable de contrôle sert uniquement de compteur du nombre d'exécutions du corps de la boucle. Si on le souhaite, on peut utiliser cette valeur dans le corps de la boucle, entre autres pour faire un calcul fondé sur cette valeur. Dans tous les cas, il faut éviter de modifier la valeur de cette variable.

3° Il est parfois utile de faire varier la variable de contrôle par valeurs décroissantes, ou par incréments différents de l'unité. Dans ce cas, il faut utiliser la forme la plus générale de la boucle "pour":

 pour v.c. de prem.val. à dern.val. par incr faire
    séquence d'instructions
 fpour

Il est important de noter ici l'impossibilité de traduire en Pascal les boucles avec des incréments différents de 1 et -1.

Avant chaque exécution du corps de la boucle, la valeur de la variable de contrôle est comparée à la dernière valeur. L'exécution s'arrête

Par convention, lorsque l'incrément est égal à 1, il n'est pas indiqué.

4° La première valeur, la dernière valeur et l'incrément peuvent être des expressions numériques. Les instructions du corps de la boucle ne peuvent en aucun cas modifier ces valeurs.

5° En fin de boucle, la valeur de la variable de contrôle n'est pas toujours égale à la valeur finale (à vérifier avec votre compilateur). Il est donc dangereux d'utiliser celle-ci.

6° Il est théoriquement possible de modifier la valeur de la variable de contrôle à l'intérieur de la boucle mais cette technique est à proscrire et ne masque pas un manque de réflexion lors de l'analyse du problème. Cette manière de faire revient en fait à transformer artificiellemnt une boucle pour en boucle tant que.

4.4. La boucle " répéter ... jusqu'à ".

Comme la boucle "tant que", ce type de répétitive est utilisé lorsque le nombre de fois que la séquence d'instructions à répéter est inconnu au moment où cette séquence est abordée pour la premiè fois mais le corps de la boucle est toujours exécuté au moins une fois.

Sa formulation générale est:

 répéter
    séquence d'instructions
 jusqu'à (expression logique)
L'expression logique est évaluée aprés l'exécution du corps de la boucle: si sa valeur est faux, le corps de la boucle est exécuté à nouveau puis l'expression logique est réévaluée (il faut donc qu'elle puisse changer de valeur pour sortir de la boucle) et si elle a la valeur vrai, on exécute l'instruction qui suit jusqu'à. Attention, si ceci correspond tout à fait à l'usage familier que nous faisons de l'expression répéter ... jusqu'à, le test effectué est la négation de celui utilisé dans la boucle "tant que" et ceci peut parfois prêter à confusion.
Il faut en effet remarquer que dans
 tant que expression logique faire
     séquence d'instructions
 ftant
expression logique exprime les raisons de continuer et dans
 répéter
     séquence d'instructions
 jusqu'à (expression logique)

expression logique exprime les raisons d'arrêter.

4.5. Exercices.

1) Lire un nombre entier et déterminer s'il est premier.

2) Lire un nombre entier et déterminer tous ses diviseurs.

3) L'ordinateur "choisit" un nombre entier compris entre 0 et 100. Un joueur essaie de le deviner. Lors de chaque essai, l'ordinateur affiche la "fourchette" dans laquelle se trouve le nombre qu'il a choisi.

4) Lire un entier N positif et non nul. Ecrire un algorithme qui calcule le Nème nombre de la suite de Fibonacci. Ceux-ci se calculent ainsi:

F(0) = 0, F(1) = 1 et F(i) = F(i-1) + F(i-2) pour i > 1.

Résumé:
Le problème principal est de bien choisir le type de boucle à utiliser.
Voilà les questions à se poser pour faire le bon choix:
Le nombre de répétitions est-il connu au moment du premier passage dans la boucle?
Oui et bien alors, il ne faut pas hésiter. Il faut utiliser une boucle pour...fpour
Non. Alors il faut se demander si on est sûr que le corps de la boucle sera effectué au moins une fois.
Oui et bien alors, il semble raisonnable d'utiliser la boucle répéter...jusqu'à.
Non. Alors pas d'hésitation, c'est la boucle tant que...ftant qu'il faut utiliser.

Dernier conseil:
sachant que les conditions d'arrêt d'une boucle sont en général plus simples à trouver que les raisons de continuer, surtout parce qu'elles s'expriment souvent sous forme condition1 ou condition2 ou ..., il est préférable d'utiliser la boucle tant que sous la forme
tant que NOT (condition1 ou condition2 ou ...)
....
ftant
.


En pratique:
Imaginons que vous ayiez:
écrire "Introduisez un nombre positif non nul"
lire N
si N>0 alors 'arrêter de demander'(*)
écrire "Introduisez un nombre positif non nul"
lire N
si N>0 alors 'arrêter de demander'
écrire "Introduisez un nombre positif non nul"
lire N
si N>0 alors 'arrêter de demander'
....
On remarque qu'entre 2 tests d'arrêt (si N>0 alors 'arrêter de demander') se situe ce qu'on appelle le corps de la boucle
écrire "Introduisez un nombre positif non nul"
lire N

Même s'il semble évident que le test d'arrêt se trouve en (*), il y a deux manières de traduire en boucle:
(1) placer le test d'arrêt après l'exécution du corps de la boucle donne:
répéter
  écrire "Introduisez un nombre positif non nul"
  lire N
jusqu'à N>0
(2) placer le test d'arrêt avant l'exécution du corps de la boucle donne:
écrire "Introduisez un nombre positif non nul"
lire N
tant que NOT (N>0) faire
  écrire "Introduisez un nombre positif non nul"
  lire N
ftant
Vous remarquerez que le test d'arrêt est bien toujours en 3ème ligne.

Alors quelle version choisir?
Au nombre de lignes, c'est la première version qui l'emporte mais pourtant beaucoup préfèrent la seconde.
Pourquoi?
Simplement parce qu'elle peut être très facilement modifiée en une version qui prévient l'utilisateur de sa faute:
écrire "Introduisez un nombre positif non nul"
lire N
tant que NOT (N>0) faire
  écrire "Le nombre introduit n'est pas positif!!"
  écrire "Introduisez un nombre positif non nul"
  lire N
ftant
En effet juste après le test tant que NOT (N>0) faire, nous sommes sûrs de ne pas avoir N>0.
Nous voyons ainsi que bien que le corps de la boucle soit exécuté au moins une fois, nous avons utilisé une boucle tant que et non une boucle répéter.

4.6. Tableaux ou variables indicées.

Reprenons l'exercice 3) et décidons de garder en mémoire les différents essais du joueur. Il est évidemment impossible de stocker chaque essai dans une variable de nom différent car cette technique nous empêche d'employer une boucle (les noms de variables du corps de la boucle ne peuvent en effet pas changer d'une répétition à l'autre); or ici, l'emploi d'une boucle est obligatoire car on ne connaît pas à l'avance le nombre d'essais qui seront tentés.

Exemple

Nous voudrions stocker les notes de l'examen semestriel pour le calcul de la moyenne de l'examen et pour un futur calcul du total semestriel.

S'il fallait calculer uniquement la moyenne, on pourrait utiliser l'algorithme suivant:

 entier note,total,max,maxnote,moyenne
 total <-- 0
 max <-- 0
 pour i de 1 à 16 faire
    lire note,maxnote
    si NOT(note < 0) alors  total <-- total + note
                            max <-- max + maxnote
    fsi
 fpour
 moyenne <-- [total/max * 100 + .5]
 écrire "La moyenne est de",moyenne,"%"
où pour indiquer une absence ou une dispense pour une certaine branche, nous avons attribué une note négative dont il ne faut évidemment pas tenir compte dans le calcul du total des points obtenus et du total des points attribués.

Mais comme il faut retenir les notes pour un calcul ultérieur, cet algorithme doit être modifié. L'utilisation d'une variable indicée (ou tableau ou table) nous fournit une solution, notei représentant la note de la ième branche et maxnotei le maximum attribué dans la branche numéro i.

Dans l'algorithme qui suit, on retient le nom de la branche en utilisant une autre variable indicée liste appelée branche (branchei représentant le nom de la ième branche).

 tableau notei, i=1,2,...,10 d'entier
         maxnotei , i=1,2,...,10 d'entier
         branchei, i=i,...,10 de chaine
 entier max,total, moyenne
 total <-- 0
 max <-- 0
 pour i de 1 à 16 faire
     écrire "Introduisez le nom de la branche ",i
     lire branchei
     écrire "Introduisez la note de la branche ",i
     lire notei
     écrire "Introduisez le maximun de la branche ",i
     lire maxnotei
     si NOT(notei < 0) alors  total <-- total + notei
                              max <-- max + maxnotei
     fsi
 fpour
 moyenne <-- [total / max * 100 + .5]
 écrire "La moyenne est de",moyenne,"%"

Définitions et commentaires

Pour définir les variables indicées, il faut introduire un nouveau type de variable dans le langage de description que nous utilisons: le type tableau. Chaque variable indicée -chaque tableau- qui sera utilisée doit être décrite dans la partie déclarative de l'algorithme; la description comprend trois parties:

1° La première partie décrit le nom de la variable et le nombre de ses indices: note, maxnote et branche dans notre exemple, chacune avec un indice. Pour indiquer que t, u sont des variables à 2, 3 indices, on aurait écrit:

 ti, j  ...de ...
 ui,j,k ...de ...
Les symboles utilisés (i, j, k, ...) pour indiquer le nombre d'indices servent uniquement dans la deuxième partie de la description. Si on le désire, on peut utiliser les mêmes symboles dans le reste de l'algorithme, mais on n'y est pas obligé.

2° La deuxième partie décrit pour chaque variable les valeurs que peuvent prendre ces indices: les entiers de 1 à 16 pour chaque variable de notre exemple. Comme on le voit, cet ensemble de valeurs peut être représenté de plusieurs façons différentes.

On appelle note1,...,note16 les composantes (ou éléments) du tableau note, de même pour maxnotei et branchei. Chaque composante se comporte comme une variable semblable à celles que nous avons manipulées jusqu'à présent: on peut la lire ou l'écrire, utiliser sa valeur dans une expression, lui assigner une valeur ...

3° Comme toute variable, chaque composante d'un tableau doit avoir un type, défini dans la troisième partie de la description du tableau: les composantes du tableau branche sont des chaînes, celles de note et maxnote sont des entiers. Toutes les composantes d'un tableau doivent être du même type: on ne peut pas définir un tableau dont certaines composantes seraient des nombres et d'autres des chaînes de caractères.

Lorsqu'on utilise une composante d'un tableau, les indices peuvent être un nom de variable comme dans l'algorithme, ou un nombre, ou même une expression. Par exemple si i=3 et N=16, notei, note3 et noteN-13 représentent tous la même composante du tableau note. Par analogie avec les variables indicées utilisées en mathématique, on appelle souvent vecteur un tableau à 1 indice et matrice un tableau à 2 indices: les déclarations suivantes sont équivalentes:

 tableau  ai ,  i=1,2,...,20 de réel
          bi, j ,i=1,2,...,9 , j=1,2,...,5 de chaîne

équivaut à:

 vecteur  ai ,i=1,2,...,20 de réel
 matrice  bi, j , i=1,2,...,9 , j=1,2,...,5 de chaîne

4.7. Exercices.

1) Etant donné un vecteur de nombres triés par ordre croissant, chercher si un nombre donné x figure parmi les composantes. Si oui, indiquer la valeur de l'indice correspondant.

2) Bonhomme pendu. L'algorithme lit un mot proposé par un premier joueur. L'algorithme affiche ensuite le mot où toutes les lettres sauf la première et la dernière sont remplacées par un tiret. Un deuxième joueur propose des lettres une à une. Chaque fois que la lettre se trouve dans le mot, l'algorithme remplace les tirets qui remplaçaient cette lettre et réaffiche le mot. Le second joueur a droit à un maximum de 6 essais infructueux (lettre ne se trouvant pas dans le mot).

3) Carrés magiques d'ordre impair. Un carré magique d'ordre n est un tableau carré à n lignes et n colonnes, donc de n² cases, dans lesquelles on écrit une et une seule fois les nombres entiers de 1 à n², de telle sorte que la somme des n nombres de chaque ligne, de chaque colonne et de chaque diagonale soit toujours la même. On dispose pour les carrés magiques d'ordre impair de l'algorithme suivant:
En désignant par (i,j) la case de la ligne i et de la colonne j:
(a) on place 1 en ( n , (n+1)/2 )
(b) ayant placé le nombre k dans la case (i,j) on place le nombre k+1 dans la case (i+1,j+1), toutefois si cette case est occupée on place le nombre k+1 dans la case (i-1,j).
Lorsque les indices calculés sont supérieurs à n, on prend 1 comme indice. Ces opérations se font pour 1<=k<=n²-1.

4) Jeu de Marienbad. On place des allumettes sur 4 rangées: 1 allumette sur la première, 3 sur la seconde, 5 sur la troisième et 7 sur la dernière. Deux joueurs peuvent alternativement ôter, sur une seule rangée à la fois, autant d'allumettes qu'ils le souhaitent mais au moins une. Le joueur qui enlève la dernière allumette a perdu.

5) Lire un texte d'au moins 120 caractères. Compter et afficher le nombre d'occurences (d'apparition) de chacune des lettres de l'alphabet.

6) Nous désignerons par a1, a2, ..., an les éléments d'un tableau à trier par ordre croissant.
On commence par chercher l'indice du plus petit des éléments, soit j cet indice. On permute alors les valeurs de a1 et aj .On cherche ensuite l'indice du plus petit des éléments a2, a3, ..., an et on permute avec a2, etc.

Résumé:
Seuls les tableaux (et les listes chaînées) permettent de stocker/traiter des données d'une manière répétitive.
C'est la seule manière de générer automatiquement des noms de variable.


4.8. Les boucles en Pascal.

Et l'exemple du calcul du PGCD de deux nombres se traduit par:

 PROGRAM Plus_Grand_Commun_Diviseur;
 VAR m,n,a,b,r,PGCD : INTEGER;
 BEGIN
 WRITELN('Nous allons calculer le PGCD de deux nombres entiers.');
 WRITE('Introduisez le premier nombre: '); READLN(m);
 WRITE('Introduisez le deuxième nombre: '); READLN(n);
 a := m; b := n;
 WHILE NOT(b = 0) DO
    BEGIN
    r := a mod b;
    a := b;
    b := r
    END;
 PGCD := a;
 WRITELN('Le PGCD de ',m,' et ',n,' est ',PGCD)
 END.
En Pascal, la boucle tant que se traduit par
 WHILE expression logique DO
    BEGIN
    séquence d'instructions;
    END;
où la séquence d'instructions est entourée comme d'habitude par un BEGIN et un END qui peuvent être omis lorsque la séquence se réduit à une seule instruction.

Le calcul de la puissance se traduit en Pascal:

 PROGRAM Puissance;
 VAR N,i : INTEGER;
     x, Puiss: REAL;
 BEGIN
 WRITELN('Calcul de la puissance N ème du réel x par multiplications successives.');
 WRITE('Introduisez le nombre réel x: ');READLN(x);
 WRITE('Introduisez l'exposant de x (entier positif): ');READLN(N);
 Puiss := 1;
 FOR i:=1 TO N DO
     Puiss:=Puiss*x;
 WRITELN('La puissance ',N,' ème de ', x,' est ',Puiss)
 END.
La boucle pour en Pascal n'exige pas de spécifier explicitement l'incrément si celui-ci est égal à un. Elle se traduit dans ce cas, comme dans notre exemple, par:
 FOR v.c.:=prem.val. TO dern.val. DO
    BEGIN
    séquence d'instructions
    END;
Le Pascal n'accepte, en dehors de l'incrément égal à 1, que l'incrément -1. Dans ce cas, la traduction est:
 FOR v.c.:=prem.val. DOWNTO dern.val.DO
    BEGIN
    séquence d'instructions
    END;
TOet DOWNTO indiquent que la variable de contrôle v.c. sera incrémentée (augmentée de une unité pour TO ou diminuée de une unité pour DOWNTO) après chaque exécution du corps de la boucle. Si la valeur de la v.c. dépasse (est strictement plus grande pour TO ou strictement plus petite pour DOWNTO) la dern. val., le corps de la boucle n'est plus exécuté et le programme exécutera les instructions qui suivent la dernière instruction du corps de la boucle.

Le corps de la boucle NE sera PAS exécuté si la prem.val. est supérieure à dern.val. pour TO ou si la prem.val. est inférieure à dern.val. pour DOWNTO.

Dans le cas de boucles FOR ... DO imbriquées, les variables de contrôle doivent avoir des noms différents et le la fin de la boucle intérieure doit apparaître avant celle de la boucle extérieure.

La traduction en Pascal de:

 répéter
     séquence d'instructions
 jusqu'à (expression logique)
se fait pratiquement mot à mot:
 REPEAT
     séquence d'instructions
 UNTIL (expression logique);
Remarque: La séquence d'instructions n'est pas entourée par BEGIN ... END.

4.9. Les tableaux en Pascal.

En Pascal, un tableau est déclaré du type ARRAY et le nombre de dimensions (indices) du tableau s'indique entre crochets en citant les valeurs minimales et maximales successives des différents indices, séparées par deux points (..). La déclaration du type des éléments contenus dans le tableau se fait en ajoutant OF INTEGER, ou OF REAL, ...

Exemple:

tableau ai, j, k   i=0, ..., 12 , j=1, ..., 5 , k=12, ..., 19 d'entiers
        bi i=12, ..., 25 de chaînes
        ci, j, k, l  i=1,...,6 , j=1,...,15 , k=1,...,9 , l="a",...,"z" de réels

se traduit en Pascal par:

VAR a: ARRAY[0..12, 1..5, 12..29] OF INTEGER;
    b: ARRAY[12..25] OF STRING;
    c: ARRAY[1..6, 1..15, 1..9, 'a'..'z'] OF REAL;
Il faut remarquer que l'indice d'un tableau ne doit pas nécessairement être du type entier. Tout type énuméré (dont le suivant est connu) peut être utilisé. L'élément ai,j,k de ce tableau s'écrit a[i,j,k]en Pascal. De même, l'élément a5,n-2,[k/2] se traduira par: a[5,n-2,TRUNC(k/2)].

En Pascal, comme toute autre type de variable, un tableau est remis à "zéro" ou à "blanc" mais il est préférable de ne pas préjuger de cette situation qui peut évoluer avec les versions du compilateur.

Il faut remarquer que la valeur maximale permise pour un indice ne peut être lue ou calculée en cours d'exécution d'un programme (allocation dynamique des tableaux) et elle ne peut donc varier d'une exécution à l'autre. Il faut par conséquent surestimer le nombre d'éléments nécessaires pour en disposer dans tous les cas d'un nombre suffisant en cours d'exécution du programme.

4.10 Exercices.

1) Calculer la racine carrée de a grâce à la formule récurrente x = 1/2 (x + a/x). Les calculs commenceront avec 1 comme valeur initiale de x et stopperont quand la valeur absolue de la différence entre les deux dernières valeurs calculées sera inférieure à 10-6.

2) Lire deux polynômes et en calculer la somme et le produit.

3) Lire un polynôme et en calculer la valeur pour x = a (a est lu au clavier).

4) Lire un nombre entier, la base dans lequel il est exprimé et celle dans lequel il doit être exprimé. Effectuer la conversion et afficher le résultat.

5) Lire une chaîne de caractères et la mettre en majuscules.

6) Lire une chaîne de caractères et en déterminer le nombre de mots.

7) Lire une chaîne de caractères et en déterminer le nombre de caractères différents.

8) Lire deux nombres entiers N1 et N2. Si un des nombres est nul, l'autre est le PGCD sinon il faut soustraitre le plus petit du plus grand et laisser le plus petit inchangé. Puis, recommencer ainsi avec la nouvelle paire jusqu'à ce que un des deux nombres soit nul. Dans ce cas, l'autre nombre est le PGCD

9) Lire deux nombres entiers N1 et N2. Assigner à N1 la valeur de N2 et à N2 la valeur du reste de la division de N1 par N2. Puis recommencer jusqu'à ce que le reste de la division soit nul. A ce moment, N1 contient le PGCD.

10) Calculer ab avec a réel et b entier par multiplications successives.

11) Rédigez en LDA un algorithme qui réalise le jeu suivant:
(a) A tour de rôle, l'ordinateur et le joueur choisissent un nombre qui ne peut prendre que 3 valeurs: 0, 1 ou 2.
Note: l'instruction

      N <-- RANDOM(3)
réalise le choix de l'ordinateur.
(b) Si la différence entre les nombres choisis vaut
  • 2, le joueur qui a proposé le plus grand nombre gagne un point
  • 1, le joueur qui a proposé le plus petit nombre gagne un point
  • 0, aucun point n'est marqué.
(c) Le jeu se termine quand un des deux joueurs (l'ordinateur ou le joueur humain) totalise 10 points ou quand l'être humain introduit un nombre négatif qui indique sa volonté d'arrêter de jouer.

Pour voir d'autres exercices (avec solution), cliquez ici.



Page précédente.