.. _05-controle: 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 :func:`max3` suivante qui retourne le plus grand de 3 nombres entiers : .. code-block:: c :linenos: int max3(int a, int b, int c) { if (a >= b && a >= c) return a; else if (b >= c) return b; else return c; } .. admonition:: 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 : .. code-block:: c max = ( a>=b ) ? a : b; .. admonition:: Exercice Ré écrire la fonction :func:`max3` en utilisant les opérateurs ternaires. Pourriez vous réduire le corps de la fonction à une seule ligne ? .. int max3(int a, int b, int c){return (a >= b && a >= c) ? a : (b >= c) ? b : c;} 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 : .. code-block:: c :linenos: for ( int i = 0; i < 10; i++ ){ printf("%d\n", i); } 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 : .. code-block:: c :linenos: int i = 0; while (i < 10) { printf("%d\n", i); i++; } 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 : .. code-block:: c :linenos: i = 0; do { printf("%d\n", i); i++; } 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. .. image:: ../images/while-do-while-fun.jpg :width: 40 % :alt: Le processus de compilation :align: center 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 : .. code-block:: c :linenos: int i = 0; while (i < 10) { if (i == 5) break ; printf("%d\n", i); i++; } Dans le code ci dessous, le chiffre ``5`` n'est pas affiché : .. code-block:: c :linenos: for ( int i = 0; i < 10; i++ ){ if (i == 5) continue ; printf("%d\n", i); } .. admonition:: 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 : .. code-block:: C while(1) { ... } .. _comptage-des-nombres-premiers: 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 :file:`primes.c`. Il sera structuré de la façon suivante : - une directive ``#include`` permettant d'utiliser :func:`printf` pour l'affichage ; - une fonction secondaire :func:`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 :func:`main` qui compte le nombre de nombres premiers jusqu'à ``n``. Concrètement : .. code-block:: C // primes.c #include int isprime(int p){ // à compléter return 0; } int main(){ // à compléter return 0; } .. admonition:: Exercice Ecrire le corps des fonctions :func:`isprime` et :func:`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 :file:`primes.c`:: $ gcc -std=c99 -Wall -Wextra primes.c -o primes $ ./primes 25 .. // primes.c #include #include int isprime(int p){ if (p%2 == 0) return 0; // for (int d=2 ; d < p ; d=d+1) for (int d=3 ; d < (int)sqrt(p)+1 ; d=d+2) //for (int d=3 ; d < (int)sqrt(p)+1 ; d=d+2) { if (p%d == 0) return 0; } return 1; } int main(){ int n=0; for (int i=2; i<1000000 ; i++){ if (isprime(i)){ n++; } } printf("%d\n", n+1); } Mesure du temps d'exécution ........................... Utiliser la commande :command:`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 à :math:`int(\sqrt{p})+1`. Pour cela il faut : - "importer" la définition des fonctions mathématiques .. code-block:: c #include - utiliser la fonction :func:`sqrt` de prototype : .. code-block:: c double sqrt(double arg); - et "caster" le résultat pour le convertir en ``int`` : .. code-block:: c (int)sqrt(p) .. admonition:: 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 .. admonition:: 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 ? .. admonition:: Si le temps le permet... Utilisez la même technique d'accélération avec Python. Remplissez un tableau similaire. Conclusions ?