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

Solution - Sujet 32

Exercice 1 - compter les occurrences d’un caractère

L’idée. On veut savoir combien de fois un caractère apparaît dans une chaîne. Il suffit de regarder les caractères de la chaîne un par un, du premier au dernier, et de compter ceux qui sont égaux à celui que l’on cherche. On part donc d’un compteur à 0, on parcourt la chaîne, et à chaque fois que le caractère courant est le bon on ajoute 1 au compteur. À la fin, le compteur contient la réponse.

Un petit exemple. Pour occurrences('e', "sciences"), on parcourt s, c, i, e, n, c, e, s. Deux caractères seulement valent 'e', donc le compteur finit à 2.

def occurrences(caractere, chaine):
    compteur = 0
    for lettre in chaine:
        if lettre == caractere:
            compteur = compteur + 1
    return compteur

compteur retient le nombre de caractères déjà trouvés depuis le début du parcours. La boucle for lettre in chaine prend chaque caractère de la chaîne à tour de rôle : on n’a même pas besoin d’un indice ici. Si la chaîne est vide, la boucle ne s’exécute jamais et la fonction renvoie 0, ce qui est bien le résultat attendu.

Exercice 2 - le rendu de monnaie glouton

L’idée. Le principe glouton, c’est de toujours prendre la plus grosse valeur possible sans dépasser la somme restante. La liste valeurs est rangée de la plus grande à la plus petite, et rang dit quelle valeur on est en train d’essayer. Il n’y a que deux cas. Soit la valeur v tient dans la somme restante, et on la rend puis on recommence avec ce qui reste, en gardant le même rang car on peut reprendre plusieurs fois la même pièce. Soit elle est trop grande, et on passe simplement à la valeur suivante en augmentant rang. Quand il ne reste plus rien à rendre, on renvoie la liste vide : c’est le cas d’arrêt de la récursion.

Un petit exemple. Pour rendu_glouton(67, 0) : 100 est trop grand, on passe à 50 ; 50 tient, on le rend et il reste 17 ; 50 puis 20 sont trop grands, 10 tient et il reste 7 ; 5 tient et il reste 2 ; 2 tient et il reste 0. On obtient [50, 10, 5, 2].

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

def rendu_glouton(a_rendre, rang):
    if a_rendre == 0:
        return []
    v = valeurs[rang]
    if v <= a_rendre:
        # on garde le même rang : la même pièce peut servir plusieurs fois
        return [v] + rendu_glouton(a_rendre - v, rang)
    else:
        return rendu_glouton(a_rendre, rang + 1)

Les quatre trous du sujet se remplissent donc par [], a_rendre, [v] et rang + 1. Le premier return [] est indispensable : sans lui la fonction s’appellerait indéfiniment. Le test v <= a_rendre utilise bien <= et non <, sinon on ne pourrait jamais rendre exactement la somme avec une pièce de cette valeur, par exemple rendre 1 avec la pièce de 1. Enfin [v] + ... construit une nouvelle liste dont le premier élément est la pièce rendue et la suite est le rendu du reste : les pièces sortent donc dans l’ordre décroissant, comme dans les exemples de l’énoncé.