Activité : Tracer l’exécution d’un programme

Mise en situation

Lorsqu’un programme ne fonctionne pas correctement, on doit être capable de comprendre les étapes de son exécution pour trouver le problème. On peut bien sûr utiliser un débogueur symbolique, mais il est important de pouvoir le faire également « à la main ». Cela permet par exemple de faire la trace de l’exécution d’un programme écrit sur du papier ou d’analyser une petite portion de code d’un grand programme. Cela vous permet également de bien comprendre le fonctionnement des structures de contrôle et de l’affectation.

Consigne

Lisez attentivement le texte qui précède chacun des quatre exercices. Chaque partie vous montre comment faire la trace de l’exécution d’un programme à l’aide d’un exemple qui met en œuvre l’une des structures de contrôle (séquence, choix, boucle définie, boucle indéfinie). Prenez le temps de bien étudier la trace d’exécution de chaque exemple avant de faire l’exercice correspondant.

Appliquez-vous à faire la trace sur papier sans utiliser le débogueur. N’utiliser NetBeans et le débogueur que pour vérifier que votre travail est correct. S’il ne l’est pas, reprenez votre travail pour comprendre votre erreur en utilisant les ressources dont vous disposez.

Si vous n’avez pas reçu de fiches, vous pouvez télécharger et imprimer le document tracetable.pdf.

Résultat attendu

Une ou plusieurs fiches pour chacun des quatre exercices :

  • Exercice1 : séquence d’instructions
  • Exercice2 : structure de choix (if-then-else)
  • Exercice3 : structure de boucle définie (for)
  • Exercice4 : structure de boucle indéfinie (while)

Objectifs

À la fin de ce travail, vous devez :

  1. Être capable de tracer l’exécution d’un programme de quelques lignes composé d’affectation et de structures de contôle (séquence, choix et boucles) et de présenter le résultat sous la forme d’un tableau.

Ressources

Logiciel :

  • Aucun

Documents :

Tracer l’exécution d’un programme

Tracer l’exécution d’une séquence

Ce premier exemple vous montre comment faire la trace de l’exécution d’une séquence d’instruction. En l’occurence, il s’agit essentiellement d’une séquence d’affectation.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Exemple1 {

    public static void main(String[] args) {
        int a;
        int b = 5;
        a = b * 3;
        int c = a - b;
        b = c;
        b = b + 20;
        c = (b + a) * 2;
        System.out.print(c);
    }
}
Fig. 1 – Programme Exemple1

La figure 1 montre le programme dont nous voulons faire la trace et la figure 2 montre la trace d’exécution de ce progamme présentée sous la forme d’un tableau.

Pour parvenir à ce résultat, on commence par faire l’inventaire des variables qui seront utilisées en cherchant les déclarations de variables. On reporte le nom de chaque variable dans une des cases prévues à cet effet en haut à gauche du tableau. Dans le programme Exemple1, il y a trois variables : a, b et c.

Fig. 2 – Trace du programme Exemple1
Fig. 2 – Trace du programme Exemple1

On utilise en suite une ligne pour chaque étape de l’exécution du programme. Comme dans le programme Exemple1 il n’y a ni structure de choix ni structure de boucle, chaque instruction est une étape du programme. Bien que cela ne soit pas vraiment des instructions, on reporte également les déclarations dans la trace qu’elles soient ou non combinées à une affectation.

Pour rappel, une affectation s’exécute en deux temps :

  1. Évaluation de l’expression de la partie droite.
  2. Affectation de la valeur de l’expression à la variable de la partie gauche.

Pour évaluer l’expression, il suffit de remplacer les variables, s’il y en a, par leur valeur à la fin de l’étape précédente, puis de faire le calcul en respectant les règles de priorité des opérations. Pour finir, on écrit la valeur de chaque variable dans la colonne correspondante en utilisant éventuellement une couleur différente pour indiquer la valeur qui a été modifiée par cette étape. Si la valeur d’une variable n’est pas définie, on l’indique à l’aide d’un tiret.

