Zébulon, encore — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 5)

Zébulon, encore

Chemins de valeur optimale · niveau 2

Énoncé

Reprendre le problème de Zébulon (chapitre 1) comme un problème de lignes de bus : les sauts de $2$ et de $3$ cases sont deux « lignes », et arriver sur la case $j$ rapporte $r_{j}$ .

Écrire la récurrence de $m (j)$ avec une seule boucle sur la longueur du saut, et mémoriser $a (j) = ar g m (j)$ , case d'où part le dernier saut.
Programmer calculerMA et la fonction d'affichage, et les exécuter sur le ruban

$R = [2, - 1, 3, 4, - 5, 1, 6, - 2, 3] .$

Corrigé

Un chemin optimal vers $j$ arrive depuis $j - 2$ ou $j - 3$ (s'ils existent et sont accessibles).

Base. $m (0) = r_{0}$ .

Hérédité. $\forall j, 1 \leq j < n$ : $m (j) = max_{t \in {2, 3}, t \leq j} {m (j - t)} + r_{j}$ , avec $max \emptyset = - \infty$ ; $a (j)$ est la case $j - t$ qui réalise le maximum. La case $1$ obtient ainsi $m (1) = - \infty$ sans cas particulier. -


static int[][] calculerMA(int[] R) {
    int n = R.length;
    int[] M = new int[n], A = new int[n];
    M[0] = R[0]; A[0] = -1;                          // base
    for (int j = 1; j < n; j++) {                     // par j croissants
        M[j] = MOINS_INFINI; A[j] = -1;               // aucun chemin connu
        for (int saut = 2; saut <= 3; saut++) {
            int i = j - saut;                         // case de départ du saut
            if (i >= 0 && M[i] > MOINS_INFINI / 2 && M[i] + R[j] > M[j]) {
                M[j] = M[i] + R[j]; A[j] = i;
            }
        }
    }
    return new int[][] {M, A};
}

static void acm(int[] A, int j) {
    if (j == 0) { System.out.print("0"); return; }
    acm(A, A[j]);                                    // chemin jusqu'à a(j) affiché
    System.out.print(" -> " + j);                    // puis la case j
}


M = [2, -oo, 5, 6, 0, 7, 12, 5, 15]
A = [-1, -1, 0, 0, 2, 3, 3, 5, 6]
Valeur maximum 15 : 0 -> 3 -> 6 -> 8

Le chemin optimal vaut $2 + 4 + 6 + 3 = 15$ .


nom : A
valeurs : -1 -1 0 0 2 3 3 5 6
colorier : 8
vert : 0 3 6
fleches : 8->6 6->3 3->0
legende : a(8) = 6, a(6) = 3, a(3) = 0 : chemin 0 → 3 → 6 → 8