Exercice 1

EXERCICE 1 (10 points)

Écrire une fonction compte_occurrences prenant en paramètres une valeur x et un tableau tab (de type list) et renvoyant le nombre d’occurrences de x dans tab.

L’objectif de cet exercice étant de parcourir un tableau, il est interdit d’utiliser la méthode count des listes Python.

Exemples :

>>> compte_occurrences(5, [])
0
>>> compte_occurrences(5, [-2, 3, 1, 5, 3, 7, 4])
1
>>> compte_occurrences('a', ['a','b','c','a','d','e','a'])
3

Exercice 2

EXERCICE 2 (10 points)

On considère dans cet exercice un algorithme glouton pour le rendu de monnaie. Pour rendre une somme en monnaie, on utilise à chaque fois la plus grosse pièce possible et ainsi de suite jusqu’à ce que la somme restante à rendre soit nulle.

Les pièces de monnaie utilisées sont :

pieces = [1, 2, 5, 10, 20, 50, 100, 200]

On souhaite écrire une fonction rendu_monnaie qui prend en paramètres

• un entier somme_due représentant la somme à payer ;
• un entier somme_versee représentant la somme versée qui est supérieure ou égale à somme_due ;
• et qui renvoie un tableau de type list contenant les pièces qui composent le rendu de la monnaie restante, c’est-à-dire de somme_versee - somme_due.

Ainsi, l’instruction rendu_monnaie(452, 500) renvoie le tableau [20, 20, 5, 2, 1].

En effet, la somme à rendre est de 48 euros soit 20 + 20 + 5 + 2 + 1.

Le code de la fonction rendu_monnaie est donné ci-dessous :

def rendu_monnaie(somme_due, somme_versee):
    '''Renvoie la liste des pièces à rendre pour rendre la monnaie
    lorsqu'on doit rendre somme_versee - somme_due'''
    rendu = ...
    a_rendre = ...
    i = len(pieces) - 1
    while a_rendre > ...:
        while pieces[i] > a_rendre:
            i = i - 1
        rendu.append(...)
        a_rendre = ...
    return rendu

Compléter ce code et le tester :

>>> rendu_monnaie(700, 700)
[]
>>> rendu_monnaie(102, 500)
[200, 100, 50, 20, 20, 5, 2, 1]

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

Exercice 1

Contraintes :

• tab est de type list et 0 <= len(tab) <= 10^4 ; tab peut être vide
• tous les éléments de tab sont d’un même type comparable par == : soit des entiers, soit des chaînes de caractères
• x est du même type que les éléments de tab
• si les éléments sont des entiers : -10^9 <= x, tab[i] <= 10^9
• si les éléments sont des chaînes : chaque chaîne est de longueur au plus 20
• tab n’est pas nécessairement trié et peut contenir des doublons
• la fonction renvoie un entier compris entre 0 et len(tab)

Exercice 2

Contraintes :

• somme_due et somme_versee sont des entiers avec 0 <= somme_due <= somme_versee <= 10^4
• somme_versee >= somme_due est garanti ; le cas somme_versee == somme_due est possible et le rendu est alors le tableau vide []
• la variable globale pieces = [1, 2, 5, 10, 20, 50, 100, 200] est disponible, triée dans l’ordre croissant, et chaque pièce est disponible en quantité illimitée
• la fonction renvoie une list d’entiers, chacun appartenant à pieces, dont la somme vaut exactement somme_versee - somme_due
• les pièces sont renvoyées dans l’ordre décroissant, tel que produit par l’algorithme glouton décrit ci-dessus

Solution

Exercice 1 - compte_occurrences

L’idée. On veut savoir combien de fois la valeur x apparaît dans le tableau tab. La méthode count étant interdite, on fait le travail à la main : on parcourt le tableau du début à la fin, et on garde un compteur qui vaut 0 au départ. Chaque fois que l’élément regardé est égal à x, on ajoute 1 au compteur. Quand le parcours est fini, le compteur contient la réponse.

Un petit exemple. Pour x = 'a' et tab = ['a','b','c','a','d','e','a'], le compteur passe à 1 en position 0, à 2 en position 3, à 3 en position 6 : la fonction renvoie 3.

def compte_occurrences(x, tab):
    nombre = 0
    # Un seul parcours suffit : on compare chaque élément à x
    for element in tab:
        if element == x:
            nombre = nombre + 1
    return nombre

nombre retient le nombre d’occurrences déjà rencontrées ; c’est lui qu’on renvoie à la fin, et pas autre chose. La comparaison se fait avec ==, ce qui marche aussi bien pour des entiers que pour des chaînes de caractères, donc le troisième exemple du sujet passe sans rien changer. Si tab est vide, la boucle ne s’exécute jamais : on renvoie 0, qui est bien la valeur attendue.

Exercice 2 - rendu_monnaie

L’idée. La somme à rendre est somme_versee - somme_due. L’algorithme glouton consiste à prendre à chaque tour la plus grosse pièce qui ne dépasse pas ce qu’il reste à rendre, à l’ajouter au résultat, puis à la retirer de la somme restante. On recommence tant qu’il reste quelque chose à rendre. Comme le tableau pieces est trié dans l’ordre croissant, on part de la fin (i = len(pieces) - 1) et on fait descendre i tant que la pièce est trop grosse.

Un petit exemple. Pour rendu_monnaie(452, 500), il faut rendre 48. La plus grosse pièce qui tient dans 48 est 20, il reste 28 ; puis encore 20, il reste 8 ; puis 5, il reste 3 ; puis 2, il reste 1 ; puis 1, il reste 0. D’où [20, 20, 5, 2, 1].

pieces = [1, 2, 5, 10, 20, 50, 100, 200]

def rendu_monnaie(somme_due, somme_versee):
    '''Renvoie la liste des pièces à rendre pour rendre la monnaie
    lorsqu'on doit rendre somme_versee - somme_due'''
    rendu = []
    a_rendre = somme_versee - somme_due
    i = len(pieces) - 1
    while a_rendre > 0:
        # On descend dans pieces tant que la pièce courante est trop grosse
        while pieces[i] > a_rendre:
            i = i - 1
        rendu.append(pieces[i])
        a_rendre = a_rendre - pieces[i]
    return rendu

rendu est le tableau qu’on construit et qu’on renverra ; a_rendre est ce qu’il reste encore à rendre, et il diminue à chaque tour, donc la boucle principale finit toujours par s’arrêter. i est l’indice de la pièce qu’on essaie : on ne le remet jamais à la fin du tableau, car une fois qu’une pièce est trop grosse elle le restera, a_rendre ne pouvant que diminuer. C’est aussi pour cela que la boucle interne se termine : la pièce pieces[0] vaut 1 et tient toujours dans une somme strictement positive.

La condition a_rendre > 0 explique le cas rendu_monnaie(700, 700) : la somme à rendre vaut 0, la boucle n’est jamais exécutée et on renvoie le tableau vide [].