Rendu de monnaie glouton - Sujet 32 - EP NSI 2025

Exercice 1

Écrire une fonction occurrences(caractere, chaine) qui prend en paramètres caractere, une chaîne de caractère de longueur 1, et chaine, une chaîne de caractères.

Cette fonction renvoie le nombre d’occurrences de caractere dans chaine, c’est-à-dire le nombre de fois où caractere apparaît dans chaine.

Exemples :

>>> occurrences('e', "sciences")
2
>>> occurrences('i',"mississippi")
4
>>> occurrences('a',"mississippi")
0

Exercice 2

On s’intéresse à un algorithme récursif qui permet de rendre la monnaie à partir d’une liste donnée de valeurs de pièces et de billets.

Le système monétaire est donné sous forme d’une liste valeurs = [100, 50, 20, 10, 5, 2, 1]. On suppose que les pièces et les billets sont disponibles sans limitation.

On cherche à donner la liste des valeurs à rendre pour une somme donnée en argument. L’algorithme utilisé est de type glouton.

Compléter le code Python ci-dessous de la fonction rendu_glouton qui implémente cet algorithme et renvoie la liste des pièces à rendre.

valeurs = [100, 50, 20, 10, 5, 2, 1]

def rendu_glouton(a_rendre, rang):
    if a_rendre == 0:
        return ...
    v = valeurs[rang]
    if v <= ...:
        return ... + rendu_glouton(a_rendre - v, rang)
    else:
        return rendu_glouton(a_rendre, ...)

On devra obtenir :

>>> rendu_glouton(67, 0)
[50, 10, 5, 2]
>>> rendu_glouton(291, 0)
[100, 100, 50, 20, 20, 1]
>>> rendu_glouton(291,1) # si on ne dispose pas de billets de 100
[50, 50, 50, 50, 50, 20, 20, 1]

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

caractere est une chaîne de caractères de longueur exactement 1
0 <= len(chaine) <= 10^4
chaine peut être vide ; dans ce cas la fonction renvoie 0
la fonction renvoie un entier

Exercice 2

Contraintes :

valeurs est la liste [100, 50, 20, 10, 5, 2, 1], triée dans l’ordre décroissant
a_rendre est un entier avec 0 <= a_rendre <= 10^3
rang est un entier avec 0 <= rang <= 6
le nombre total de pièces rendues n’excède pas 300
rendu_glouton(0, rang) renvoie la liste vide pour tout rang valide
la fonction renvoie une liste d’entiers pris dans valeurs

Énoncé du problème

Exercice 1

Exercice 2