Probleme – Couvrir une boucle : zéro, un, et au moins deux tours

/* Renvoie la longueur de la plus longue suite de termes EGAUX et
   CONSECUTIFS dans t[0..n-1]. Vaut 0 si n vaut 0.  Precondition : n >= 0. */
int plus_longue(const int t[], int n) {
    if (n == 0) { return 0; }
    int meilleur = 1, courant = 1;
    for (int i = 1; i < n; i = i + 1) {
        if (t[i] == t[i-1]) { courant = courant + 1; }
        if (courant > meilleur) { meilleur = courant; }
    }
    return meilleur;
}

1. Le graphe, et ses chemins.

Il y a un cycle : $C\to D\to \cdots \to C$. Le nombre de chemins est donc infini — un chemin par nombre de tours, et quatre variantes par tour selon les issues de $D$ et de $F$. Après $k$ tours, $4^k$ chemins. La couverture des chemins est inatteignable par principe, comme l'annonçait l'exercice 4.10.

Le compromis usuel couvre zéro tour, un tour, et au moins deux tours, en prenant dans chaque cas les deux issues de $D$.

2. Un jeu de tests couvrant les arcs, et sa mesure.

int rien[1] = {0};    assert(plus_longue(rien, 0) == 0); /* A vrai : sortie immediate */
int un[] = {5};       assert(plus_longue(un, 1) == 1);   /* zero tour  */
int eg[] = {1,1};     assert(plus_longue(eg, 2) == 2);   /* un tour, D vrai */
int df[] = {1,2};     assert(plus_longue(df, 2) == 1);   /* un tour, D faux */

Lines executed:       100.00% of 19
Branches executed:    100.00% of 8
Taken at least once:  100.00% of 8

Tous les arcs sont pris, et les quatre assertions passent.

3. La faute, et l'entrée qui la révèle. Il manque la remise à zéro : le if (t[i] == t[i-1]) n'a pas d'else, et courant n'est jamais ramené à $1$ lorsque la suite s'interrompt. Il faudrait

if (t[i] == t[i-1]) { courant = courant + 1; } else { courant = 1; }

Mesure sur quatre entrées à trois tours ou plus :

[1,1,2,2]   : correct 2, version soumise 3     <-- REVELE
[1,2,1,2]   : correct 1, version soumise 1
[3,3,3]     : correct 3, version soumise 3
[1,2,2,2,3] : correct 3, version soumise 3

Une seule des quatre la révèle, et il a fallu le motif « une suite, une rupture, une autre suite » : $[1,1,2,2]$. Les trois autres, pourtant plus longues, coïncident — parce qu'elles n'ont qu'une seule suite maximale, ou aucune répétition du tout.

Pourquoi deux tours ne suffisaient pas. La faute est une omission de réinitialisation. Une telle faute ne se voit que si l'on repasse dans l'état qu'il fallait réinitialiser, après l'avoir quitté. Il faut donc au minimum : un tour qui incrémente, un tour qui aurait dû remettre à $1$, puis un tour qui incrémente à nouveau — soit trois tours, et un tableau de quatre cases.