Énumération des chemins de Schröder⚓︎
Dans une grille, on souhaite compter tous les chemins allant de \((0, 0)\) à \((2n, 0)\), en restant au-dessus ou sur l'axe des abscisses, et avec les mouvements possibles suivants :
- Nord-Est (↗), donc suivi plus tard d'un Sud-Est (↘)
- Sud-Est (↘), qui est donc précédé d'un Nord-Est (↗) correspondant
- Deux fois de suite à l'Est (→→)
Chaque paire (↗, ↘) est associée à un déplacement de deux unités vers l'Est. Ainsi, un chemin de Schröder fait globalement un déplacement horizontal d'un nombre pair d'unités, que l'on note \(2n\).
Objectif : Écrire une fonction telle que schroder(n)
renvoie le nombre de chemins de Schröder allant de \((0, 0)\) à \((2n, 0)\).
Chemins de Schröder de longueur \(2×2\)
Il y en a 6.
Chemins de Schröder de longueur \(2×3\)
Il y en a 22.
Formule
On admettra qu'une relation pour calculer ces nombres \(S_n\) est :
- \(S_0 = 1\), \(S_1 = 2\)
- \((n+1)S_n = (6n-3)S_{n-1} - (n-2)S_{n-2}\), pour \(n>1\).
Exemples
>>> schroder(2)
6
>>> schroder(3)
22
>>> schroder(4)
90
Compléter le code :
La fonction doit renvoyer un nombre entier.
schroderpy-undmem = [...]bksl-nlbksl-nldef schroder(n):bksl-nl if n >= len(schroderpy-undmem):bksl-nl resultat = ... # ... schroder(n - 1) ...bksl-nl # ici schroderpy-undmem est de longueur au moins n, garantibksl-nl schroderpy-undmem.append(...)bksl-nl return schroderpy-undmem[...]bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert schroder(2) == 6bksl-nlassert schroder(3) == 22bksl-nlassert schroder(4) == 90bksl-nlbksl-nlschroderpy-undmem = [1, 2]bksl-nlbksl-nldef schroder(n):bksl-nl if n >= len(schroderpy-undmem):bksl-nl resultat = (bksl-nl (6py-strn - 3) py-str schroder(n - 1)bksl-nl - (n - 2) py-str schroder(n - 2)bksl-nl ) // (n + 1)bksl-nl # ici schroderpy-undmem est de longueur n garantibksl-nl schroderpy-undmem.append(resultat)bksl-nl return schroderpy-undmem[n]bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert schroder(2) == 6bksl-nlassert schroder(3) == 22bksl-nlassert schroder(4) == 90bksl-nlbksl-nl
A
Z