Nombre d'occurrences

• Arrêt : $k=n$. Alors $c$ est le nombre d'occurrences de $v$ dans $T$.
• Initialisation : $I(0,0)$ : le $0$-préfixe est vide, il contient $0$ occurrence.
• Progression : $I(c,k)\wedge k\ne n\wedge T[k]=v\Rightarrow I(c+1,k+1)$ et $I(c,k)\wedge k\ne n\wedge T[k]\ne v\Rightarrow I(c,k+1)$.
• Variant : $n-k$, entier positif qui décroît de $1$ à chaque tour.

static int occurrences(int v, int[] T) { int n = T.length;
    int c = 0, k = 0;                 // I(0,0) : c = nombre de v dans T[0:0]
    while (k != n) {                  // I(c,k) et k ≠ n
        if (T[k] == v) c = c + 1;     // c = nombre de v dans T[0:k+1]
        k = k + 1;                    // I(c,k)
    }                                 // I(c,n) : c = nombre de v dans T
    return c;
}

$n$ tours de temps constant : $\Theta (n)$. Par exemple occurrences(2, new int[] {2, 7, 2, 2, 5, 2}) retourne $4$.

nom : T
valeurs : 2 7 2 2 5 2
colorier : 0 2 3
pointeurs : k=4
zone : 0..3 c = 3
zone : 4..5 non examiné
legende : v = 2 : I(3, 4), c compte les occurrences de v dans T[0:4]