Énumération des chemins à Manhattan

Dans une grille de taille \(n×m\), on souhaite compter tous les chemins allant du coin inférieur gauche (au Sud-Ouest) vers le coin supérieur droit (au Nord-Est).

Les seuls mouvements autorisés sont :

• Aller au Nord (↑) d'une unité.
• Aller à l'Est (→) d'une unité.

Les chemins pour aller de \((0, 0)\) à \((4, 3)\)

Ceux passant par \((3, 3)\), il y en a 20.

Ceux passant par \((4, 2)\), il y en a 15.

Écrire une fonction telle que nb_chemins(n, m) renvoie le nombre de chemins allant de \((0, 0)\) jusqu'à \((n, m)\).

Pour ce faire, on remarquera :

• Si n ou m est nul,
  • alors le seul chemin est en ligne droite, la réponse est 1,
• sinon :
  • n et m sont non nuls et les chemins qui vont en (n, m) se répartissent en deux catégories :
    • ceux qui venaient de (n - 1, m ),
    • ceux qui venaient de (n , m - 1),
  • ces deux catégories sont distinctes et se comptent bien par récursivité.
• On utilisera un dictionnaire pour mémoriser les résultats intermédiaires.

Exemples

🐍 Console Python

>>> nb_chemins(3, 3)
20
>>> nb_chemins(4, 2)
15
>>> nb_chemins(4, 3)
35

Contraintes : Ici, \(0\leqslant n \leqslant 20\) et \(0\leqslant m \leqslant 20\).

Compléter le code :

###

Lancer# testsbksl-nlbksl-nlassert nbpy-undchemins(3, 3) == 20bksl-nlassert nbpy-undchemins(4, 2) == 15bksl-nlassert nbpy-undchemins(4, 3) == 35bksl-nlbksl-nl# autres testsbksl-nlbksl-nlNBpy-undCHEMINS = [bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1, ],bksl-nl [1, 2, 3, 4, 5, 6, 7, 8, 9, ],bksl-nl [1, 3, 6, 10, 15, 21, 28, 36, 45, ],bksl-nl [1, 4, 10, 20, 35, 56, 84, 120, 165, ],bksl-nl [1, 5, 15, 35, 70, 126, 210, 330, 495, ],bksl-nl [1, 6, 21, 56, 126, 252, 462, 792, 1287, ],bksl-nl [1, 7, 28, 84, 210, 462, 924, 1716, 3003, ],bksl-nl [1, 8, 36, 120, 330, 792, 1716, 3432, 6435, ],bksl-nl [1, 9, 45, 165, 495, 1287, 3003, 6435, 12870, ],bksl-nl]bksl-nlbksl-nlfor n in range(9):bksl-nl for m in range(9):bksl-nl attendu = NBpy-undCHEMINS[n][m]bksl-nl assert nbpy-undchemins(n, m) == attendu, f"Erreur avec n = {n} et m = {m}."bksl-nlbksl-nl Valider 5/5 TéléchargerTéléverser RechargerSauvegarder

nbpy-undcheminspy-undmem = dict()bksl-nlbksl-nldef nbpy-undchemins(n, m):bksl-nl if (n, m) not in nbpy-undcheminspy-undmem:bksl-nl if (n == 0) or (...):bksl-nl resultat = ...bksl-nl else:bksl-nl resultat = nbpy-undchemins(..., ...) + ...bksl-nl nbpy-undcheminspy-undmem[(n, m)] = ...bksl-nl return ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undchemins(3, 3) == 20bksl-nlassert nbpy-undchemins(4, 2) == 15bksl-nlassert nbpy-undchemins(4, 3) == 35bksl-nlbksl-nlNone

A

Z