Aller au contenu

Énumération des chemins à Manhattan

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é.

Les chemins pour aller de \((0, 0)\) à \((4, 3)\)

Ceux passant par \((3, 3)\), il y en a 20.

Ceux passant par \((4, 2)\), il y en a 15.

Exercice

Coder une fonction nb_chemins qui prend deux entiers positifs n et m en paramètres et renvoie le nombre de chemins allant de \((0, 0)\) jusqu'à \((n, m)\) avec deux types de mouvements autorisés (→ 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 deux catégories :
      • ceux qui venaient de (n - 1, m ),
      • ceux qui venaient de (n , m - 1),
    • ces deux 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 : /
.8593.128013.8594x/.ùrnbOylaeêu)d6ç3×m?(P+02è-U],59fq!7}8 N_o={pcwgv41`kRIéhtsàSLC[Di:E050s0o0.0n0_0m0/0R0Y0m0n0/0/0V010.0_0X010406050/0q0x0x0n0h0l040;0U0m0q1c0U0i050e1j1l1n1p1h0X04051F1y1I0e1F1h0s0_0#1416181a0-0_0!0-0m1W0-0.1f050 0j0m0o1R1719011V1X1Z1X0.1)1+1%0.0h1G0.0-1-1T010L110o0i0n0x0o01141s0/0X0n0i1a0D1%2e2g211/241+27291f0b0R0A0h0U0X0U0/0_1v0i0R0}2c0h0h0o0Y2D1y2l0i1G0e1 2Q1|1~1}1(0s2n1a1Z0i262A1%1O1Q151.2!0_2$0i0U2*1%0X2J1G2O2Q2{1i2f2E2,222;0h1m0m1f0R0%2N2 1g2~2m311/3335370D3a2g3c2O2Z013h0n36040R0v3l2P1h3o3f1a3r3t0R0$3x3n2 3p3D370J3H3z3J3B3q0U343s370t3O3d301S3g3T3i3u0O3Y3A3#3C3%3V3u0Q3+3Q3-3S3U3E0K3?3e3^3L040%0C3}3!2-3_3(0%391z3b3P3~46400%3k4b3m4d45323/3t0%3w4j3y3Z3K4o1f0%3G4s2Q2^0o2Q2*2T0s1~2Y3R0Y2=2a1G4F1H2_3Z2|3b054L0}2`3@4f1f0i0j0T0Y0-0o0x2/0/0T290x3H0R4u3R0U1f0V4=4@3 0j1f1O2L3H4}461e040z0r3O4l3p0)500o0L533,460Z375h4Z320L4#4%4)4+4-5m4e22560z5v4m3g4#5A3p560I4|5i321f4;4A545x1f0r0`443p5k3u0R5X5E3R0/0s1f015(5T5!5$5W5X0?0U0x0X0m0E0.0o0I0R2B0R0j0o0/0U2/5`1+2F0_2L0_1w270_2J0R0(4$4(4*4,0i4.4:0(5*3^5#375X0R0*260#611,6f5s6i6k4+0@0z0i5`0x0r0H0R0`0R642;0x0j6c2G6z5u4A5b5+6q6r6r3s160i0.2F1,0z0C5`0C0r0R0:0R6E6G6/0n0#2K0R0c0R0U0q0R0a6n466p5-0R5(013O6Z5O1/5d040_5g4A4?5J1/5y5Z3 5D5N7k1a5G5I5n5C045M2}7r0156597i7c1a0U5V2;0.7u5w1/7H1f2/7L5B3C5q6g5t6j4/4+7n551f5S6V6Z7b7A7e7g7R5F1f5z7q7v7T041x7E7A4_040V4{7`7?014,1f437=7M7s5Q7.4^5V3T8a3^7m867S3q5L8e467|7~8l228304857z817C7%2{067)8A7j817e2J0.0q0h7_2{8C87820_4x7a8B7F017e0o120o7!5P048x4c8B7)8S0i7U6T7X4:8Y7l1f6D8/7@8J4U7A7t808M8*7x8?7B5Q0H8p7N4`948@5r6h6U8u8M8g9c8i8~8^3m8L8i7|0F978N8P8h7/045H8|9g8k9r3R7C9o7|0B9o9h997W0/909e8_819h9J1f9u8K8)9x9R7{1f9n9v3p8r4a9f9s7D8y7*8D1f8F8H9i2P9k3K8+9a8-7Z9y8f8;7;9$3R9N9`7#9t9E9T9L9d923Y0e4W4D1J4R0e4P2R4H1y2Uaj0n1*acaf1P3caf0~10123c2*3p0n0s0x1w2C682E0s2g0!0o0h1f1EayaAaC2D0F1c0.1`045/5;0m0,296%9I1L3c1F0G309@0R2z8H0R6#aJ6)9;3R1n2C0-1m5^0d1f090z6+6-0r099(3b6:a@3^a_1 a|0oa~04b00z0$5`0vb4b69j0X0o1u0R0p1|1,0s0,0Y0h2Ca-1n0R0q2$140-10bF6S1n0n2L0E2J134L5;2A0,bv1,0$4?ab04000{001ybZ0R0~3vbY4Mb!0Sb%aab.0f1Ja(040AbCbe4+5=5_b-4X010{0{0Sc5c679b=4X2Fbxbz6(050_0x0!a:0m0.1a2b0/0h0Y1ach0naI0/aa9@0T0%0Q0f0/0#0!010e4Bb_0+0m0R0la:a:1u2g6(6S9@13a.0hck1+cX2G8Sbba{0na}a b16,0R6.b54=6;c$cec(c*bgb1bj3vbm4=0M0qbVbGbI5 a?0YbLbNbP2cbS0/bU132GbX4Vb.b#b;b)b+0vc14D00b:b(b?b^1EaV5:a!6(1+bQ5:0X5^cX0ydv050q0m3c1Z04cKcMcOc?a`bdbfb00$0Bdo0V0R0Oc:7id70hbM0.bO5 b@0edN1hdNdPcN0nb946c%dUc+0$d%8K4)610da-2A2BancV1n4,6Md50Oa-160Yd5cWefbMa=dBdpb!b$dt4Xd/d;05dN0{6j0q2Cc0endi4Xdrdlb.a-2J0i2:dAd5do5=el13bP0 6%5 5`0/2g136_61cX64e20_0d5`2G1m0i0_d-bDe.d00oet0_ardKb_0=6x5:6Qd28,cV6 cXa;c!1,dSbcc)bec+b2c.c~7ic=7Ad|fbdVc{bkfg8K5 eM0R6Of0a?0L0n0u1wdf1,e(2BcXbXePehe9340_d#d/1M1H040^1,e-e/6c0!0,0i0,d*1+63e~6P6RfCcUe5a/f6a?f9c^fcc`fec/bn9:fi81fkc_bh6F0R6He0b7frecfte f)0Rfxfz6jd60-61fEd`22f}f=b00ig3boegeieafLf:d}c`0i0B0xgo2PfNb_ex2c8HfBg1c)0-aZc)0_e?0/5`1wa-bq6(6v6b0Re?14f%fvg57%fOaxa^c@gv090@090j2/5:0W0i0Pg?gy0P0Rd!090s0Ld*0Y0W6Egy0r0Ng^0i0N0xh70993ap0#b_0k0g6KdIe{d=e_guflc+h9g|380w0D0w0v0w090Y0s0U0.0/0w6E0F0%0r0wgnf_2QeudNhpf~0zhbht0%hvhxhzhBhDhFhThIhKgzhN1yhPhofjg+hqf?gx6H0NhVhXhyhAhChEhGh?h(h h5gAhOe_1h0ehmfPb{cXb}aX5_hldLhn4Y8Mgkfm0$h^d!hWhwhyd h+d:i6evh.f|h:hS0viohuiri4h,iwhQh/dTh;bhdXbliDiqhY0$0w0J0w0t0wd$iueui8ih0|1PayiAglg.g:6O0W0$g^iOg{g}g h10WiRisiUiWiYg^i|0wd d0az0R0w0R09j52Yi|i@j9i_bM0WiViX0Oj1h`jeg~h0jhiVhA2geh0m0W0t0Pj0i{hZju8V0Wir0Pje0v0Jhd1y4Fdw0S6 136`2IfA6)130x0,1 4McV1t135f24d7fIf,cXd70m0YdKa=bE2cj(660_266(i.5:0_3sgCi74F.