Précédent Remonter Suivant

Chapitre 2  Suite d'instructions

Dans ce chapitre on s'intéresse à deux types d'instructions: les instructions conditionnelles, qui permettent d'effectuer une opération dans le cas où une certaine condition est satisfaite et les itérations qui donnent la possibilité de répéter plusieurs fois la même instruction (pour des valeurs différentes des variables!).

2.1  Expressions booléennes

Le point commun aux diverses instructions décrites ci-dessous est qu'elles utilisent des expressions booléennes, c'est-à-dire dont l'évaluation donne l'une des deux valeurs true ou false.

2.1.1  Opérateurs de comparaisons

Les opérateurs booléens les plus simples sont
== != < > <= >=


Le résultat d'une comparaison sur des variables de type primitif:
a == b
est égal à true si l'évaluation de la variable a et de la variable b donnent le même résultat, il est égal à false sinon. Par exemple, (5-2) == 3 a pour valeur true, mais 22/7 == 3.14159 a pour valeur false.

Remarque: Attention à ne pas écrire a = b qui est une affectation et pas une comparaison.

L'opérateur != est l'opposé de ==, ainsi a != b prend la valeur true si l'évaluation de a et de b donne des valeurs différentes.

Les opérateurs de comparaison <, >, <=, >= ont des significations évidentes lorsqu'il s'agit de comparer des nombres. Noter qu'ils peuvent aussi servir à comparer des caractères; pour les caractères latins courants c'est l'ordre alphabétique qui est exprimé.

2.1.2  Connecteurs

On peut construire des expressions booléennes comportant plusieurs comparateurs en utilisant les connecteurs &&, qui signifie et, || qui signifie ou et ! qui signifie non.

Ainsi C1 && C2 est évalué à true si et seulement si les deux expressions C1 et C2 le sont. De même C1 || C2 est évalué à true si l'une deux expressions C1 ou C2 l'est.

Par exemple
!( ((a<c) && (c<b) && (b<d)) || ((c<a) && (a<d) && (d<b)) )
est une façon de tester si deux intervalles [a,b] et [c,d] sont disjoints ou contenus l'un dans l'autre.

Règle d'évaluation: en Java l'évaluation de l'expression C1 && C2 s'effectue dans l'ordre C1 puis C2 si nécessaire; ainsi si C1 est évaluée à false alors C2 n'est pas évaluée. C'est aussi le cas pour C1 || C2 qui est évaluée à true si c'est le cas pour C1 et ceci sans que C2 ne soit évaluée. Par exemple l'évaluation de l'expression
(3 > 4) && (2/0 > 0)

donne pour résultat false alors que
(2/0 > 0) && (3 > 4)
donne lieu à une erreur provoquée par la division par zéro et levant une exception (voir annexe).

2.2  Instructions conditionnelles

Il s'agit d'instructions permettant de n'effectuer une opération que si une certaine condition est satisfaite ou de programmer une alternative entre deux options.

2.2.1  If-else

La plus simple de ces instructions est celle de la forme:
    if(C)
        I1
    else
        I2
