Aller au contenu

Sujet n°1

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°1☘

Écrire une fonction recherche qui prend en paramètres caractere, un caractère, et mot, une chaîne de caractères, et qui renvoie le nombre d’occurrences de caractere dans mot, c’est-à-dire le nombre de fois où caractere apparaît dans mot.

Exemples

>>> recherche('e', "sciences") 
2 
>>> recherche('i', "mississippi") 
4 
>>> recherche('a', "mississippi") 
0
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def recherche(caractere, mot):
    """
    caractere - str, un caractère
    mot - str, une chaîne de caractères
    Sortie: int, nombre d'occurences de caractere dans mot
    """
    nb_occur = 0
    for carac in mot:
        if carac == caractere:
            nb_occur += 1
    return nb_occur


if __name__ == '__main__':
    print(recherche('e', "sciences") == 2)
    print(recherche('i', "mississippi") == 4)
    print(recherche('a', "mississippi") == 0)

Exercice n°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 pieces = [100, 50, 20, 10, 5, 2, 1] (on supposera qu’il n’y a pas de limitation quant à leur nombre), on cherche à donner la liste de pièces à rendre pour une somme donnée en argument.

Commentaires

Ici, le mot « liste » est à comprendre dans le sens « liste Python » (c'est-à-dire tableau) plutôt que dans le sens du type abstrait de données liste étudié en Terminale.

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Pieces = [100, 50, 20, 10, 5, 2, 1]

def rendu_glouton(arendre, solution=None, i=0):
    if solution is None:
        solution = []
    if arendre == 0:
        return ...
    p = Pieces[i]
    if p <= ... :
        solution.append(...)
        return rendu_glouton(..., solution, i)
    else :
        return rendu_glouton(arendre, solution, ...)
Commentaire sur le code original

Pour télécharger l'original du fichier à compléter, cliquer ici.

Ce code original contient un paramètre par défaut mutable. À chaque fois que la fonction rendu_glouton() sera appelée, il y aura empilement des nouvelles décompositions aux décompositions déjà obtenues...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Pieces = [100, 50, 20, 10, 5, 2, 1]

def rendu_glouton(arendre, solution=[], i=0):
    if arendre == 0:
        return ...
    p = Pieces[i]
    if p <= ... :
        solution.append(...)
        return rendu_glouton(arendre - p, solution, i)
    else :
        return rendu_glouton(arendre, solution, ...)

On devra obtenir : 

>>> rendu_glouton(68, [], 0) 
[50, 10, 5, 2, 1] 
>>> rendu_glouton(291, [], 0) 
[100, 100, 50, 20, 20, 1]

Commentaire

Avec les valeurs par défaut des paramètres, on peut aussi procéder aux appels suivants pour obtenir le même résultat : 

>>> rendu_glouton(68) 
[50, 10, 5, 2, 1] 
>>> rendu_glouton(291) 
[100, 100, 50, 20, 20, 1]

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
Pieces = [100, 50, 20, 10, 5, 2, 1]

def rendu_glouton(arendre, solution=None, i=0):
    if solution is None:
        solution = []
    if arendre == 0:
        return solution
    p = Pieces[i]
    if p <= arendre :
        solution.append(p)
        return rendu_glouton(arendre - p, solution, i)
    else :
        return rendu_glouton(arendre, solution, i+1)


if __name__ == '__main__':
    print(rendu_glouton(68, [], 0) == [50, 10, 5, 2, 1] )
    print(rendu_glouton(291, [], 0) == [100, 100, 50, 20, 20, 1])