Exercice 2 - Partie C · Bac Numérique et Sciences Informatiques Métropole 2024 (sujet 2)

EXERCICE 2 (6 points)

Cet exercice porte sur la programmation orientée objets, les tris, les algorithmes gloutons, la récursivité et les assertions.

Cet exercice est composé de trois parties dont les deux dernières sont indépendantes entre elles.

Dans cet exercice, l'entête des fonctions est décrit avec le type des objets en paramètre et le type de l'objet renvoyé. Ainsi la fonction puissance qui prend un paramètre flottant x et un entier n puis qui renvoie le flottant x**n, a pour entête puissance(x: float, n: int) -> float.

Une entreprise transporte des marchandises. Elle souhaite maximiser son profit en optimisant le remplissage de ses moyens de transport. On considère qu'un moyen de transport est limité par son volume (exprimé en litres). Chaque marchandise est caractérisée par son prix (en euros) et son volume indivisible (en litres).

Supposons qu'on ait trois marchandises caractérisées par les couples (prix, volume) suivants: $m_1 = (100, 10)$, $m_2 = (100, 10)$ et $m_3 = (250, 20)$. Si le moyen de transport peut encore charger 25 litres, il vaut mieux charger la marchandise numéro 3 qui rapporte 250 € à l'entreprise plutôt que charger les marchandises numéros 2 et 3 qui rapportent 200 € au total pour le même espace utilisé.

Partie C – Rangement optimisé par récursivité

L'algorithme précédent ne renvoie pas toujours une solution optimale. On peut donc suivre un algorithme récursif. On note $n$ le nombre de marchandises et on souhaite implémenter la fonction récursive chargeOptimale d'entête:

chargeOptimale(tab: list, v_restant: int, i: int) -> list

Un appel à cette fonction doit permettre de calculer la charge optimale pour un transport de volume v_restant utilisant les marchandises à partir de l'indice i:

si i >= n, toutes les marchandises ont été essayées et il n'en reste plus d'autres disponibles. L'appel récursif renvoie la liste vide;

si i < n et la marchandise d'indice i est de volume strictement supérieur au volume restant, l'appel récursif renvoie le résultat de l'appel effectué avec le même volume restant mais avec la marchandise suivante, c'est-à-dire chargeOptimale(tab, v_restant, i+1);

si i < n et la marchandise d'indice i est de volume inférieur ou égal au volume restant, il existe deux options possibles: Option 1: soit on utilise la marchandise i, auquel cas le chargement contiendra cette marchandise et celles du résultat de l'appel récursif à partir de la prochaine marchandise et d'un volume restant strictement inférieur,

Option 2: soit on n'utilise pas la marchandise i, auquel cas le chargement sera le résultat de l'appel récursif avec le même volume restant mais à partir de la marchandise suivante.

On garde l'option de chargement qui maximise le prix transporté.

10.

Compléter le code de la fonction chargeOptimale dont le principe a été décrit ci-avant:

def chargeOptimale(tab: list, v_restant: int, i: int) -> list: if i >=: return else: if tab[i].volume > v_restant: return chargeOptimale(tab, v_restant, i+1) else: option1 = chargeOptimale(tab,,) option2 = [tab[i]] + chargeOptimale(tab,,) if prixListe(option1) > prixListe(option2): return else: return