Compter le nombre de chemins pour parcourir une distance
Étant donnée une distance dist, écrire une fonction qui compte le nombre total de chemins permettant de parcourir exactement cette distance en utilisant uniquement des pas de longueur 1, 2 et 3.
dist = 4
7
- Principe : à chaque étape, on peut avancer de
1,2ou3. Le nombre total de chemins est donc la somme des solutions obtenues après avoir retiré1,2ou3à la distance restante. - Cas de base : si
dist == 0, on a trouvé un chemin valide, donc on retourne1. Sidist < 0, le chemin est impossible, donc on retourne0. - Implémentation :
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))) - Résultat attendu : pour
dist = 4, la fonction retourne7.
Compter le nombre de chemins dans un labyrinthe avec obstacles
Étant donné un labyrinthe représenté par une matrice de taille m × n, écrire une fonction qui compte le nombre de chemins permettant d’atteindre la case (m-1, n-1) à partir de la case (0, 0).
Une case contient la valeur -1 si elle est bloquée, sinon 0. À partir d’une case, seuls les déplacements vers le bas et vers la droite sont autorisés.
[[0, 0, 0, 0], [0, -1, 0, 0], [-1, 0, 0, 0], [0, 0, 0, 0]]
4
- Principe : depuis une case libre, le nombre de chemins est la somme du nombre de chemins obtenus en allant vers le bas et vers la droite.
- Cas de base : si la case d’arrivée est atteinte, on retourne
1. Si l’on sort de la matrice ou si la case est bloquée, on retourne0. - Implémentation :
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 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 chemins est :", labyrinth(mat, 0, 0)) - Résultat attendu : pour l’exemple donné, la fonction retourne
4.
Compter le nombre de chemins avec un maximum de k tours
Étant donné un labyrinthe de taille m × n, écrire une fonction qui compte le nombre de chemins permettant d’atteindre la case (m-1, n-1) à partir de la case (0, 0) avec un maximum de k tours autorisés.
Un tour correspond à un changement de direction : on se déplaçait horizontalement puis verticalement, ou inversement. Les déplacements autorisés sont uniquement vers la droite et vers le bas.
m = 3, n = 3, k = 2
4
- Principe : pour résoudre ce problème, il faut connaître la position courante, le nombre de tours restants, ainsi que la direction du dernier déplacement.
- Direction : on utilise un paramètre
d:0pour un déplacement horizontal et1pour un déplacement vertical. Lorsqu’on change de direction, on diminuek. - Résultat final : le nombre total de chemins s’obtient en essayant de commencer selon les deux directions possibles.
- Implémentation :
def nombre(mat, i, j, k): return labyrinth2(mat, i, j, k, 0) + labyrinth2(mat, i, j, k, 1) # d : direction # 0 = déplacement horizontal # 1 = déplacement vertical 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 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 chemins est :", nombre(mat, 0, 0, 2)) - Résultat attendu : pour une grille
3 × 3aveck = 2, la fonction retourne4.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.