Exercices corrigés sur la récursivité (TD 02)
Exercice 1
Considérez un jeu où un joueur peut marquer 3, 5 ou 10 points en un seul mouvement. Étant donné un score total n, trouvez le nombre de façons d'atteindre le score donné.
Exemple(s)
Il y a 4 façons pour atteindre 20
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 facons est :", nbFacons(obj, S))
Exercice 2
Étant donné N, comptez le nombre de façons d'exprimer N comme la somme de 1, 3 et 4.
Exemple(s)
le nombre de façons d’exprimer N=5 comme la somme des nombres 1, 3 et 4 est 6
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 facons est :", nbFacons(obj))
Exercice 3
Considérez un concours de codage sur developpement-informatique.com. Il y a n participants distincts qui participent au concours. Un seul participant peut se couplé avec au plus un autre participant. Nous devons compter le nombre de façons dont n participants participent au concours de codage.
Exemple(s)
le nombre de façons est 4
(une façon : trois participants restent seuls ; Trois autres façons : [(1, 2) (3)], [(1), (2,3)]et [(1,3) (2)])
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)
Exercice 4
Vous êtes debout sur un point (n, m) et vous voulez aller à l’origine (0, 0) en faisant des pas vers la gauche ou vers le haut, c’est-à-dire à partir de chaque point, vous êtes autorisé à vous déplacer soit en (n-1, m) soit ( n, m-1). Trouvez le nombre de chemins du point (n, m) à l’origine (0, 0)
Exemple(s)
Le nombre de chemins est 84
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))