Aller au contenu

Nombre de chemins dans une grille

Dans une grille de taille \(n×m\), on souhaite compter tous les chemins allant du coin inférieur gauche (au Sud-Ouest) repéré par \((0, 0)\) vers le coin supérieur droit (au Nord-Est) repéré par \((n, m)\).

Un point repéré par la position \((n, m)\) a donc pour coordonnées \((n, m)\) dans un repère ayant pour origine le point situé en bas à gauche de la grille.

Les seuls mouvements autorisés sur la grille sont :

  • Aller au Nord (↑) d'une unité.
  • Aller à l'Est (→) d'une unité.

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

Ceux obtenus en venant du sud \((4, 2)\), il y en a 15.

Ceux obtenus en venant de l'Ouest \((3, 3)\), il y en a 20.

Écrire une fonction nb_chemins qui prend en paramètres deux entiers n et m. (n, m) est un tuple donnant une position sur la grille.
Cette fonction renvoie le nombre de chemins allant de \((0, 0)\) jusqu'à \((n, m)\).

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.
Exemples 
>>> nb_chemins(3, 3)
20
>>> nb_chemins(4, 2)
15
>>> nb_chemins(4, 3)
35

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

Compléter le code :

###(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 : 10/10
.9875.65038.128013oCèé{3IpRa[7g?q 6PU!/êD09ç]eymit=×ldE.k2v:L1b,Nù+}cu)hx85nà4_Of;rSw(-s050M0E0I0m0H0L0{0s0#0L0m0{0{0J010I0H0k010406050{0$0G0G0m0?0F040@0d0L0$1c0d0,0s020m0G0k0=0s0l0E1m0?0r0$0E0{050x1j1l1n1p1h0k04051U1N1X0x1U1h0M0H0R1416181a0(0H0p0(0L1/0(0I1f050 0V0L0E1*1719011.1:1=1:0I1{1}1_0I0?1V0I0(141s0{0k0m0,1a0Q011 1,010;110E0,1A0E1_2i2k2p212s1}2v0G2x040c0s0u0?0d0k0d0{0H1v1x0}2g0?0?0E0#2S1N2z0,1V0x2e2(2b2d2c1`0M2B1a1=0,2u2P1_1%1)15202=0H2@0,0d2{1_0k2X1V2$2(391i2j1x2}2q320?1m0L1f0s0U2#3d1g3c2A3f213h3j3l0Q3o2k3q2$2;013v0m3k040s0i3z2%1h3C3t1a3F3H0s0.3L3B3d3D3R3l0+3V3N3X3P3E0d3i3G3l0t3$3r3e1+3u3+3w3I0o3:3O3?3Q3^3-3I0*3|3(3~3*3,3S0B443s463Z040U0A4b3=2~473_0U3n1O3p1Y371N2{2+0M2d2:3)0#332H0|1(1V360E384q4p3A054A0}4I4c4k0,1f0,0V0/0#0(1G300{0/2G0G3V0s3;3D0d1f0J4)4+3)4U1f1%2Z3V4;461e040_0%3$063%4Q2q0P4@0E0;4`3}4k0^3l5a454R0;4T4V4X4Z0,1M4K2%4{4k4}0_5f543u4T5v4j2q4}0W4:5b3g1f4(5p4P5A214}0%0S3$0s5R4*5F2156040H595J5T5g5B1f5u5J5r5G040,5z3D5C5E5$5x045I3b5U1a5N5=5w1a0d5d5-0d0I5~5L606230663Y5j4W4Y0G4!4$1G5/3)4}5P5J065S6q5#5 015W5Y6b6l5(6k4d5y5!5+214-040J4/6D5{016g1f4h5*6L5}6K5?681f3+6x4|6z6Q6U3E5H6Y4k6G6I6)2q6N046P5`6$5N6n396p6r6{6E3Q1f2X1j0L0 656T6t6+6-216/4o6_6{5R6}6u1f0E120E6A5s1f6^3p6`7d5S7f4S04700$720m74396s670177757D7u4U6e5m5o6=6t5t7l5,5.7G4,1f0`781a7a7Q5M1f5D7T4=6(6#7O1f507(466G0Z7X6%5-5k6f4!7!5|6!7N7H6C7 5:7$7?7u5_3p7C7U047W7/4k7Z7+7D6S7c7d7t6d5l6g5n6i874L6R1f0n5)827)5-7|015;8d5,8r5q8t040%0D7?7F7B8l7v1L7x735Q7s6L5W2X0I0$0?7S8N6L7I7_7L8q8A4}8v8A7I8,848D5@8F5K838I8K6o1N4N4H4r900x4u1N0I4w952.2)0m1|924u1T8_3)2X0G0/0;0m0P0E0/0(0i1f1F1H1J1L0s7o4L1!3q1U0v2@0s0m0M0m0k730H1w0s1%2X2Z1~0}13304^7z9L5n9N1~0L000g320,0#0g0O1Y3q0(0U0s0H0M1a4A1B1}2G0,0I0{1f0e0d9_0g9{9}050m3D4Y9G0E0?2?560s0(2X0;1a039^0k9`2u9}2o1c0I1}1a0uab1m310I0sad1f0a0b1N0m2(9/9B049D147`1x2O8Z9F0L1}0?9Z893)1n2R0(1m0I0E0)1f090_0_0A0W0s0A0%097.7B0-aW46aY2ea#a%a)a+0.a.0ia;a?880k0E1u0s0y2b9R0g0#0?2R0s2jaU0$9E4X109E2U0#1n0m2Z0f702g1B2P0g9R1~0.4*8 04000N008~4B3I0~3JbEbL000XbJ0xbF9,9A9f0u1n0sa%1Gam0Ea.4MbL010N0N0Xb/b:01bK4O9Nbebgaza63D0p251@0V0da(afah1a0H1m0p1LbUaN0/0U0*0O0{0R0p2o9H0 0`0I0Fb7c7c92x9N7z0m0`0^9=2e1a0m1u4-cvcn4Y1?0IcCcEclcw0`9S0#0`2O2Q2S1ac227a11_c80paRcK012o0{0?0#cs0mca0{cc5mcecgcick0s0x2(aG9-9f0j0L0s0F9F9F1u2kazbqaN13aPaU3GaTaV7fa{a!7za~04a*a,a.a:a=4)a^dib{dka$a(dnb0b2b44)9vaVbn309wbqbsbubwalbzdJbCbP4ObHbTbFb#az0idS4HbRdVbLbW1#1W04a01laoaA9wala$aU0qc 057x3q1=04d1d3d5dvaZa}dza*0.0ZdZ0J0s0ods5!br0?bt0Ibv1LbWd}1hd}d d4a7e2a|dle50_0.ed7B4X0d0H0)bi2P2Q9cdc1n6gd:130obi160#9wddeObtabeLd!bGbIb@4Hel0Hd|e%0N5n0$2Rb)eWb+dTbSe!3I4G0,ayeWdZameU13700 9|1La.0{2k130m0ReBaU1}aMeB0)a.2Uax0Hej0sbl0H9ve$3q0xd{9f0T1~320G0V2XdGdbeEaQdfeV2Uesdxdmdoa-a/dD5!du6Ldje4a ewdCey881LazfcfwfybB0s9l0C1w13daeB2QaUbDe}eQeI3i0Hebd)aJ0z1~fifk0p9%0geg1}a.f!a1f$fA7LfCdeaSfF1~fHfSdAdpfMfW3A0sfP6$fReufT0,a.0GfN7BfYd:0sf#fz2Uf)f+fAf.0HaUghgsdA0,gm2%eTf?bieJf_gLdya 0,0Z0GgP04f{9fe*2g8Zf,f~7z0(a39W9v0{a.9Mb7b9f9gJ0sdFeQgBg8fzgz6nd*2{3DgrgXdn0n090V30a10h0,0!hhg!0!0sea090M0;eg0#0h0_gZgw0whj0,0w0Ghy098|9ed+0:0Y9xd_fs05d}gWfJhv0whn3m0K0Q0K0i0K090#0M640{0Khv0`0U0%0KgOb59zemhNe%hPevhChT0UhVhXhZh#h%h)0Gh+h-g#h:5q0xh=hOfQdwgidohw0%hSeah|hWhYh!h$9}h)hwi4iqg!gx4Jh=fr0LaJbZaUb$9_b)hLizenh@ice3gMe6iihUil0Kexi72(iaiJgqidiM0_0iiOikhXg$1NiV9ga`iYhadoe7b3i$h}hY0.0K0+0K0t0KeciTi*e%1hiy3qh7aXi.fJhchefw0h0.hji;hmhohqhs0hi%i^i`i|i~hjjmiR091J9G0s0K0sju0$jwjmjhjzjjbt0hi{i}0ojri@jEhphrjHi{h!2keQ0L0h0t0!jqjlh jU7i0hil0!jE0i0+hE4t4Ej30}0 110{04.