Exercice 2 - Récursivité · Bac Numérique et Sciences Informatiques Amérique du Nord 2025 (jour 1)

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

Une entreprise souhaite gérer les colis qu'elle expédie à l'aide d'une application informatique. On sait que chaque colis a un identifiant unique, un poids, une adresse de livraison et un état. Pour chacun d'entre eux, trois états sont possibles: « préparé », « transit » ou « livré ».

Pour cela, on a créé une classe Colis avec les attributs suivants:

id: un identifiant unique (de type str);

poids: le poids du colis en kilogrammes (de type float);

adresse: l'adresse de destination (de type str);

etat: l'état du colis (de type str parmi 'préparé', 'transit', 'livré').

Lorsque l'on crée une instance de la classe Colis, l'attribut etat est initialisé à 'préparé' tandis que les valeurs des autres attributs sont passées en paramètres. Voici le début du code Python de la classe Colis:

class Colis:

def __init__(self, id, poids, adresse):

self.id = id

self.poids = poids

self.adresse = adresse

self.etat = 'préparé'

On crée, par exemple, les deux colis suivants:

colisA = Colis('AC12', 5.0, '20 rue de la paix 57000 Metz')

colisB = Colis('AF34', 10.25, '32 rue du centre 57000 Metz')

Le code Python ci-après présente la fonction récursive chargement_glouton dont les paramètres sont:

liste: une liste de colis triées par poids décroissants;

rang: un indice compris entre 0 inclus et len(liste) inclus;

charge: une charge exprimée en kilogrammes;

et qui renvoie la liste des colis à charger en appliquant l'algorithme glouton, en supposant que la charge restante dans le camion est capacite, et en ne considérant que les colis de liste d'indice supérieur ou égal à rang.

def chargement_glouton(liste, rang, capacite):

if rang == len(liste):

return...

elif liste[rang].poids <=...:

return... + chargement_glouton(liste,...,...)

else:

return chargement_glouton(liste,...,...)

8.

Recopier et compléter le code ci-dessus de la fonction chargement_glouton.

9.

Expliquer brièvement pourquoi, lors d'un appel à la fonction chargement_glouton, on peut obtenir l'erreur suivante:

RecursionError: maximum recursion depth exceeded while calling a Python object.

10.

Écrire une fonction chargement_glouton2 itérative (sans récursivité) qui prend en paramètres liste une liste de colis triés par poids décroissants et capacite la capacité du camion exprimée en kilogrammes, et qui renvoie la liste des colis à charger pour maximiser le poids total sans dépasser la capacité.

On pourra créer une liste colis_a_charger, puis parcourir les colis triés en les ajoutant à cette liste tant que le poids total n'excède pas la capacité du camion.