LES STRUCTURES REPETITIVES.

 lire N
 i <-- N+1
 tant que NOT (i est premier) faire
   i <-- i+1
 ftant
 écrire i

 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

 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

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

 répéter
     séquence d'instructions
 jusqu'à (expression logique)

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,"%"

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, note_i représentant la note de la ième branche et maxnote_i 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 (branche_i 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 ...

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 note₁,...,note₁₆ les composantes (ou éléments) du tableau note, de même pour maxnote_i et branche_i. 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, note_i, note₃ et note_N-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 a₁, a₂, ..., a_n 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 a₁ et a_j .On cherche ensuite l'indice du plus petit des éléments a₂, a₃, ..., a_n et on permute avec a₂, etc.

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.

 WHILE expression logique DO
    BEGIN
    séquence d'instructions;
    END;

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.

 FOR v.c.:=prem.val. TO dern.val. DO
    BEGIN
    séquence d'instructions
    END;

 FOR v.c.:=prem.val. DOWNTO dern.val.DO
    BEGIN
    séquence d'instructions
    END;

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)

 REPEAT
     séquence d'instructions
 UNTIL (expression logique);

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;

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 a^b 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)

• 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é.

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