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