Énumération des chemins dans une petite grille⚓︎
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
oum
est nul,- alors le seul chemin est en ligne droite, la réponse est
1
,
- alors le seul chemin est en ligne droite, la réponse est
- sinon :
n
etm
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)
,
- ceux qui venaient de
- 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
>>> 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 :
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