Énumération des chemins de Delannoy⚓︎
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é.
- ↗ Aller au Nord-Est en diagonale, sur le prochain nœud.
Les chemins pour aller de \((0, 0)\) à \((3, 3)\)
Écrire une fonction telle que delannoy(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 trois catégories : - ceux qui venaient de(n - 1, m )
, - ceux qui venaient de(n , m - 1)
, - ceux qui venaient de(n - 1, m - 1)
,- ces trois catégories sont distinctes et se comptent bien par récursivité.
- On utilisera un dictionnaire pour mémoriser les résultats intermédiaires.
Exemples
>>> delannoy(3, 3)
63
>>> delannoy(2, 1)
5
Compléter le code :
delannoypy-undmem = dict()bksl-nlbksl-nldef delannoy(n, m):bksl-nl if (n, m) not in delannoypy-undmem:bksl-nl if (n == 0) or (...):bksl-nl resultat = ...bksl-nl else:bksl-nl resultat = ...bksl-nl delannoypy-undmem[(n, m)] = ...bksl-nl return ...bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert delannoy(3, 3) == 63bksl-nlassert delannoy(2, 1) == 5bksl-nlbksl-nldelannoypy-undmem = dict()bksl-nlbksl-nldef delannoy(n, m):bksl-nl if (n, m) not in delannoypy-undmem:bksl-nl if (n == 0) or (m == 0):bksl-nl resultat = 1bksl-nl else:bksl-nl resultat = (bksl-nl delannoy(n - 1, m )bksl-nl + delannoy(n, m - 1)bksl-nl + delannoy(n - 1, m - 1)bksl-nl )bksl-nl delannoypy-undmem[(n, m)] = resultatbksl-nl return delannoypy-undmem[(n, m)]bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert delannoy(3, 3) == 63bksl-nlassert delannoy(2, 1) == 5bksl-nlbksl-nl
A
Z