Aller au contenu

Énumération des chemins dans une grande grille⚓︎

Dans une grande 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).

⚠ Dans cet exercice, on pourra avoir \(0\leqslant n \leqslant 1000\) et \(0\leqslant m \leqslant 1000\).

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)\)

Il y en a 35.

É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 admettra que nb_chemins(n, m) est égal à \(\binom{n}{n+m}\).

\[\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)\)

Utilisation pour nb_chemins(4, 3)

  • \(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~×~1×2×3}\]
\[\binom{4}{4+3} = \dfrac{5×6×7}{1×2×3} = 35\]

Utilisation pour nb_chemins(n, m)

  • \(n! = 1×2×3×\cdots×n\)
  • \(m! = 1×2×3×\cdots×m\)
  • \((n+m)! = 1×2×3×\cdots×(n+m) = 1×2×3×\cdots×n×(n+1)×\cdots×(n+m)\)
\[\binom{n}{n+m} = \dfrac{1×2×3×\cdots×(n+m)}{1×2×3×\cdots×n~×~1×2×3\cdots×m}\]
\[\binom{n}{n+m} = \dfrac{\xcancel{(1×2×3×\cdots×n)}~×~(n+1)×\cdots×(n+m)}{\xcancel{1×2×3×\cdots×n}~×~1×2×3×\cdots×m}\]

En conclusion

On déduit la formule simple, à utiliser ici :

nb_chemins(n, m) est égal à \(\dfrac{(n+1)×(n+2)×(n+3)×\cdots×(n+m)}{1×2×3×\cdots×m}\)

  • Pour calculer nb_chemins(n, m),
    • on fera une boucle pour calculer le numérateur
    • et une autre boucle pour calculer le dénominateur
    • on terminera par la division entière.
  • Il sera interdit d'utiliser le module math

Exemples

🐍 Console Python
>>> nb_chemins(3, 3)
20
>>> nb_chemins(4, 2)
15
>>> nb_chemins(4, 3)
35

Contraintes : Ici, \(0\leqslant n \leqslant 1000\) et \(0\leqslant m \leqslant 1000\).

###
# 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-nldef FACT(n):bksl-nl ans = 1bksl-nl for i in range(1, n + 1):bksl-nl ans py-str= ibksl-nl return ansbksl-nlbksl-nlfor (n, m) in [(13, 17), (13, 18), (14, 17), (14, 18), (200, 221)]:bksl-nl attendu = FACT(n + m) // FACT(n) // FACT(m)bksl-nl assert nbpy-undchemins(n, m) == attendu, f"Erreur avec n = {n} et m = {m}"bksl-nlbksl-nl ∞/∞

def nbpy-undchemins(n, m):bksl-nl numerateur = ...bksl-nl for i in range(...):bksl-nl numerateur = ...bksl-nl denominateur = ...bksl-nl for i in range(...):bksl-nl denominateur = ...bksl-nl return numerateur ... denominateurbksl-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

Retour en haut de la page