Exercice 3 - Partie C · 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 C

Pour éviter les calculs redondants, on décide d'utiliser la programmation dynamique et de mémoriser les résultats de ces calculs au fur et à mesure qu'on les obtient dans un tableau memo (type list en Python).

On déclare et initialise la variable globale memo comme suit:

memo = [0, 1, 5, 8, -1, -1, -1, -1, -1, -1, -1]

Il faut maintenant coder la fonction valmax_dynamique de paramètre n, la longueur de la planche (en mètre) dont on cherche la valeur maximale, de façon à ce que:

si memo[n] ne vaut pas -1 alors la valeur maximale a déjà été mémorisée et memo[n] vaut cette valeur maximale donc on la renvoie;

sinon:

on calcule la valeur maximale en utilisant les appels récursifs;

on affecte à memo[n] la valeur maximale obtenue.

13.

Recopier et compléter les lignes 2 à 8 du code de la fonction ci-après:

1 def valmax_dynamique(n):

2 if...:

3...

4 else:

5 maximum = prix[n]

6 for longueur in range(1,...):

7 maximum = max(maximum,... +...)

8 memo[n]...

9 return maximum

14.

Donner en justifiant le nombre d'appels récursifs effectués par l'appel de valmax_dynamique(6), après l'exécution de valmax_dynamique(5).

15.

Expliquer ce qui se serait passé si on avait initialisé la variable memo avec uniquement des valeurs égales à -1.

On rappelle que, pour gérer son stock, la scierie utilise un dictionnaire effectif qui associe à chaque longueur de planche en mètre présente dans le stock son effectif dans le stock. De plus on suppose que la variable memo vient d'être initialisée comme suit:

memo = [0, 1, 5, 8, -1, -1, -1, -1, -1, -1, -1]

16.

Écrire une fonction valeur_max_stock qui prend en paramètre un dictionnaire effectif et qui renvoie la valeur maximale en euro que peut rapporter le stock à l'entreprise en optimisant le découpage de chaque planche afin qu'elle rapporte le maximum.