É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 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 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

🐍 Console Python

>>> delannoy(3, 3)
63
>>> delannoy(2, 1)
5

Compléter le code :

###

# testsbksl-nlbksl-nlassert delannoy(3, 3) == 63bksl-nlassert delannoy(2, 1) == 5bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlDELANNOY = [bksl-nl [1, 1, 1, 1, 1, 1, 1, 1, 1],bksl-nl [1, 3, 5, 7, 9, 11, 13, 15, 17],bksl-nl [1, 5, 13, 25, 41, 61, 85, 113, 145],bksl-nl [1, 7, 25, 63, 129, 231, 377, 575, 833],bksl-nl [1, 9, 41, 129, 321, 681, 1289, 2241, 3649],bksl-nl [1, 11, 61, 231, 681, 1683, 3653, 7183, 13073],bksl-nl [1, 13, 85, 377, 1289, 3653, 8989, 19825, 40081],bksl-nl [1, 15, 113, 575, 2241, 7183, 19825, 48639, 108545],bksl-nl [1, 17, 145, 833, 3649, 13073, 40081, 108545, 265729],bksl-nl]bksl-nlbksl-nlfor n in range(9):bksl-nl for m in range(9):bksl-nl attendu = DELANNOY[n][m]bksl-nl assert delannoy(n, m) == attendu, f"Erreur avec n = {n} et m = {m}."bksl-nlbksl-nl 5/5

delannoypy-undmem = dict()bksl-nlbksl-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-nl# testsbksl-nlbksl-nlassert delannoy(3, 3) == 63bksl-nlassert delannoy(2, 1) == 5bksl-nlbksl-nldelannoypy-undmem = dict()bksl-nlbksl-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 = delannoy(n - 1, m) + delannoy(n, m - 1) + delannoy(n - 1, m - 1)bksl-nl delannoypy-undmem[(n, m)] = resultatbksl-nl return delannoypy-undmem[(n, m)]bksl-nlbksl-nl

A

Z