É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-nlnbpy-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 (m == 0):bksl-nl resultat = 1bksl-nl else:bksl-nl resultat = nbpy-undchemins(n - 1, m ) + nbpy-undchemins(n, m - 1)bksl-nl nbpy-undcheminspy-undmem[(n, m)] = resultatbksl-nl return nbpy-undcheminspy-undmem[(n, m)]bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undchemins(4, 3) == 35bksl-nlassert nbpy-undchemins(3, 3) == 20bksl-nlbksl-nl

A

Une adaptation directe des indications de l'énoncé.

Compléments

Un chemin pour aller de \((0, 0)\) à \((4, 3)\) peut être décrit par une chaine de caractères composée de 4 'E' et 3 'N'.

Par exemple, "EENENNE" décrit

Il y a autant de chemins pour aller de \((0, 0)\) à \((4, 3)\) que de chaines de caractères composées de 4 'E' et 3 'N'.

Comment les compter ?

• Il y a \(4+3 = 7\) caractères.
• Il y a \(4\) choix possibles parmi les 7 places pour placer les 'E'.
• Ensuite, les 'N' prennent les 3 places restantes, sans avoir le choix, de manière unique.

Le nombre de chemins pour aller de \((0, 0)\) à \((4, 3)\) est le nombre de façons de choisir 4 places parmi 7.

De manière générale, le nombre de chemins pour aller de \((0, 0)\) à \((n, m)\) est le nombre de façons de choisir \(n\) places parmi \(n+m\).

En cours de mathématiques, on peut voir que ce nombre est :

\[\binom{n}{n+m} = \dfrac{(n+m)!}{n!m!}\]

Où :

• \(n! = 1×2×3×\cdots×(n-1)×n\)
• \(m! = 1×2×3×\cdots×(m-1)×m\)
• \((n+m)! = 1×2×3×\cdots×(n+m-1)×(n+m)\)

Par exemple,

• \(4! = 1×2×3×4\)
• \(3! = 1×2×3\)
• \((4+3)! = 1×2×3×4×5×6×7\)

\[\binom{4}{4+3} = \dfrac{1×2×3×4×5×6×7}{1×2×3×4\quad × \quad 1×2×3} = \dfrac{5×6×7}{1×2×3} = \dfrac{5×\cancel{6}×7}{1×\cancel{2×3}} = 35\]

Z