Dans cette écriture C est une expression booléenne (attention à ne pas oublier les parenthèses autour); I1 et I2 sont formées ou bien d'une seule instruction ou bien d'une suite d'instructions à l'intérieur d'une paire d'accolades { }. On rappelle que chaque instruction de Java se termine par un point virgule (;, symbole qui fait donc partie de l'instruction). Par exemple, les instructions
    if(a >= 0)
        b = 1;
    else
        b = -1;
permettent de calculer le signe de a et de le mettre dans b.

La partie else I2 est facultative, elle est omise si la suite I2 est vide c'est à dire s'il n'y a aucune instruction à exécuter dans le cas où C est évaluée à false.

On peut avoir plusieurs branches séparées par des else if comme par exemple dans:
    if(a == 0 )      x = 1;
    else if (a < 0)  x = 2;
    else if (a > -5) x = 3;
    else             x = 4;
qui donne 4 valeurs possibles pour x suivant les valeurs de a.

2.2.2  Forme compacte

Il existe une forme compacte de l'instruction conditionnelle utilisée comme un opérateur ternaire (à trois opérandes) dont le premier est un booléen et les deux autres sont de type primitif. Cet opérateur s'écrit C ? E1 : E2. Elle est utilisée quand un if else paraît lourd, par exemple pour le calcul d'une valeur absolue:
    x = (a > b)? a - b : b - a;

2.2.3  Aiguillage

Quand diverses instructions sont à réaliser suivant les valeurs que prend une variable, plusieurs if imbriqués deviennent lourds à mettre en oeuvre, on peut les remplacer avantageusement par un aiguillage switch. Un tel aiguillage a la forme suivante dans laquelle x est une variable d'un type primitif et a,b,c sont des constantes représentant des valeurs que peut prendre cette variable. Lors de l'exécution les valeurs après chaque case sont testées l'une après l'autre jusqu'à obtenir celle prise par x ou arriver à default, ensuite toutes les instructions sont exécutées en séquence jusqu'à la fin. Par exemple dans l'instruction:
    switch(x){
    case a  : I1
    case b  : I2
    case c  : I3
    default : I4
    }
Si la variable x est évaluée à b alors toutes les suites d'instructions I2, I3, I4 seront exécutées, à moins que l'une d'entre elles ne contienne un break qui interrompt cette suite. Si la variable est évaluée à une valeur différente de a,b,c c'est la suite I4 qui est exécutée.

Pour sortir de l'instruction avant la fin, il faut passer par une instruction break . Le programme suivant est un exemple typique d'utilisation:

    switch(c){
    case 's':
        System.out.println("samedi est un jour de week-end");
        break;
    case 'd':
        System.out.println("dimanche est un jour de week-end");
        break;
    default:
        System.out.print(c);
        System.out.println(" n'est pas un jour de week-end");
        break;
    }
permet d'afficher les jours du week-end. Si l'on écrit plutôt de façon erronée:
    switch(c){
    case 's':
        System.out.println("samedi est un jour de week-end");
    case 'd':
        System.out.println("dimanche est un jour de week-end");
    default:
        System.out.print(c);
        System.out.println(" n'est pas un jour de week-end");
        break;
  }
on obtiendra, dans le cas où c s'évalue à 's':
samedi est un jour de week-end
dimanche est un jour de week-end
s n'est pas un jour de week-end

2.3  Itérations

Une itération permet de répéter plusieurs fois la même suite d'instructions. Elle est utilisée pour évaluer une somme, une suite récurrente, le calcul d'un plus grand commun diviseur par exemple. Elle sert aussi pour effectuer des traitements plus informatiques comme la lecture d'un fichier. On a l'habitude de distinguer les boucles pour des boucles tant-que. Les premières sont utilisées lorsqu'on connaît, lors de l'écriture du programme, le nombre de fois où les opérations doivent être itérées, les secondes servent à exprimer des tests d'arrêt dont le résultat n'est pas prévisible à l'avance. Par exemple le calcul d'une somme de valeurs pour i variant de 1 à n est de la catégorie boucle-pour celui du calcul d'un plus grand commun diviseur par l'algorithme d'Euclide relève d'une boucle tant-que.

2.3.1  Boucles pour

L'itération de type boucle-pour en Java est un peu déroutante pour ceux qui la découvrent pour la première fois. L'exemple le plus courant est celui où on exécute une suite d'opérations pour i variant de 1 à n, comme dans:
    int i;
    for(i = 1; i <= n; i++)
        System.out.println(i);
Ici, on a affiché tous les entiers entre 1 et n. Prenons l'exemple de n=2 et déroulons les calculs faits par l'ordinateur:

Une forme encore plus courante est celle où on déclare i dans la boucle:
    for(int i = 1; i <= n; i++)
        System.out.println(i);
Dans ce cas, on n'a pas accès à la variable i en dehors du corps de la boucle.

Un autre exemple est le calcul de la somme



qui se fait par
    double s = 0.0;
    for(int i = 1; i <= n; i++)
        s = s + 1/((double)i);
La conversion explicite est ici nécessaire, car sinon la ligne plus naturelle:
        s = s + 1/i;
conduit à évaluer d'abord 1/i comme une opération entière, autrement dit le quotient de 1 par i, i.e., 0. Et la valeur finale de s serait toujours 1.0.



La forme générale est la suivante:
    for(Init; C; Inc)
        I
Dans cette écriture Init est une initialisation (pouvant comporter une déclaration), Inc est une incrémentation, et C un test d'arrêt, ce sont des expressions qui ne se terminent pas par un point virgule. Quant à I, c'est le corps de la boucle constitué d'une seule instruction ou d'une suite d'instructions entre accolades. Init est exécutée en premier, ensuite la condition C est évaluée si sa valeur est true alors la suite d'instructions I est exécutée suivie de l'instruction d'incrémentation Inc et un nouveau tour de boucle reprend avec l'évaluation de C. Noter que Init peut être composée d'une seule expression ou bien de plusieurs, séparées par des , (virgules).

Noter que les instructions Init ou Inc de la forme générale (ou même les deux) peuvent être vides. Il n'y a alors pas d'initialisation ou pas d'incrémentation; l'initialisation peut, dans ce cas, figurer avant le for et l'incrémentation à l'intérieur de I.

Insistons sur le fait que la boucle
    for(int i = 1; i <= n; i++)
        System.out.println(i);
peut également s'écrire:
    for(int i = 1; i <= n; i++)
    {
        System.out.println(i);
    }
pour faire ressortir le bloc d'instructions, ou encore:
    for(int i = 1; i <= n; i++){
        System.out.println(i);
    }
ce qui fait gagner une ligne...

2.3.2  Itérations tant que

Une telle instruction a la forme suivante:
    while(C)
        I
C est une condition et I une instruction ou un bloc d'instructions. L'itération évalue C et exécute I si le résultat est true, cette suite est répétée tant que l'évaluation de C donne la valeur true.

Un exemple classique de l'utilisation de while est le calcul du pgcd de deux nombres par l'algorithme d'Euclide. Cet algorithme consiste à remplacer le calcul de pgcd(a,b) par celui de pgcd(b,r) où r est le reste de la division de a par b et ceci tant que r ≢ 0.
    while(b != 0){
        r = a % b;
        a = b;
        b = r;
    }
Examinons ce qu'il se passe avec a=28, b=16.

Notons enfin que boucles pour ou tant-que sont presque toujours interchangeables. Ainsi une forme équivalente de
    double s = 0.0;
    for(int i = 1; i <= n; i++)
        s += 1/((double)i);
est
    double s = 0.0;
    int i = 1;
    while(i <= n){
        s += 1/((double)i);
        i++;
    }
mais que la première forme est plus compacte que la seconde. On a tendance à utiliser une boucle for quand on peut prévoir le nombre d'itérations, et while dans les autres cas.

2.3.3  Itérations répéter tant que

Il s'agit ici d'effectuer l'instruction I et de ne la répéter que si la condition C est vérifiée. La syntaxe est:
    do
       I
    while(C)
À titre d'exemple, le problème de Syracuse est le suivant: soit m un entier plus grand que 1. On définit la suite un par u0 = m et



(la notation n ÷ 2 désigne le quotient de la division euclidienne de n par 2). Il est conjecturé, mais non encore prouvé que pour tout m, la suite prend la valeur 1 au bout d'un temps fini.

Pour vérifier numériquement cette conjecture, on écrit le programme Java suivant:
class Syracuse{
    public static void main(String[] args){
        int n = Integer.parseInt(args[0]);

        do{
            if((n % 2) == 0)
                n /= 2;
            else
                n = 3*n+1;
        } while(n > 1);
        return;
    }
}

que l'on appelle par:
unix% java Syracuse 101
L'instruction magique Integer.parseInt(args[0]); permet de récupérer la valeur de l'entier 101 passé sur la ligne de commande.

2.4  Terminaison des programmes

Le programme que nous venons de voir peut être considéré comme étrange, voire dangereux. En effet, si la conjecture est fausse, alors le programme ne va jamais s'arrêter, on dit qu'il ne termine pas. Le problème de la terminaison des programmes est fondamental en programmation. Il faut toujours se demander si le programme qu'on écrit va terminer. D'un point de vue théorique, il est impossible de trouver un algorithme pour faire cela (cf. chapitre 6). D'un point de vue pratique, on doit examiner chaque boucle ou itération et prouver que chacune termine.

Voici quelques erreurs classiques, qui toutes simulent le mouvement perpétuel:
    int i = 0;
    while(true)
        i++;
ou bien
    for(i = 0; i >= 0; i++)
        ;
On s'attachera à prouver que les algorithmes que nous étudions terminent bien.

2.5  Instructions de rupture de contrôle

Il y a trois telles instructions qui sont return, break et continue. L'instruction return doit être utilisée dans toutes les fonctions qui calculent un résultat (cf. chapitre suivant).

Les deux autres instructions de rupture sont beaucoup moins utilisées et peuvent être omises en première lecture. L'instruction break permet d'interrompre une suite d'instructions dans une boucle pour passer à l'instruction qui suit la boucle dans le texte du programme.

L'instruction continue a un effet similaire à celui de break, mais redonne le contrôle à l'itération suivante de la boucle au lieu d'en sortir.

2.6  Exemples

2.6.1  Méthode de Newton

On rappelle que si f est une fonction suffisamment raisonnable de la variable réelle, alors la suite



converge vers une racine de f à partir d'un point de départ bien choisi.

Si f(x) = x2-a avec a>0, la suite converge vers √ . Dans ce cas particulier, la récurrence s'écrit:



On itère en partant de x0=a, et on s'arrête quand la différence entre deux valeurs consécutives est plus petite que ε > 0 donné. Cette façon de faire est plus stable numériquement (et moins coûteuse) que de tester |xn2-a|≤ ε. Si on veut calculer √  par cette méthode en Java, on écrit:
class Newton{
    public static void main(String[] args){
        double a = 2.0, x, xold, eps;

        x = a;
        eps = 1e-10;
        do{
            // recopie de la valeur ancienne
            xold = x;
            // calcul de la nouvelle valeur
            x = (xold+a/xold)/2;
            System.out.println(x);
        } while(Math.abs(x-xold) > eps);
        System.out.print("Sqrt(a)=");
        System.out.println(x);
        return;
    }
}
ce qui donne:
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.4142135623730949
Sqrt(2)=1.4142135623730949
On peut également vérifier le calcul en comparant avec la fonction Math.sqrt() de Java.

Comment prouve-t-on que cet algorithme termine ? Ici, il suffit de prouver que la suite |xn+1-xn| est strictement décroissante, ce qui est vrai puisque la suite (xn) converge (elle est décroissante, minorée par √ ).



Exercice 1. On considère la suite calculant 1/√  par la méthode de Newton, en utilisant f(x)=a-1/x2:



Écrire une fonction Java qui calcule cette suite, et en déduire le calcul de √ . Cette suite converge-t-elle plus ou moins vite que la suite donnée ci-dessus ?
Précédent Remonter Suivant