Aller au contenu

Sujet n°41

Sujet original

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

Exercice n°1☘

Écrire une fonction recherche(caractere, chaine) qui prend en paramètres caractere, un unique caractère (c’est-à-dire une chaîne de caractères 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

>>> 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
18
19
20
21
22
def recherche(caractere, chaine):
    """
    caractere - str, un caractère
    chaine - str, une chaîne de caractères
    Sortie: int, nombre d'occurences de caractere dans chaine
    """
    nb_occur = 0
    for carac in chaine:
        if carac == caractere:
            nb_occur += 1
    return nb_occur


if __name__ == '__main__':
    # Exemples de l'énoncé
    print(recherche('e', "sciences") == 2)
    print(recherche('i',"mississippi") == 4)
    print(recherche('a',"mississippi") == 0)

    # Exemples supplémentaires
    print(recherche('a', "abracadabra") == 5)
    print(recherche('i', "Supercalifragilisticexpialidocious") == 7)

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 valeurs = [100, 50, 20, 10, 5, 2, 1]. On suppose que les pièces et billets sont disponibles sans limitation.

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

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 valeurs à rendre.

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

def rendu_glouton(arendre, rang):
    if arendre == 0:
        return ...
    v = valeurs[rang]
    if v <= ... : 
        return ... + rendu_glouton(a_rendre - v, rang) 
    else : 
        return rendu_glouton(a_rendre, ...)
Commentaire sur le code original

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

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]

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

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


if __name__ == '__main__':
    # Exemples de l'énoncé
    print(rendu_glouton(67, 0) == [50, 10, 5, 2])
    print(rendu_glouton(291, 0) == [100, 100, 50, 20, 20, 1])
    print(rendu_glouton(291, 1) == [50, 50, 50, 50, 50, 20, 20, 1])

    #○ Exemples supplémentaires
    print(rendu_glouton(68, 0) == [50, 10, 5, 2, 1] )
    print(rendu_glouton(19, 0) == [10, 5, 2, 2])