Exercice 3 - Partie B · Bac Numérique et Sciences Informatiques Antilles-Guyane 2026 (jour 2)

Cet exercice traite de tableaux, de dictionnaires, de récursivité et de programmation dynamique.

Une scierie possède un stock de planches. Chacune des planches du stock a une longueur entière (en mètre) comprise entre 1 m et 10 m et un prix entier (en euro) qui dépend de cette longueur. Le propriétaire de la scierie souhaite estimer la valeur marchande de son stock.

On utilise dans tout le problème la variable globale prix du type list telle que pour tout entier n compris entre 1 et 10, prix[n] est le prix de vente en euro d'une planche de longueur n (en mètre).

On suppose ici que la liste prix est:

prix = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] On remarque que l'élément d'indice 0 de prix est fixé à 0 mais ne sera jamais utilisé car une planche ne peut mesurer 0 m.

Partie B

On réalise qu'on peut parfois augmenter la valeur d'une planche en la découpant en planches plus petites (toujours de longueurs entières) et en vendant séparément les morceaux obtenus.

On cherche donc à déterminer la valeur maximale que peut rapporter une planche à l'entreprise, éventuellement en la découpant.

On remarque que:

on ne peut pas découper une planche de $1\text{ m}$: sa valeur maximale est donc $1\text{ €}$;

une planche $2\text{ m}$ peut être vendue entière pour $5\text{ €}$ ou en deux planches de $1\text{ m}$ pour $1 + 1 = 2\text{ €}$: il vaut donc mieux ne pas la découper;

une planche de $3\text{ m}$ peut être vendue entière pour $8\text{ €}$ ou en une planche de $2\text{ m}$ et une planche de $1\text{ m}$ pour $1 + 5 = 6\text{ €}$ ou en trois planches de $1\text{ m}$ pour $1 + 1 + 1 = 3\text{ €}$: il vaut donc mieux ne pas la découper.

7.

Déterminer, en justifiant, la valeur maximale que peut rapporter une planche de $4\text{ m}$.

On note valmax(n) la valeur maximale d'une planche de longueur $n$ mètres pour $n$ compris entre $1\text{ m}$ et $10\text{ m}$ en optimisant sa découpe et on propose la formule récursive ci-dessous.

Si $n \le 3$, $\text{valmax}(n) = \text{prix}[n]$.

Sinon, $\text{valmax}(n) = \max(\text{prix}[n], \text{prix}[n-1] + \text{valmax}(1), \text{prix}[n-2] + \text{valmax}(2), \dots, \text{prix}[1] + \text{valmax}(n-1))$.

8.

Expliquer le cas d'arrêt de cette formule récursive.

9.

Recopier et compléter les quatre lignes ci-dessous.

valmax(1) = prix[

] =

valmax(2) = prix[

] =

valmax(3) = prix[

] =

Ligne valmax(4) complétée:

10.

Expliquer pourquoi, si $n \ge 4$, on a bien:

$$\text{valmax}(n) = \max(\text{prix}[n], \text{prix}[n-1] + \text{valmax}(1), \text{prix}[n-2] + \text{valmax}(2), \dots, \text{prix}[1] + \text{valmax}(n-1))$$

On souhaite disposer de la fonction valmax qui prend en paramètre un entier $n$ et qui renvoie la valeur maximale obtenue pour une planche de longueur $n$ selon les prix de la variable globale prix.

11.

Recopier et compléter les lignes 2 à 7 du code de la fonction valmax ci-après.

1 def valmax(n):

8

return maximum

12.

Expliquer pourquoi l'appel de valmax(7) effectuera deux appels de valmax(5).