Chemin de poids maximal dans une pyramide

On considère une suite de nombres formant une pyramide de hauteur et de largeur {n(n=15} sur l’exemple).

On souhaite calculer la somme maximale d’un chemin partant du sommet vers la base (on passe à chaque étape sur l’entier situé en dessous et soit à droite soit à gauche).

Une question un peu plus difficile consiste à renvoyer non seule- ment la valeur de ce poids maximum, mais aussi les étapes du chemin correspondant.

On dira qu’un tableau de tableaux d’entiers une pyramide de hauteur {n} si ses lignes successives sont de longueur {1,2,...,n.}

Figure du chapitre 7, page 4

7.3.1 Une solution partielle

La fonction maxpyr prend en argument une pyramide et renvoie la valeur maximum d’un chemin du sommet vers la base (mais sans renvoyer un chmein réalisant ce maximum). L’idée est que tout chemin passe par l’avant-dernière ligne de la pyramide avant d’aboutir à la dernière ligne. Actuellement, les deux dernières lignes s’écrivent :

63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Le chemin de poids maximal passe nécessairement par l’un des entiers {a_{j}(}en position {j)} de l’avant-dernière ligne, avant de choisir l’un des deux entiers « voisins » {b_{j}} ou {b_{j+1}\quad (}positions {j} ou {j+1)} de la dernière ligne.

Mais bien sûr, le choix se fait sur le plus grand d{eb_{j}} et d{eb_{j+1}\quad (}c’est parce qu’on arrive à la dernière ligne !). Finalement, et parce qu’on est seulement intéressé par le poids total du chemin, on peut remplacer chaque {a_{j}} de l’avant dernière ligne par {a_{j}^{\prime }=a_{j}+\max (b_{j},b_{j+1}\quad ).} Après cette modification de l’avant-dernière ligne du tableau, on peut effacer la dernière ligne et on est ramené à une pyramide de hauteur (et de base{)n-1.}

On poursuit ce processus jusqu’au sommet de la pyramide, dans lequel on finit donc par écrire le poids du chemin maximum (mais sans information sur les étapes de ce chemin).

Sur l’exemple de l’énoncé, le poids maximum est 1074.

NB : la pyramide passée en argument est modifiée !

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :