Aller au contenu

Ep 36

le document

l'algorithme

Issue de : 23-NSI-41⚓

EXERCICE 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ù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 :

🐍 Script Python
>>> recherche('e', "sciences")
2
>>> recherche('i',"mississippi")
4
>>> recherche('a',"mississippi")
0

RĂ©ponse

Complétez le code ci-dessous

###
# Mettre votre code icibksl-nlbksl-nl

Solution

###
def recherche(caractere, chaine):bksl-nl somme = 0bksl-nl for lettre in chaine:bksl-nl if lettre == caractere:bksl-nl somme += 1bksl-nl return sommebksl-nlbksl-nltry:bksl-nl assert recherche('e', "sciences") == 2bksl-nl assert recherche('i',"mississippi") == 4bksl-nl assert recherche('a',"mississippi") == 0bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme đŸ€”')bksl-nl

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 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.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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, ...)

Exemple :

🐍 Script Python
>>> 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]

RĂ©ponse

Complétez le code ci-dessous

###
def rendupy-undglouton(apy-undrendre, rang):bksl-nl if apy-undrendre == 0:bksl-nl return ... bksl-nl v = valeurs[rang]bksl-nl if v <= ...: bksl-nl return ... + rendupy-undglouton(apy-undrendre - v, rang) bksl-nl else:bksl-nl return rendupy-undglouton(apy-undrendre, ...) bksl-nl

Solution

###
valeurs = [100,50,20,10,5,2,1]bksl-nlbksl-nldef rendupy-undglouton(apy-undrendre, rang):bksl-nl if apy-undrendre == 0:bksl-nl return []bksl-nl v = valeurs[rang]bksl-nl if v <= apy-undrendre :bksl-nl return [v] + rendupy-undglouton(apy-undrendre - v, rang)bksl-nl else :bksl-nl return rendupy-undglouton(apy-undrendre, rang + 1)bksl-nlbksl-nltry:bksl-nl assert rendupy-undglouton(67, 0) == [50, 10, 5, 2]bksl-nl assert rendupy-undglouton(291, 0) == [100, 100, 50, 20, 20, 1]bksl-nl assert rendupy-undglouton(291,1) == [50, 50, 50, 50, 50, 20, 20, 1]bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme đŸ€”')bksl-nl