Les structures de contrôle

Comme en Python, les structures de contrôle sont organisées en deux grandes catégories :

  • les tests logiques ;

  • et la répétition d’instruction.

Le test logique

Le test logique en C est très similaire à la façon de faire en Python, à deux différences près:

  • les prédicats doivent être encapsulés entre parenthèses ;

  • l’instruction Python elif n’a pas d’équivalent en C. Elle est remplacée par une combinaison de else et if.

Pour illustrer son fonctionnement, considérons la fonction max3() suivante qui retourne le plus grand de 3 nombres entiers :

1int max3(int a, int b, int c)
2{
3    if (a >= b && a >= c)
4        return a;
5    else if (b >= c)
6        return b;
7    else
8        return c;
9}

Exercice

Tracer l’organigramme du programme ci dessus.

Pour réaliser des tests élémentaires, C permet l’utilisation d’un opérateur dit ternaire (il prend trois arguments) dans une expression :

  • un prédicat ;

  • l’évaluation de l’expression si le prédicat est évalué à True ;

  • l’évaluation de l’expression si le prédicat est évalué à False.

La syntaxe générale de l’expression est la suivante

predicat ? expression_if_true : expression_if_false;

L’évaluation de l’expression peut être affectée à une variable :

max = ( a>=b ) ? a : b;

Exercice

Ré écrire la fonction max3() en utilisant les opérateurs ternaires. Pourriez vous réduire le corps de la fonction à une seule ligne ?

La répétition d’instructions

Pour répéter un ensemble d’instructions en Python on dispose de 2 constructions :

  • la boucle for ;

  • la boucle while .

Le langage C en propose 3 :

  • la boucle for ;

  • la boucle while ;

  • la boucle do ... while ;

La boucle for

Malgré la similitude des mots clés pour les deux langages, il y a des différences fondamentales pour la boucle for :

  • en Python on itère sur les objets d’une collection (mais les indices correspondants sont accessibles) ;

  • en C, on itère sur des entiers, qui peuvent être utilisés pour accéder aux éléments d’un tableau.

En C, la boucle for est composée de 3 parties :

  • l’initialisation ;

  • la condition de continuation ;

  • l’incrémentation.

L’exemple ci dessous permet d’afficher les nombres entiers positifs, strictement inférieurs à 10 :

1for ( int i = 0; i < 10; i++ ){
2    printf("%d\n", i);
3}

On retrouve les 3 parties identifiées ci dessus :

  • int i = 0 est l’initialisation ;

  • i < 10 est la condition de continuation ;

  • i++ est l’incrémentation.

La boucle while

La boucle while est quasiment identique dans les deux langages. La seule différence est qu’en C le prédicat doit être encapsulé dans une paire de parenthèses.

La boucle while évalue la condition de continuation AVANT l’exécution du bloc d’instructions :

1int i = 0;
2while (i < 10)
3{
4    printf("%d\n", i);
5    i++;
6}

La boucle do ... while

La boucle do ... while est très similaire à la boucle while. La différence est que la condition de continuation est évaluée après l’exécution du bloc d’instructions :

1i = 0;
2do
3{
4    printf("%d\n", i);
5    i++;
6} while (i < 10);

Selon le problème à traiter l’une des deux constructions (while et do ... while) sera plus adaptée et conduira à une écriture plus simple.

Le processus de compilation

Contrôle de l’exécution des boucles

Comme en Python, on dispose de deux instructions permettant de modifier le parcours des boucles. Les deux instructions ont exactement le même fonctionnement :

  • break interrompt le parcours de la boucle et le programme reprend à l’instruction suivant immédiatement la boucle ;

  • continue suspend l’exécution des instructions qui suivent et saute à l’itération suivante ;

Dans le code ci dessous, les chiffres supérieurs ou égaux à 5 ne sont jamais affichés :

1int i = 0;
2while (i < 10)
3{
4    if (i == 5) break ;
5    printf("%d\n", i);
6    i++;
7}

Dans le code ci dessous, le chiffre 5 n’est pas affiché :

1for ( int i = 0; i < 10; i++ ){
2        if (i == 5) continue ;
3        printf("%d\n", i);
4    }

