Exercice
Atteindre un score avec des coups de 3, 5 ou 10 points
Considérez un jeu dans lequel un joueur peut marquer 3, 5 ou 10 points en un seul mouvement. Écrire une fonction qui, pour un score total n, retourne le nombre de façons d’atteindre exactement ce score.
Remarque Le programme doit renvoyer uniquement le nombre de façons et non pas l’énumération détaillée de toutes les façons possibles.
Exemple
Entrée
n = 20
Sortie
4
Explication : il existe 4 façons d’atteindre exactement le score 20.
Solution détaillée
- Principe : on dispose d’un ensemble de scores autorisés
S = [3, 5, 10]. À chaque étape, on peut soit utiliser le premier score, soit l’ignorer et poursuivre avec le reste de la liste. - Cas de base : si
obj == 0, on a trouvé une façon valide ; siobj < 0, la construction est impossible ; siobj > 0et qu’il ne reste plus de scores autorisés, il n’existe aucune solution. - Implémentation :
def nbFacons(obj, S): if obj == 0: return 1 if obj < 0: return 0 if obj > 0 and len(S) == 0: return 0 return nbFacons(obj - S[0], S) + nbFacons(obj, S[1:]) S = [3, 5, 10] obj = 20 print("Le nombre de façons est :", nbFacons(obj, S)) - Résultat attendu : pour
n = 20, la fonction retourne4.
Exercice
Exprimer un entier N comme somme de 1, 3 et 4
Étant donné un entier N, écrire une fonction qui compte le nombre de façons d’exprimer N comme une somme utilisant uniquement les valeurs 1, 3 et 4.
Remarque Le programme renvoie uniquement le nombre de façons et non pas les différentes décompositions.
Exemple
Entrée
N = 5
Sortie
6
Explication : il existe 6 façons d’exprimer 5 comme somme de 1, 3 et 4.
Solution détaillée
- Principe : pour obtenir
N, on peut commencer par utiliser1,3ou4, puis compter récursivement les façons de compléter la somme restante. - Cas de base : si
obj == 0, une décomposition valide a été trouvée ; siobj < 0, le choix n’est pas valide. - Implémentation :
def nbFacons(obj): if obj == 0: return 1 if obj < 0: return 0 return nbFacons(obj - 1) + nbFacons(obj - 3) + nbFacons(obj - 4) obj = 5 print("Le nombre de façons est :", nbFacons(obj)) - Résultat attendu : pour
N = 5, la fonction retourne6.
Exercice
Compter les façons de participation à un concours de codage
Considérez un concours de codage avec n participants distincts. Chaque participant peut soit participer seul, soit être couplé avec au plus un autre participant. Écrire une fonction qui compte le nombre total de façons possibles de participation.
Remarque Le programme renvoie uniquement le nombre de façons et non la liste complète des groupements possibles.
Exemple
Entrée
n = 3
Sortie
4
Explication : une possibilité correspond à trois participants seuls. Les trois autres correspondent aux différents couplages possibles de deux participants.
Solution détaillée
- Principe : pour un participant donné, deux cas sont possibles : soit il reste seul, soit il forme une paire avec l’un des
N-1autres participants. - Relation de récurrence :
concours(N) = concours(N-1) + (N-1) × concours(N-2). Le premier terme correspond au cas où le participant reste seul, le second au cas où il est mis en paire. - Cas de base :
N = 0ouN = 1donne1façon ;N = 2donne2façons. - Implémentation :
def concours(N): if N == 1 or N == 0: return 1 if N == 2: return 2 return concours(N - 1) + (N - 1) * concours(N - 2) - Résultat attendu : pour
n = 3, la fonction retourne4.
Exercice
Nombre de chemins d’un point (n, m) vers l’origine
Vous êtes placé au point (n, m) et vous souhaitez rejoindre l’origine (0, 0) en effectuant uniquement des pas vers la gauche ou vers le haut. Écrire une fonction qui compte le nombre total de chemins possibles.
Remarque Le programme renvoie uniquement le nombre de chemins et non pas la liste détaillée des chemins.
Exemple
Entrée
(3, 6)
Sortie
84
Explication : il existe 84 chemins différents pour aller du point
(3,6) à l’origine en se déplaçant seulement vers la gauche ou vers le haut. Solution détaillée
- Principe : depuis la position
(i, j), on peut aller soit en(i-1, j), soit en(i, j-1). Le nombre de chemins depuis(i, j)est donc la somme des chemins issus de ces deux positions. - Cas de base : si l’on atteint
(0, 0), on retourne1. Si l’un des indices devient négatif, il n’existe aucun chemin valide. Si l’on est sur un bord, il n’existe qu’un seul chemin possible. - Implémentation :
def nbChemins(i, j): if i == j == 0: return 1 if i == 0 and j > 0: return 1 if j == 0 and i > 0: return 1 if i < 0 or j < 0: return 0 return nbChemins(i - 1, j) + nbChemins(i, j - 1) print(nbChemins(3, 6)) - Résultat attendu : pour le point
(3,6), la fonction retourne84.
Sortie
// La sortie apparaîtra ici…
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.