Aller au contenu

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

Exercice

Coder une fonction delannoy qui prend en paramètres deux entiers positifs n et m et qui renvoie le nombre de chemins allant de \((0, 0)\) jusqu'à \((n, m)\) avec les seuls 3 déplacements : ↑, → et ↗.

⚠ On ne vous donne pas de formule, à vous de déterminer une méthode. 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.
Contraintes
  • \(0 \leqslant n < 20\)
  • \(0 \leqslant m < 20\)
  • Modules math et functools interdits
  • Code source limité à 2000 caractères
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.128013.8594.8593.8599],59/f78rnb _o=ylaepcwgu)vd461`3kRmhtsP(S0à+2Cè[-i:050E0w0O0v0#0u0P0p0y0u0v0P0P0s010O0#0x010406050P0B0M0M0v0m0t040S0r0u0B0`0r0n050i111315170 0x04051n1g1q0i1n0 0E0#0D0/0;0?0^0N0#0A0N0u1E0N0O0}050*0o0u0w1z0=0@011D1F1H1F0O1N1P1L0O0m1o0O0N1R1B010j0,0w0n0v0M0w010/1a0P0x0v0n0^0W1L1|1~1,1T1/1P1=1@0}0a0p0Q0m0r0x0r0P0#1d0n0p0(1`0m0m0w0y2l1g230n1o0i1*2y1%1)1(1M0E250^1H0n1;2i1L1w1y0:1S2I0#2K0n0r2O1L0x2r1o2w2y2$101}2m2Q1-2V0m140u0}0p0H2v2*0~2)242,1T2.2:2=0W2^1~2`2w2H012 0v2;040p0J332x0 362}0^393b0p0F3f352*373l2=0g3p3h3r3j380r2/3a2=0G3w2{2+1A2~3B303c0k3G3i3J3k3L3D3c0l3P3y3R3A3C3m0h3X2|3Z3t040H0T3(3I2R3!3M0H2@1h2_3x3)3;3+0H323_343{3:2-3T3b0H3e413g3H3s460}0H3o4a3q3|453#4f3v4i434d4m3,3F4p4c3z3~3O4v3Q3}4e3,3W4i1r2!1g2O2B0E1)2G3z0y2W1^1o4K1p4I2(4G4Q0(2#3Y3}0}0(0;0n2V0t0q1@0M3p0p4w3Z0r0}0s4;4?3}0o4(0#2t3p4|1-0|040R0C3w4q3z0K4(0w0j524B1-0z2=5g4$2-0j5d4*4,5l4k1T550R5s442~0}1f4G5h5u0}0f4{5D3k0}4:5C5m5E040C0$3/375j3c0p5W5x370P0E0}015%5S3z5!2=5W0p0X0r0M0x0u0Y0O0w0f0p2j0p0o0w0P0r2T5`1P2n502l1=0#2r0p0I4)1~4,4.0w0M0I5)3Z5+5V5W0L1;0D611Q6d6f4/0Z0R0n5`0M0C0e0p0$0p642V0M0o6a2o0y0N6h2T0P6k3;6m5-6V0p3a4*0O2n1Q0R0T5`0T0C0p0U0p6y6A6+0v0D2s0p0c5`0b0p0r0B0p0d6S1-6U5-5%013w6V531T5c040#5f4i4=5I015v5Y4x5A7k3Z555G7f795J045L2(7h55587r7h0r5U2V0O5H5N0^7C0}2T7G5t7t6u6v6h7n3;555R4p6W5-7s017b7d7M5y0^7j5M7N387m7A7H014^040s4`7/7,0M0#0}3.7+7(7i0}7z2$7g7:7J043B7%377*7w7:0n5K8a3z7=7@8h3Z7{7}7S54827V2$067X7X7Z7b2r0O0B0m5B847Z8n3,778v8x0}0w0-0w8p5O8s3`8v6W7Z8f047P0r4-4/8P7)0}6x8$7-048D2_7Z7p8l4%7u8*7y0e8;1-8j8`5O5w7W8T8J7B0}0V8}7O8M6e8Z8@0}8 8d7,8W8-34857,7=0!96018G3^9e808:7_808W7v2_787x828I918U9304959u3s5p990t9b568*9g4;7Y9A047q8E7h9w9n9l9n9p9N838S9D9E86949n8W8Y9M7 8b9c9P7.9W9,049m9I3z9$9=3z9t9`9f8g9~4@0}9}a480a09r9?5P9C918/9B905X7h8y0)8B9h2x9j9v9K4+8Z6g9x34aj048)a13*9_8.9T9V9y8Va6aea2828_4v0i4Z0w2y2ZaU4J1x4L2B2E2z0v1OaX0i4K0 a+0)0+0-04.