É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 [bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl 1,bksl-nl ],bksl-nl [bksl-nl 1,bksl-nl 2,bksl-nl 3,bksl-nl 4,bksl-nl 5,bksl-nl 6,bksl-nl 7,bksl-nl 8,bksl-nl 9,bksl-nl ],bksl-nl [bksl-nl 1,bksl-nl 3,bksl-nl 6,bksl-nl 10,bksl-nl 15,bksl-nl 21,bksl-nl 28,bksl-nl 36,bksl-nl 45,bksl-nl ],bksl-nl [bksl-nl 1,bksl-nl 4,bksl-nl 10,bksl-nl 20,bksl-nl 35,bksl-nl 56,bksl-nl 84,bksl-nl 120,bksl-nl 165,bksl-nl ],bksl-nl [bksl-nl 1,bksl-nl 5,bksl-nl 15,bksl-nl 35,bksl-nl 70,bksl-nl 126,bksl-nl 210,bksl-nl 330,bksl-nl 495,bksl-nl ],bksl-nl [bksl-nl 1,bksl-nl 6,bksl-nl 21,bksl-nl 56,bksl-nl 126,bksl-nl 252,bksl-nl 462,bksl-nl 792,bksl-nl 1287,bksl-nl ],bksl-nl [bksl-nl 1,bksl-nl 7,bksl-nl 28,bksl-nl 84,bksl-nl 210,bksl-nl 462,bksl-nl 924,bksl-nl 1716,bksl-nl 3003,bksl-nl ],bksl-nl [bksl-nl 1,bksl-nl 8,bksl-nl 36,bksl-nl 120,bksl-nl 330,bksl-nl 792,bksl-nl 1716,bksl-nl 3432,bksl-nl 6435,bksl-nl ],bksl-nl [bksl-nl 1,bksl-nl 9,bksl-nl 45,bksl-nl 165,bksl-nl 495,bksl-nl 1287,bksl-nl 3003,bksl-nl 6435,bksl-nl 12870,bksl-nl ],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écharger Téléverser Recharger Sauvegarder

nbpy-undcheminspy-undmem = dict()bksl-nlbksl-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-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-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