Exercice

Compléter les portions de code ci dessus pour produire un programme complet permettant l’affichage correspondant aux instructions break et continue.

La boucle infinie

Lorsqu’un programme ne se termine pas, il est vraisemblable qu’il contienne une boucle infinie, c’est à dire une boucle pour laquelle la condition de continuation est toujours vraie.

La boucle infinie peut parfois être une construction souhaitée, mais dans ce cas il faut prévoir la scrutation d’un évènement externe qui peut y mettre fin (scrutation du clavier par exemple).

En C une boucle infinie peut s’écrire :

while(1) {
    ...
}

Exercice : comptage des nombres premiers

Lors de l’apprentissage de Python, vous avez écrit un programme permettant d’afficher les nombres premiers strictement inférieurs à n.

L’objectif de cet exercice est de transposer ce code en langage C pour compter les nombres premiers strictement inférieurs à n.

Ecriture des fonctions

Le code source sera stocké dans le fichier primes.c. Il sera structuré de la façon suivante :

  • une directive #include permettant d’utiliser printf() pour l’affichage ;

  • une fonction secondaire isprime():

    • qui prend en argument un nombre entier p, teste tous les diviseurs entre 2 et p ;

    • et retourne la vérité de « p est premier ».

  • et la fonction principale main() qui compte le nombre de nombres premiers jusqu’à n.

Concrètement :

// primes.c

#include <stdio.h>

int isprime(int p){
    // à compléter
    return 0;
}

int main(){
    // à compléter
    return 0;
}

Exercice

Ecrire le corps des fonctions isprime() et main().

Vérifier la validité du programme en comptant le nombre de nombres premiers strictement inférieurs à 100. Si le code source est dans le fichier primes.c:

$ gcc -std=c99 -Wall -Wextra primes.c -o primes
$ ./primes
25

Mesure du temps d’exécution

Utiliser la commande time pour mesurer le temps d’exécution de la recherche de nombre premiers jusqu’à 100000.

A titre indicatif, sur une machine Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz, 16 Go de RAM, Windows 10 64 bits, WSL2/Ubuntu:

$ time ./primes
9592

real    0m0.477s
user    0m0.469s
sys     0m0.000s

Le temps d’exécution est la somme des valeurs user et sys, ici 469 ms.

A titre de comparaison, le temps d’exécution du programme Python équivalent:

$ time python3 primes.py
9592

real    0m10.485s
user    0m10.453s
sys     0m0.031s

Il y a ici un rapport 20 entre les temps d’exécution.

Pour obtenir une mesure plus précise, il est possible de répéter l’exécution du programme plusieurs fois et de calculer la moyenne des temps d’exécution. Par exemple, pour 10 exécutions:

$ time for counter in {1..10}; do ./primes; done

real    0m4.781s
user    0m4.473s
sys     0m0.031s

Ici le programme a été exécuté 10 fois en 4.504s, soit 450 ms en moyenne.

Amélioration des performances

Améliorez le programme en testant la parité puis uniquement les diviseurs impairs inférieurs à \(int(\sqrt{p})+1\). Pour cela il faut :

  • « importer » la définition des fonctions mathématiques

#include <math.h>

  • utiliser la fonction sqrt() de prototype :

double sqrt(double arg);

  • et « caster » le résultat pour le convertir en int :

(int)sqrt(p)

Exercice

Implémenter les modifications ci dessus.

Lors de la construction du programme exécutable, il faut également « lier » la bibliothèque mathématique avec l’option -lm:

$ gcc -std=c99 -Wall -Wextra primes.c -lm  -o primes

Exercice

En ajustant le nombre d’exécutions pour que le résultat obtenu soit significatif, mesurer les performances obtenues avec les programmes C naïf et amélioré, pour n = 10000, 100000, 1000000.

Renseigner le tableau ci dessous :

n

C naïf (ms)

C amélioré (ms)

10000

100000

1000000

Quelle conclusion tirez vous sur le gain de performance ?

Si le temps le permet…

Utilisez la même technique d’accélération avec Python. Remplissez un tableau similaire. Conclusions ?