Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité

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

The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.

Commentaire(s)