É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}\).
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\)
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)\)
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
>>> 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\).
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-nldef nbpy-undchemins(n, m):bksl-nl numerateur = 1bksl-nl for i in range(n + 1, n + m + 1):bksl-nl numerateur py-str= ibksl-nl denominateur = 1bksl-nl for i in range(1, m + 1):bksl-nl denominateur py-str= ibksl-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-nl
A
Pour calculer un produit, on initialise le produit à 1, et non à 0.
- Une somme vide est égale à 0.
- Un produit vide est égal à 1.
Pour la boucle, on peut écrire resultat *= facteur
à la place de resultat = resultat * facteur
. De la même manière qu'on peut écrire resultat += terme
à la place de resultat = resultat + terme
Il existe aussi les raccourcis
-=
, pour la soustraction//=
, pour la division entière%=
, pour le modulo/=
, pour la division continuée**=
, pour la puissance<<=
pour le décalage de bits à gauche>>=
pour le décalage de bits à droite
Formule à justifier ; maths⚓︎
Justifions la formule : nb_chemins(n, m)
est égal à \(\binom{n}{n+m}\).
On rappelle que pour compter le nombre de façons de choisir \(k\) éléments parmi \(n\), on utilise le coefficient binomial $\binom{k}{n}`.
Un chemin allant de \((0, 0)\) jusqu'à \((n, m)\) peut être décrit par une suite de E
et de N
; E
pour aller à l'Est, N
pour aller au Nord. Il doit y avoir \(n\) fois la présence de E
, et \(m\) fois la présence de N
.
Il y a autant de chemins allant de \((0, 0)\) jusqu'à \((n, m)\) que de mots de \(n+m\) lettres composés de \(n\) E
et \(m\) N
. Pour compter ces mots, il suffit de compter le nombre de façons de choisir \(n\) positions parmi les \(n+m\) pour placer les E
. On remarquera que \(\binom{n}{n+m} = \binom{m}{n+m}\), et choisir les N
impose les E
tout autant. Ce qui justifie la formule donnée.
Z