C2 Discipline de programmation ¶

"Program testing can be used to show the presence of bugs, but never to show their absence! "
E. Dijkstra
(in Notes on structured programming, 1970)

Cours¶

Support de cours chapitre 2

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.

Travaux dirigés¶

Fiche de TD2

Travaux pratiques¶

Exercice 1 : Recherche d'un élément dans un tableau¶

Voici le code d'une fonction indice en C :

    int indice(int tab[], int taille, int elt)
    {
        /* Renvoie l'indice de la première occurrence de elt dans tab
         ou -1 si elt n'est pas dans tab  */
        for (int i = 0; i < taille; i++)
        {
            if (tab[i] == elt)
            {
                return i;
            }
            else
            {
                return -1;
            }
        }

Les tests proposés pour cette fonction sont de vérifier qu'elle renvoie -1 lorsqu'on cherche 12 dans le tableau {2, 5, 6, 1} et 0 lorsqu'on cherche 2 dans ce tableau. Cette fonction valide-t-elle ces tests ?
Par des tests appropriés, montrer que cette fonction n'est pas conforme à sa spécification.
Corriger cette fonction.

Exercice 2 : Validation de date¶

Écrire une fonction bissextile qui prend en argument un entier strictement positif annee et renvoie true si annee est une année bissextile.
Écrire une fonction verifie_date prenant en argument trois entiers (jour, mois et annee) et renvoyant true si jour/mois/annee est une date valide.
Proposer un jeu de tests pour cette fonction.

Exercice 3 : Somme des éléments d'un tableau¶

Afin de calculer la somme des éléments d'un tableau, un élève propose le code suivant qui selon lui permet de gagner du temps car on somme les éléments deux par deux :

int somme_deux(int tab[], int size)
{
    /* renvoie la somme des éléments de tab*/
    int s = 0;
    for (int i = 0; i < size - 1; i += 2)
    {
        s = s + tab[i] + tab[i+1];
    }
    return s;
}

Montrer par un test approprié que cette fonction n'est pas conforme à sa spécification.
Écrire une version correcte de cette fonction.

Exercice 4 : Tri à bulles¶

Le tri à bulles est un algorithme de tri qui consiste à parcourir de façon répétitive un tableau : si deux éléments consécutifs ne sont pas dans le bon ordre, alors on inverse leur position. À la fin du premier parcours, le plus grand élément se trouve forcément en dernière position. Le parcours suivant s'arrête donc à l'avant-dernier élément, et ainsi de suite. Par exemple, sur le tableau {12, 9, 17, 11, 3}, les étapes du tri seront :

après le premier parcours : {9, 12, 11, 3, 17}
après le deuxième parcours : {9, 11, 3, 12, 17}
après le troisième parcours : {9, 3, 11, 12, 17}
après le quatrième parcours : {3, 9, 11, 12, 17}

Le but de l'exercice est d'implémenter cet algorithme.

Écrire une fonction de signature void echange(int tab[], int i, int j, int taille) qui échange les éléments d'indice i et j dans tab. On vérifiera les préconditions suivantes : 0 <= i < taille et 0 <= j < taille.
Écrire une fonction de signature void parcours(int tab[], int limite, int taille) qui parcourt tab jusqu'à l'indice limite en échangeant l'élément avec son voisin de droite s'il lui est supérieur. Donner les préconditions.
Écrire une fonction void tri_bulles(int tab[], int size) qui trie en place le tableau tab. Proposer des tests pour valider le comportement de cette fonction.

Exercice 5 : Nombres narcissiques¶

Un nombre \(a\) ayant \(p\) chiffres en base 10, noté \(a = \overline{a_{p-1}\dots a_1a_0}^{10}\), est dit narcissique lorsqu'il est égal à la somme des puissances \(p\)-ièmes de ses chiffres, c'est-à-dire lorsque \(a = a_{p-1}^p + \dots + a_1^p + a_0^p\). Exemples :

\(153\) est narcissique (\(p=3\)) car \(1^3 + 5^3 + 3^3 = 153\)
\(255\) n'est pas narcissique (\(p=3\)) car \(2^3 + 5^3 + 5^3 = 258\)
\(1634\) est narcissique (\(p=4\)) car \(1^4 + 6^4 + 3^4 + 4^4 = 1634\)
\(3375\) n'est pas narcissique (\(p=4\)) car \(3^4 + 3^4 + 7^4 + 5^4 = 3188\)

Le but de l'exercice est de trouver le plus grand nombre narcissique inférieur à un million.

Écrire une fonction prenant en entrée un entier \(n\) et un entier \(p\) et renvoyant \(n^p\). On se limite au cas \(p>0\) et \(n\geqslant 0\) et on vérifiera ces préconditions à l'aide d'instructions assert. Écrire dans le code en commentaire une spécification précise de cette fonction et proposer un jeu de tests sous la forme d'instructions assert.
Écrire une fonction nb_chiffres prenant en entrée un entier \(n \geqslant 0\) et renvoyant son nombre de chiffres. Par exemple nb_chiffres(1634) doit renvoyer 4.

Aide

Voir le cours
Écrire une fonction est_narcissique qui prend en argument un entier n et qui renvoie true si et seulement si n est un nombre narcissique.
Aide

On rappelle que si \(a = \overline{a_{p-1}\dots a_1a_0}^{10}\), alors :
- \(a_0\) est le reste dans la division euclidienne de \(a\) par 10,
- le quotient dans la division euclidienne de \(a\) par 10 est \(\overline{a_{p-1}\dots a_1}^{10}\).
Tester cette fonction en écrivant les instructions assert permettant de vérifier les exemples de nombres narcissiques ou non donnés en début d'exercice.
Écrire une fonction narcissique_seuil qui prend en entrée un entier n et renvoie le plus grand nombre narcissique inférieur à cet entier n. Par exemple narcissique_seuil(200) doit renvoyer 153. Quel est le plus grand nombre narcissique inférieur à un million ?
Tester votre réponse
Écrire une fonction compte_narcissique qui prend en entrée un entier n et renvoie le nombre de nombres narcissiques inférieurs ou égaux à n. Combien de nombres narcissiques sont inférieurs à un million ?
Tester votre réponse

Exercice 6 : Recherche dichotomique et batterie de tests¶

Écrire une fonction int recherche_dichotomique(int tab[], int taille, int cible) qui prend en argument un tableau tab d'entiers trié par ordre croissant, sa taille taille et un entier cible, et qui renvoie l'indice de cible dans tab si elle est présente, et -1 sinon. On vérifiera la précondition taille >= 0 à l'aide d'une assertion (assert).
Pour valider rigoureusement cette fonction, on utilise la méthode du partitionnement du domaine d'entrée et le test des valeurs limites. Écrire une fonction void test_recherche_dichotomique(void) contenant une suite d'instructions assert testant les cas suivants :
- Tableau de taille nulle (taille = 0) et tableau à un seul élément (élément présent et absent) ;
- cible présente aux extrémités (tab[0], tab[taille - 1]) et au milieu du tableau ;
- cible absente : strictement inférieure au minimum, strictement supérieure au maximum, et intercalée entre deux éléments du tableau.
Appeler la fonction test_recherche_dichotomique dans le main et vérifier que tous les tests sont validés.

Exercice 7 : Élimination des doublons dans un tableau trié¶

On considère un tableau tab d'entiers trié par ordre croissant contenant d'éventuels doublons. On souhaite éliminer les doublons en place en déplaçant les valeurs uniques vers le début du tableau.

Écrire une fonction int supprimer_doublons(int tab[], int taille) qui modifie tab en place de sorte que ses \(k\) premières cases contiennent les éléments uniques de tab triés par ordre strictement croissant, et qui renvoie ce nombre \(k\) (\(0 \le k \le \text{taille}\)).
Par exemple, si tab contient {1, 1, 2, 3, 3, 3, 5} (taille = 7), après exécution la fonction renvoie 4 et les 4 premiers éléments de tab sont {1, 2, 3, 5}.
Écrire une fonction oracle bool est_strictement_croissant(int tab[], int taille) qui renvoie true si le sous-tableau des taille premiers éléments est trié par ordre strictement croissant et false sinon.
À l'aide de cet oracle et d'instructions assert, écrire une fonction void test_supprimer_doublons(void) testant systématiquement les cas suivants :
- Tableau vide (taille = 0) et tableau ne contenant aucun doublon ;
- Tableau dont tous les éléments sont identiques (ex : {4, 4, 4, 4}) ;
- Tableau avec des doublons situés uniquement au début, au milieu ou à la fin.

Exercice 8 : Chasse au bug et couverture de code¶

On dit qu'un tableau d'entiers de taille \(n \ge 3\) forme une vallée s'il est d'abord strictement décroissant jusqu'à un minimum local, puis strictement croissant jusqu'à la fin. Par exemple {9, 6, 2, 5, 8} est une vallée, mais {9, 6, 2} (pas de remontée) et {9, 2, 5, 2, 8} (deux creux) n'en sont pas.

Pour tester cette propriété, un élève propose le code suivant :

href="#__codelineno-2-1">bool est_vallee(int tab[], int taille) pan> /* Précondition : taille >= 3 */ int i = 0; // Descente while (i < taille && tab[i] > tab[i+1]) { i++; } // Si on n'a pas du tout descendu ou si on est arrivé au bout if (i == 0 || i == taille - 1) { return false; } // Remontée while (i < taille && tab[i] < tab[i+1]) { i++; } return i == taille - 1; }

Tracer le graphe de flot de contrôle de cette fonction.
Proposer un jeu de tests (tableaux d'entrée et sorties attendues) permettant d'exécuter 100 % des instructions du code sans déclencher de comportement indéfini.
Identifier le bug critique présent dans les conditions de boucle tab[i] > tab[i+1] et tab[i] < tab[i+1] (accès hors bornes lorsque i == taille - 1).
Proposer un test qui met en évidence ce problème, puis corriger la fonction.

Exercice 9 : Exponentiation rapide et mesure d'opérations¶

L'algorithme d'exponentiation rapide permet de calculer \(x^n\) (pour \(x \in \mathbb{R}\) et \(n \in \mathbb{N}\)) en effectuant un nombre d'opérations proportionnel à \(\log_2(n)\), contre \(n\) multiplications pour l'algorithme naïf.

Écrire une fonction double puissance_naive(double x, int n, int *nb_mult) qui calcule \(x^n\) par une boucle simple et incrémente le compteur *nb_mult à chaque multiplication effectuée.
Écrire une fonction double puissance_rapide(double x, int n, int *nb_mult) calculant \(x^n\) par élévation au carré itérative en comptant également le nombre de multiplications effectuées :
- On initialise le résultat r = 1.0 et p = x ;
- Tant que \(n > 0\) : si \(n\) est impair on multiplie r par p, puis on remplace p par p * p et \(n\) par \(n / 2\).
Écrire une fonction de test vérifiant à l'aide d'instructions assert que pour \(n = 1000\) et \(x = 1.001\) :
- Les deux fonctions renvoient le même résultat ;
- La méthode naïve effectue exactement 1000 multiplications ;
- La méthode rapide effectue strictement moins de 20 multiplications (vérifier que *nb_mult < 20).

Humour d'informaticien¶

punition