Exercice 1 : Faites la trace du programme suivant en utilisant les fiches que vous avez reçues et expliquez ce que font les lignes 9, 10 et 11 de ce programme.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Exercice1 {

    public static void main(String[] args) {
        int y;
        int x = 5;
        int a = 5;
        int b = 10;
        
        int tmp = a;
        a = b;
        b = tmp;

        y = a * x + b;

        System.out.print(y);
    }
}

Tracer l’exécution d’une structure de choix

Pour faire la trace d’un programme, on doit parfois faire des suppositions. Dans l’exemple de la figure 3, on demande à l’utilisateur de saisir un nombre. Comme la trace de l’exécution dépend de la valeur saisie, on doit admettre une valeur et exécuter le programme avec cette valeur.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Exemple2 {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        
        double val = input.nextDouble();
        double res;

        if (val >= 10 && val <= 20) {
            res = -val;
        } else {
            res = val * 2;
        }

        res = res + 20;

        System.out.print(res);
    }
}
Fig. 3 – Programme Exemple2

De plus, ce programme contient une structure de choix dont la condition du choix dépend de la valeur saisie par l’utilisateur. Il y a donc deux chemins d’exécution possibles. Pour illustrer cela, la figure 4 montre un organigramme de progammation(ou simplement organigramme) qui permet de bien visualiser les deux chemins que peut suivre le fil d’exécution dans une structure de choix.

image/svg+xmlStart Condition du choix Instruction 1 condition non remplie Instruction 2 condition non remplie Instructions 1 condition remplie Instructions avant la structure de choix Stop vrai faux (else) Instruction 2 condition remplie
Fig. 4 – Organigramme d'une structure de choix

La trace de l’exécution pour une valeur donnée ne suivra qu’un seul de ces deux chemins. Si l’on veut analyser les deux chemins, on doit faire la trace une première fois avec une valeur qui remplit la condition, puis une seconde fois avec une valeur qui ne la remplit pas. La figure 5 montre deux traces d’exécution possible du programme Exemple2.

Fig. 6 – Deux traces d'exécution possibles du programme Exemple2
Fig. 5 – Deux traces d'exécution possibles du programme Exemple2

Remarquez dans ces traces, comment on peut utiliser deux lignes du tableau pour une seule étape (étape 2), dans le cas où les espaces réservés à l’instruction ou comme ici à la description et aux remarques seraient insuffisants.

Exercice 2 : Faites les traces de trois exécution du programme Exercice2 en admettant que la première fois l’utilisateur saisis un 10, la deuxième fois un 20 et la troisième fois un 40. Est-ce que tous les chemins possibles ont été empruntés ? Décrivez à quelles intervalles correspond chacune des deux conditions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Exercice2 {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        
        int res;
        int n = input.nextInt();

        if (n > 10 && n <= 20) {
            res = n * 3;
        } else if (n <= 10 || n > 40) {
            res = n * 8;
        } else {
            res = n;
        }

        System.out.println(res);
    }
}

Tracer l’exécution d’une boucle for

Une boucle for permet de répéter une ou plusieurs instructions un nombre de fois bien définie. Pour rappel, une boucle définie (ou boucle for) dit que l’on doit répéter les instructions pour chaque valeur entière comprise entre un minimum et un maximum de la variable de boucle (généralement i).

L’exécution d’une boucle for comprend plusieurs étapes :

  1. Initialiser la variable de boucle (int i = min).
  2. Évaluation de la condition de continuation (i <= max); si la condition n’est pas remplie, aller au point 6.
  3. Exécuter les instructions du corps de la boucle.
  4. Incrémenter la variable de boucle (i = i + 1)
  5. Recommencer à au point 2.
  6. Fin de la boucle.

La figure 6 montre ces étapes sous la forme d’un organigramme. On peut remarquer en gras, les trois parties que l’on retrouve dans la syntaxe de la boucle for en Java.

image/svg+xmlStart Initialiser la variable de boucle int i = min Condition de continuation i <= max Instruction 1 du corps de la boucle Instruction 2 du corps de la boucle Incrémenter la variable de boucle i = i + 1 Instructions après la boucle for Instructions avant la boucle for Stop vrai faux
Fig. 6 – Organigramme d'une boucle for

