Escalier de coût minimum — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 1)

Escalier de coût minimum

Glouton ou dynamique ? · niveau 2

Énoncé

Un escalier a $n$ marches numérotées $0, \dots, n - 1$ ; poser le pied sur la marche $i$ coûte $c_{i}$ . Depuis la marche $i$ on peut monter sur la marche $i + 1$ ou $i + 2$ . On part du sol (une marche fictive $- 1$ , de coût nul) et l'on doit atteindre la marche $n - 1$ .

On note $m (j)$ le coût minimum d'une montée du sol jusqu'à la marche $j$ incluse. Donner l'équation de récurrence des valeurs $m (j)$ .
Écrire le programme qui calcule le tableau $M$ et affiche une montée de coût minimum.
Application : $c = [10, 15, 20, 5, 25, 10, 5]$ .

Corrigé

On arrive sur la marche $j \geq 2$ depuis $j - 1$ ou depuis $j - 2$ , et la montée jusqu'à cette marche précédente est elle-même de coût minimum (principe d'optimalité). Base : $m (0) = c_{0}$ et $m (1) = c_{1}$ (depuis le sol, on atteint directement les marches $0$ et $1$ ). Hérédité : $\forall j, 2 \leq j < n$ ,

$m (j) = min {m (j - 1), m (j - 2)} + c_{j} .$


static int[] calculerM(int[] c) { int n = c.length;
    int[] M = new int[n];
    M[0] = c[0];                               // base
    if (n > 1) M[1] = c[1];
    for (int j = 2; j < n; j++)                // hérédité, j croissants
        M[j] = Math.min(M[j-1], M[j-2]) + c[j];
    return M;
}
static void amc(int[] M, int j) {
    // affiche une montée de coût minimum du sol à la marche j
    if (j <= 1) { System.out.print(" -> " + j); return; }   // depuis le sol
    amc(M, M[j-1] <= M[j-2] ? j-1 : j-2);  // montée jusqu'à la marche précédente
    System.out.print(" -> " + j);          // puis la marche j
}

Calcul en $Θ (n)$ , affichage en $Θ (n)$ . -


c = [10, 15, 20, 5, 25, 10, 5]
M = [10, 15, 30, 20, 45, 30, 35]
cout minimum 35 : sol -> 1 -> 3 -> 5 -> 6

La montée $15 + 5 + 10 + 5 = 35$ évite les deux marches chères ( $20$ et $25$ ).


nom : M
valeurs : 10 15 30 20 45 30 35
colorier : 6
vert : 0..5
fleches : 4->6 5->6
legende : m(6) = min(m(5), m(4)) + 5 = min(30, 45) + 5 = 35


nom : c
valeurs : 10 15 20 5 25 10 5
vert : 1 3 5 6
fleches : 1->3 3->5 5->6
legende : montée sol → 1 → 3 → 5 → 6 : 15 + 5 + 10 + 5 = 35