adplus-dvertising

Exercices corrigés sur la récursivité (TD 02)

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)
  n = 20
Il y a 4 façons pour atteindre 20
 le programme renvoie uniquement le nombre de façons et non les façons.

Voir solution

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)
  N = 5
le nombre de façons d’exprimer N=5 comme la somme des nombres 1, 3 et 4 est 6
 le programme renvoie uniquement le nombre de façons et non les façons.

Voir solution

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)
  n = 3
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)])
 le programme renvoie uniquement le nombre de façons et non les façons.

Voir solution

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)
  (3,6)
Le nombre de chemins est 84
 le programme renvoie uniquement le nombre de chemins et non les chemins.


Voir solution

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))
                                            
Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.