Le programme de la figure 7 calcule la somme des 5 premiers nombres entiers à l’aide d’une boucle for. La valeur min est 1 (int i = 1), la valeur max est 5 (i <= 5) et le pas est de 1 (i = i + 1 ou, en version abrégée : i += 1).

1
2
3
4
5
6
7
8
9
10
11
12
public class Exemple3 {

    public static void main(String[] args) {
        int sum = 0;

        for (int i = 1; i <= 5; i += 1) {
          sum = sum + i;
        }

        System.out.print(sum);
    }
}
Fig. 7 – Programme Exemple3

La figure 8 montre la trace de l’exécution de ce programme. On peut remarquer que même si le programme est très court, la trace, elle, est plutôt longue. Cela vient du fait que lorsque l’on fait la trace d’un programme qui contient une boucle, on doit répéter les instructions du corps de la boule, l’instruction d’incrémentation de la variable de boucle et le test de la condition de continuation autant de fois que nécessaire.

Fig. 10 – Trace du programme Exemple3
Fig. 8 – Trace du programme Exemple3

Repérez comment on a représenté la répétition des instructions, l’incrémentation de la variable de boucle et le test de la condition de continuation dans la trace.

Exercice 3 : Faites la trace d’exécution du programme Exercice3 et expliquez ce que fait le programme. La fonction charAt permet d’obtenir le caractère qui se trouve à une certaine position de la chaîne de caractères. La position est passée en paramètre. Le premier caractère de la chaîne (à gauche) est à la position 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Exercice3 {

    public static void main(String[] args) {
        String s = "abcd";
        String res = "";

        for (int i = 0; i < s.length(); i += 1) {
            char c = s.charAt(i);
            res = c + res;
        }

        System.out.println(res);
    }
}

Tracer l’exécution d’une boucle while

Une boucle for est une boucle définie, c’est-à-dire que l’on connaît au moment d’entrer dans la boucle, le nombre de répétitions des instructions du corps de la boucle. Lorsque ce nombre n’est pas connu, on utilise une boucle indéfinie. En Java, on utilise pour cela une boucle while (tant que). Avec une telle boucle, les instructions du corps de la boucle sont répétées tant que la condition de continuation est remplie ou, dis autrement, que l’expression booléenne est vérifiée.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Exemple4 {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        
        int val = input.nextInt();
        
        String result = "";
        int quotient = val;

        while (quotient > 0) {
            int rest = quotient % 2;
            result = rest + result;
            quotient = quotient / 2;
        }

        System.out.print(result);
    }
}
Fig. 9 – Programme Exemple4

Le programme de la figure 9 utilise une boucle indéfinie pour convertir un nombre de la base 10 à la base 2 à l’aide de divisions successives. Comme le montre l’organigramme la figure 10, l’exécution d’une boucle while commence par le test de la condition de continuation. Pour le cas, où l’on souhaiterait que le test se fasse à la fin de la boucle, on peut utiliser une boucle do-while.

image/svg+xmlStart Condition de continuation Instruction 1 du corps de la boucle Instruction 2 du corps de la boucle Instructions après la boucle while Instructions avant la boucle while Stop vrai faux
Fig. 10 – Organigramme d'une boucle while

La figure 11 montre la trace de l’exécution du programme Exemple4 lorsque l’utilisateur saisit la valeur 5.

Fig. 5 – Trace du programme Exemple4
Fig. 11 – Trace du programme Exemple4

Exercice 4 : Faites la trace d’exécution du programme Exercice4 et expliquez ce que fait le programme. Proposez ensuite une manière plus simple d’écrire la condition de la boucle while et refaite la trace pour vérifier que vous parvenez au même résultat.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Exercice4 {

    public static void main(String[] args) {
       int a = 24;
       int b = 6;
       int q = 0;
       int r;

       while ((a - b) > 0 || (b - a) == 0) {
           a = a - b;
           q = q + 1;
       }

       r = a;

       System.out.println(q);
       System.out.println(r);
    }
}

Exercice 5 : Entraînez-vous à tracer l’exécution d’un programme avec l’un ou l’autre des programmes que vous avez déjà fait.