adplus-dvertising

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

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

Exercice 1

Étant donné une distance «dist», comptez le nombre total de chemins pour parcourir la distance avec 1, 2 et 3 pas.

Exemple(s)
  dist = 4
Le nombre de chemins est 7

Voir solution


def nbCheminsDist(dist):
    if dist == 0:
        return 1

    if dist < 0:
        return 0

    return nbCheminsDist(dist-1)+nbCheminsDist(dist-2)+nbCheminsDist(dist-3)


dist = 4
print("Il y a {} chemins".format(nbCheminsDist(dist)))
                                            

Exercice 2

Étant donné un labyrinthe (matrice de dimension (m x n) ) avec des obstacles, comptez le nombre de chemins pour atteindre la cellule (m-1,n-1) a partir de la cellule (0,0). Une cellule dans un labyrinthe donné a la valeur -1 s’il s’agit d’un blocage ou d’une impasse, sinon 0. À partir d’une cellule donnée, nous sommes autorisés à passer aux cellules (i + 1, j) et (i, j + 1) uniquement

Exemple(s)
  [[0, 0, 0, 0],[0, -1, 0, 0],[-1, 0, 0, 0],[0, 0, 0, 0]]
Le nombre de chemins est 4

Voir solution


def labyrinth(mat, i, j):
    if i == len(mat)-1 and j == len(mat[0])-1:
        return 1

    if j >= len(mat[0]) or i >= len(mat):
        return 0

    if mat[i][j] == -1:
        return 0

    else:
        return labyrinth(mat, i+1, j)+labyrinth(mat, i, j+1)


mat = [[0,  0, 0, 0],
       [0, -1, 0, 0],
       [-1, 0, 0, 0],
       [0,  0, 0, 0]]

print('le nombre de chemin est : ', labyrinth(mat, 0, 0))
                                            

Exercice 3

Étant donné un labyrinthe (m x n), comptez le nombre de chemins pour atteindre la cellule (m-1,n-1) a partir de la cellule (0,0) avec un maximum de k tours autorisés.

Un mouvement est considéré comme un tour, si nous nous déplaçons le long d’une ligne et que nous nous déplaçons maintenant le long d’une colonne. OU nous nous déplaçions le long de la colonne et maintenant nous déplaçons le long de la ligne.

Exemple(s)
  m = 3, n = 3, k = 2
Le nombre de chemins est 4

Voir solution


def nombre(mat, i, j, k):
    return labyrinth2(mat, i, j, k, 0)+labyrinth2(mat, i, j, k, 1)


# d: la direction  ; 0 le long de la ligne ; 1 le long de la colonne
def labyrinth2(mat, i, j, k, d):
    if k == 0:
        if i == len(mat)-1 and j == len(mat[0])-1:
            return 1
        return 0

    if i == len(mat)-1 and j == len(mat[0])-1:
        return 1

    if j >= len(mat[0]) or i >= len(mat):
        return 0

    else:
        if d == 0:
            return labyrinth2(mat, i, j+1, k, d)+labyrinth2(mat, i+1, j, k-1, 1)
        else:
            return labyrinth2(mat, i+1, j, k, d)+labyrinth2(mat, i, j+1, k-1, 0)


mat = [[0,  0, 0],
       [0, 0, 0],
       [0, 0, 0]]

print('le nombre de chemin est : ', nombre(mat, 0, 0, 2))
                                            
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.