La pyramide de nombres — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 5)

La pyramide de nombres

Chemins de valeur optimale · niveau 2

Énoncé

On descend une pyramide de nombres depuis le sommet ; de la case $c$ de la ligne $l$ , on va sur la case $c$ ou $c + 1$ de la ligne $l + 1$ . On veut un chemin de somme maximum jusqu'à la base.

				3
			7		4
		2		4		6
	8		5		9		3
1		6		2		7		4

Représenter la pyramide par un tableau « en escalier » (int[][] P dont la ligne $l$ a $l + 1$ cases) et écrire la récurrence de $m (l, c)$ , somme maximum d'un chemin du sommet à $(l, c)$ .
Programmer le calcul et l'affichage d'un chemin optimal.
Combien de chemins une pyramide de $n$ lignes a-t-elle ?

Corrigé

La case $(l, c)$ est atteinte depuis $(l - 1, c - 1)$ ou $(l - 1, c)$ , quand ces cases existent ( $0 \leq c - 1$ et $c \leq l - 1$ ).

Base. $m (0, 0) = p (0, 0)$ .

Hérédité. $\forall l, 1 \leq l < n$ , $\forall c, 0 \leq c < l + 1$ : $m (l, c) = max {m (l - 1, c - 1), m (l - 1, c)} + p (l, c)$ , les termes inexistants omis. -


int[][] M = new int[n][];
M[0] = new int[] {P[0][0]};                                   // base
for (int l = 1; l < n; l++) {                                 // par lignes croissantes
    M[l] = new int[l + 1];
    for (int c = 0; c < l + 1; c++) {
        int p = Integer.MIN_VALUE;
        if (c > 0) p = Math.max(p, M[l - 1][c - 1]);          // venir d'en haut à gauche
        if (c < l) p = Math.max(p, M[l - 1][c]);              // d'en haut à droite
        M[l][c] = p + P[l][c];
    }
}


[3]
[10, 7]
[12, 14, 13]
[20, 19, 23, 16]
[21, 26, 25, 30, 20]
Somme maximum 30 : 3 + 7 + 4 + 9 + 7

Chaque pas offre deux choix : $2^{n - 1}$ chemins, contre $n (n + 1) /2$ cases à calculer.