Escalier : compter — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 12)

Escalier : compter

Recherche séquentielle, dichotomique, arrière · niveau 2

Énoncé

Le tableau $G$ à $L$ lignes et $C$ colonnes est trié par lignes (croissant de gauche à droite) et par colonnes (croissant de haut en bas), comme dans la recherche en escalier du cours. Écrire une fonction en $Θ (L + C)$ qui compte les cases de $G$ dont la valeur est inférieure ou égale à $x$ . On partira du coin en bas à gauche et on donnera l'invariant.

Corrigé

On part de la case $(L - 1, 0)$ , en bas à gauche.

Si $G [l] [c] \leq x$ : la colonne $c$ croît vers le bas, donc les $l + 1$ cases $G [0] [c], \dots, G [l] [c]$ sont toutes $\leq x$ . On les compte et on passe à la colonne suivante.
Sinon $G [l] [c] > x$ : la ligne $l$ croît vers la droite, donc $G [l] [c], \dots, G [l] [C - 1]$ sont toutes $> x$ . On élimine la ligne $l$ .

Invariant : « $nb$ est le nombre de cases $\leq x$ des colonnes $[0 : c]$ , et dans les colonnes $[c : C]$ , toutes les cases des lignes $[l + 1 : L]$ sont $> x$ ».


static int compterInfEgal(int[][] G, int x) { int L = G.length, C = G[0].length;
    int l = L - 1, c = 0, nb = 0;     // coin en bas à gauche
    while (l >= 0 && c < C) {
        if (G[l][c] <= x) { nb += l + 1; c++; } // la colonne c jusqu'à l est <= x
        else l--;                               // la ligne l à partir de c est > x
    }
    return nb;
}

À l'arrêt, soit $c = C$ et toutes les colonnes sont comptées, soit $l = - 1$ et les colonnes $[c : C]$ ne contiennent aucune case $\leq x$ . Chaque tour élimine une colonne ou une ligne : au plus $L + C$ tours, donc $Θ (L + C)$ . Le programme Sequentielles.java compare le résultat à un comptage exhaustif sur une grille $4 \times 4$ pour $x \in {0, 5, 9, 13, 20}$ : les résultats sont identiques.