Les instructions de boucle
En programmation, il arrive très souvent que vous deviez effectuer des opérations en boucle. Par exemple, faire un traitement sur tous les pixels d'une image. Le langage Pascal propose 3 instructions de boucle ayant leur particularité.
L'instruction For fait varier une variable de type ordinale (Entier ou char) de manière croissante ou décroissante
L'instruction While est une boucle qui s'exécute tant que les conditions de la boucle sont remplies : Cette boucle peut s'arrêter dès le début.
L'instruction Repeat fait la même chose que While à part que la boucle s'exécute au moins une fois avant de rencontrer les conditions.
Structure d'une boucle For
La structure d'une boucle FOR est définie comme suit :
Var
i : word;
c : char;
Begin
for i:=1 to 10 do
writeln(i);
for c:='Z' downto 'A' DO
writeln(c);
readln;
End.
var
r:real;
begin
for r:=1 to 10 do;
readln;
end.
Contrairement au Basic, il n'y a pas de possibilité de changer la taille du pas, et contrairement au langage C (et Java, PHP etc), il n'y a pas possibilité de mettre plusieurs conditions de sortie de boucle avec FOR. Pour cela, utilisez l'instruction WHILE ou REPEAT décrit après dans ce chapitre.
Dans une boucle for, l'index NE PEUT PAS changer de valeurs en dehors de ce que le programme Pascal fait (incrémentation ou décrémentation). Ainsi si vous essayez d'exécuter le code suivant :
{...}
for i:=1 to 10 do
if i=5 then
i:= 2*i;
{...}
Exemple : somme des N premiers entiers
Soit le programme suivant
Program boucle1a;
Var
i,n : word;
r:LongInt;
Begin
r:=0;
write ('Valeur de N ? (<65535) ');
readln(n);
writeln ('le calcul par méthode itérative se fait...');
for i:=1 to N do
r:= r + i;
writeln('La somme des ',n
,' premiers entiers (méthode itérative) est : '#10#13,
r);
readln;
End.
- Si on saisit 65535, il y a une erreur de dépassement de capacité pour R (Résultat de type LongInt), car la valeur limite de R est +231
- Si on saisit 65536 et au delà, le programme affichera le nombre saisi comme étant N Modulo 65536 ! Ce qui est logique puisqu'on a défini N comme type WORD, le programme ne gardant, après la lecture de N (avec readln), que le reste de la division entière de N par 65536
Program boucle1b;
Var
i,n : LongInt;
r:Real;
Begin
r:=0;
write ('Valeur de N ? (< 2 milliards) ');
readln(n);
writeln ('le calcul par méthode itérative se fait...');
for i:=1 to N do
r:= r + i;
writeln('La somme des ',n
,' premiers entiers (méthode itérative) est : '#10#13,
r:10:0);
readln;
End.
- A partir de N = 300.000 pour un processeur Motorola 68020/30 à 16 MHz
- A partir de N = 700.000 pour un coprocesseur arithmétique 68882 à 32 MHz avec le type real (10 octets)
- A partir de N = 2.500.000 pour le même coprocesseur 68882 mais avec le type extended (12 octets) au lieu de Real pour la variable r ou avec MC 68040 ou 486 à 32 MHz. Attention : le type extended est SPECIFIQUE aux coprocesseurs arithmétiques MC 68881/688882 de Motorola et accélère grandement les opérations sur les flottants.
- A partir de N=10.000.000 pour les processeurs Pentium à 50 MHz ou les motorola 68060 à 50 MHz
- A partir de N=50.000.000 pour les RISC PC 100 MHz ou ColdFire 100 MHz
- A partir de N=500.000.000 pour les Pentium 1 GHz
Program boucle1c;
Var
i,n : LongInt;
r:Real;
Begin
r:=0;
write ('Valeur de N ? (< 2 milliards) ');
readln(n);
writeln ('le calcul par méthode itérative se fait...');
for i:=1 to N do
r:= r + i;
writeln('La somme des ',n
,' premiers entiers (méthode itérative) est : '#10#13,
r:10:0);
writeln ('Appuyez sur Entrée pour continuer');
readln;
writeln ('le calcul par méthode rapide se fait...');
r:= n/2 * (n+1);
writeln('La somme des ',n
,' premiers entiers (méthode rapide) est : '#10#13,
r:10:0);
readln;
End.
Il est important de connaître la façon dont le compilateur Pascal agit sur les conversions de type avec les opérations. Si au lieu de r:=n /2*(n+1);,vous aviez écrit r:=n*(n+1)/2; le résultat aurait été faux pour des grandes valeurs de N (au delà de 65536), ou cela aurait entraîné une erreur pendant l'exécution.
Si vous n'avez pas la possibilité d'effectuer une opération de conversion en réel dès le début, utilisez une valeur réelle comme 0.0 (en cas de somme ou différence) ou 1.0 (en cas de produit ou division) : ainsi, pour notre code, vous auriez pu écrire simplement r:= 1.0 * n*(n+1)/2; ou r:= 0.0 + n*(n+1)/2; qui aurait effectué la conversion en réel dès le début.
Important : pour la méthode rapide, le type du résultat, dans ce cas particulier doit posséder le double d'octets de la valeur initiale puisque le résultat doit pouvoir contenir au moins le carré de la valeur maximale de N (231). Il est important d'analyser les valeurs limites des opérations mathématiques avant de choisir les types adéquats des variables.
La recherche d'optimisation algorithmique est un travail important des développeurs informatique, en réduisant la Complexité des algorithmes. Plus un algorithme utilise de boucles et plus il est d'une grande complexité. Ici N est passé de la complexité O(N) à O(1)... O(N) signifie que la complexité est proportionnelle à N et O(1), qu'elle ne demande qu'une opération.
Exercices
- Démontrez par récurence la méthode rapide pour la somme des N premiers entiers du programme ci dessus
- Créez un programme d'une boucle allant de 1 à 1000, donnant le nombre d'entiers dont la somme des chiffres est exactement 18. Aide : on obtient le chiffre d'un nombre en faisant N mod 10, puis on effectue n div 10 pour obtenir le chiffre suivant...
- En partant du programme de la somme des N premiers entiers, écrivez un programme calculant la somme des carrés des n premiers entiers. La méthode rapide pour calculer cette série est n*(n+1)*(2*n+1)/6 : remplacez la formule rapide précédente par cette formule (Ne pas oublier d'effectuer la conversion en réel sur la première opération). Combien de chiffres a le résultat r pour N=500000 ? Avez-vous les 2 mêmes résultats pour N=500000 ?
Vous avez ici un exemple des limites à utiliser des types à octets limités (4 octets pour LongInt et 10 pour Real) : En effet, en faisant le produit de 3 entiers à 4 octets, il faudrait un type ayant au moins 12 octets (alors que le type réal n'en a que 10 dont 2 pour l'exposant.
Pour éviter ce genre de problème,il existe un format de données sous forme de chaînes de caractères, non présent en Pascal, ni en C, Java ou Python, appelé BCMath (en PHP) effectuant des opérations sur de très grands nombres basé sur une chaîne de caractères (plus de 2 milliards de chiffres possibles maxi). Une unité BCMath est prévu dans les algorithmes de ce site web (vérifiez la page "Algorithme").
Boucle While
La boucle While est utilisée pour effectuer un même ensemble d'instructions Tant que les conditions initiales sont satisfaites.Exemple 1
var
i : word;
begin
i:=1;
while (i mod 7 <> 0) and (i mod 13 <> 0) do
inc(i);
writeln('Le premier nombre divisible par 7 ',
'et par 13 est : 'i);
readln
end.
La fonction inc() est une des nombreuses fonctions système de Pascal. Cette fonction incrémente la variable donnée en argument. La présence d'un 2ème paramètre indique que variable sera incrémentée de la valeur de ce paramètre. Ainsi inc(n,3) incrémente-t-il n de 3. De même il existe une fonction dec() effectuant la décrémentation d'une variable (avec la présence optionnelle du pas de décrémentation).
La boucle while permet de modifier de n'importe quelle façon les variables entrant dans les conditions de sortie. Ainsi on aurait pu écrire le programme précédent d'une autre façon :
var
i,j : word;
begin
i:=7;
j:=13;
while i <> j do
begin
inc(i,7);
inc(j,13);
end;
writeln('Le premier nombre divisible par 7 ',
'et par 13 est : 'i);
readln
end.
Lorsqu'on aura ajouté 12 fois 7 à i (i vaudra 7 × 13) et 6 fois 13 à j (j vaudra 13 × 7), on sortira de la boucle.
La différence d'avec le programme précédent est :
- il n'y a qu'une seule condition de sortie
- on incrémente i de 7 et j de 13 à chaque boucle.
Retour sur la somme des N premiers entiers
Nous allons reprendre notre programme de somme des N premiers entiers. Avec la boucle while, vous pouvez interdire la saisie de certaines valeurs avant d'exécuter la boucle FOR :
Program boucle2a;
Var
i,n ,r:LongInt;
Begin
r:=0;
write ('Valeur de N ? (<65535) ');
readln(n);
while n > 65534 do
begin
write ('Valeur de N ? (<65535) ');
readln(n);
end;
writeln ('le calcul par méthode itérative se fait...');
for i:=1 to N do
r:= r + i;
writeln('La somme des ',n
,' premiers entiers (méthode itérative) est : '#10#13,
r);
readln;
End.
Program boucle2c;
Var
i,n : LongInt;
r:Real;
Begin
r:=0;
write ('Valeur de N ? (< 2 milliards) ');
readln(n);
while n > 2000000000
begin
write ('Valeur de N ? (< 2 milliards) ');
readln(n);
end;
writeln ('le calcul par méthode itérative se fait...');
for i:=1 to N do
r:= r + i;
writeln('La somme des ',n
,' premiers entiers (méthode itérative) est : '#10#13,
r:10:0);
writeln ('Appuyez sur Entrée pour continuer');
readln;
writeln ('le calcul par méthode rapide se fait...');
r:= n/2 * (n+1);
writeln('La somme des ',n
,' premiers entiers (méthode rapide) est : '#10#13,
r:10:0);
readln;
End.
Dans vos logiciels utilisant la méthode rapide, vous devez utiliser une condition de validation (If ou while) au delà de laquelle le résultat serait faux. Pour cela, créer un algorithme comparant les résultats des 2 algorithmes (dans une boucle for) serait approprié.
Exercices
- Reprendre l'algorithme de la somme des carrés vu dans le paragraphe FOR. Etudier les valeurs limites possible pour N par rapport à R et l'intégrer dans une condition while comme le programme boucle2c ci-dessus,mais en n'utilisant que la méthode RAPIDE (r = n*(n+1)*(2*n+1)/6 ).
- Ecrire un programme utilisant une variable réelle R que vous initialisez avec une valeur quelconque et un compteur i. Faites une boucle while de laquelle vous ne sortirez que quand R sera nul, sachant qu'à chaque boucle, vous divisez R par 2. Pourquoi R finit-il par prendre la valeur 0 alors qu'il s'agit d'un réel et, qu'à priori, R ne peut pas prendre la valeur 0 quand on le divise infiniment par 2 ?
Important
La condition de sortie d'une boucle while est NON (ensemble de condition pour continuer la boucle). Ainsi si vous avez un ensemble de conditions While condition 1 and condition2 ou condition3 la sortie s'effectuera avec (Non condition1) ou (Non condition2) et (non condition3).Boucle Repeat
Au contraire de l'instruction while, l'instruction Repeat (Répéter) exécute une suite d'instructions avant de tester des conditions de sortie.On peut ainsi reprendre le programme boucle2a précédent en remplaçant l'instruction While par Repeat :
Program boucle2a;
Var
i,n ,r:LongInt;
Begin
r:=0;
Repeat
write ('Valeur de N ? (<65535) ');
readln(n);
until n <= 65534;
writeln ('le calcul par méthode itérative se fait...');
for i:=1 to N do
r:= r + i;
writeln('La somme des ',n
,' premiers entiers (méthode itérative) est : '#10#13,
r);
readln;
End.
Les contitions de sortie sont indiquées après le mot clé Until (Jusqu'à), et ces conditions sont l'opposé des conditions pour rester dans la boucle (au contraire de While).
Si un ensemble d'instructions doit être exécuté dans Repeat, on n'utilise PAS les mot clé Begin et End, puisque tout ce qui est entre Repeat et Until est exécuté!
Instruction GOTO
A l'instar d'autres langages de programmation plus "BASIC" (ainsi que le langage C), vous pouvez utiliser l'instruction GOTO. Cependant tous les bons enseignants en programmation informatique vous déconseilleront voire interdirons l'utilisation de cette méthode qui peut vite devenir un sac de noeuds dans la gestion des variables. Le LANGAGE Basic, qui ne possède pas de structures (pas de procédure ou fonction), ni de boucle WHILE est un langage impropre à la création de programmes solides et structurés (Hormis le GFA BAsic des Atari ST).Donc je me joins à ces enseignants (une pensée pour mon mentor Michel Lalos qui nous a quitté) pour INTERDIRE l'utilisation de GOTO dans les langages procéduraux tels que Pascal, C, Modula 2, Oberon, Java, PHP etc... Pour les BASIC interprétés, hélas, il n'y a pas d'autres possibilités.. (hormis pour le GFA Basic).
Notions vues dans ce cours
- Boucle For : incrémentation avec TO et décrementation avec DOWNTO
- Algorithme de la somme des N premiers entiers
- Optimisation de cet algorithme
- Notion de complexité algorithmique
- Tests sur les valeurs limites de variables : comment éviter les erreurs de dépassement de limites ?
- Boucle While
- Fonction inc() et dec()