Aller au contenu

Chemins à sauts entiers sur une grille⚓︎

  • On part du coin supérieur gauche d'une grille,
  • on ne fait que des sauts qui font progresser dans le secteur du coin opposé,
  • les sauts sont à aussi à distance entière.

On souhaite compter le nombre de tels chemins.

Un chemin à sauts entiers d'une grille de 8 lignes et 7 colonnes

⚠ On compte ici les nœuds de la grille et non ses cases. Il y a bien 8 lignes et colonnes. En partant d'un coin, ce chemin est composé des sauts suivants :

TODO Figure à venir

  • \(\overrightarrow{OA}\), 1 en bas ; de distance 1,
  • \(\overrightarrow{AB}\), 4 en bas et 3 à droite ; de distance 5,
  • \(\overrightarrow{BC}\), 3 à droite, de distance 3,
  • \(\overrightarrow{CD}\), 2 en bas, de distance 2.

Il s'agit d'un des \(160\,758\) chemins entiers possibles de \(O\) à \(D\).

Requête

Écrire une fonction nb_chemins_entiers

  • qui prend en paramètres :
    • nb_lignes : un entier strictement positif, le nombre de lignes de la grille,
    • nb_colonnes : un entier strictement positif, le nombre de colonnes de la grille,
  • qui renvoie un entier : le nombre de chemins à sauts entiers
    • pour aller du coin supérieur gauche au coin inférieur droit,
    • en ne réalisant que des sauts \(\overrightarrow{MN}\) :
      • \(d_i\) en bas,
      • \(d_j\) à droite,
      • de distance \(\sqrt{d_i^2+d_j^2}\) entière,
      • avec \(d_i, d_j \in \mathbb N\).

Dans les tests,

  • on garantit que nb_lignes < 42 et nb_colonnes < 43,
  • on utilisera la fonction une cinquantaine de fois au plus.
Exemple 
>>> nb_chemins_entiers(2, 2)
2
>>> nb_chemins_entiers(4, 5)
290
>>> nb_chemins_entiers(8, 7)
160758
>>> nb_chemins_entiers(21, 41)
403280419507196134012726226
Indices
Indice 1

Il faudrait générer tous les sauts possibles dans cette grille, donc tous les triangles rectangles à côtés entiers (di, dj, dk) avec 0 ≤ di ≤ nb_lignes, 0 ≤ dj ≤ nb_colonnes et di² + dj² égal à dk².

On pourra, par exemple, pour chaque (di, dj, dk) vérifier si ce triplet convient.

Cette méthode est peu performante, mais suffisante ici.

Indice 2

On pourra créer un tableau 2D qui compte le nombre de chemins, on le remplira de manière dynamique, ligne par ligne, par exemple.

###(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

.128013.339:LpM(40ed3; 1jo5_Aên)Kh]6,qc[yuôv8i2+DxmsU7=wlSIatf-9Rrg.*éPkbè/050k0j0Z0Y0K0V0Q0n0D0V0Y0Q0Q0T010Z0K0e010406050Q0G0P0P0Y0(0F040W0q0V0G150q0v0n020Y0P0e0m0n0%0j1f0(0C0G0j0Q050;1c1e1g1i1a0e041G1N051Q0;1Q1S1N1a0k0K0I0}0 11130y0K0)0y0V1*0y0Z18050^0/0V0j1#1012011)1+1-1+0Z1?1^1;0Z0/0q0k1i1=0(1O0Z0y0}1l0Q0e0Y0v130L011`1%010!0`0j0v1t0j1;2i2k2p1|2s1^2v0P2x040a0n0-0(0q0e0q0Q0K1o1q0?2g0(0(0j0D2S1G2z0v1O0;2e2(0Z2c2b2d0k2B131-0v2u2P1;1Y1!0~1{2=0K2@0v281Z1;0e2X1O2$2(391b2j1q2}2q320(1f0V180n0o2#3d193c2A3f1|3h3j3l0L3o2k3q2$2;013v0Y3k040n0l3z2%1a3C3t133F3H0n0h3L3B3d3D3R3l0r3V3N3X3P3E0q3i3G3l0A3$3r3e1$3u3+3w3I0S3:3O3?3Q3^3-3I0J3|3(3~3*3,3S0$443s463Z040o0i4b3=2~473_0o3n1H3p3%4c4k4e0o3y4p3A4r4j3g403H0o3K4x3M3;3Y4C180o3U4G3W4s4B484L3#4O4z4J4S4f3/4V4I3)4u3{4#3}4t4K4f434*454,4Y0o4a4:4Q3@4Y0L4h4O1P371G2{2+0k2/3D0D282H0=1Z1O360j383p3V05580?5g4`130.0v180!2M0P5i4+2q0U3l5v4;3g5q041f2e5A5n015y3I5H4A1|5p180K1u3+0Z3V0n4$4d180Q0C0(5U4V4W3)0.180?0!5M3D5K5W4 5w3u0!180v0/0s0D0y1z300Q0s2u150j0(1F5?5B1|17040g5/4%5`5|202@683b5@136c0B5V5X4t6h5}1l1p6k6f466c0w0c3$0n6F5W6n3E5Z0Y1n6l3p6H6a130q180T6r6I6c0E0z6E6G6s3g180N0x6V6Q016S046U4O6P5I5{5Q0v5%6m6,6c6e696?5Z5#6`5h6W186~6{70045{0s6j1E6+5I6.0+7f5N3Q6u7d6N3A6=7k6-180M7j3Y6u580V6x7e6;6$1|7h7v6g7a5|7y7A7o2%7D6o180w0w6!6F7O015+040!3+7G5Y041Y7#4k0q5K307)3g0/180(2k0)0j6z4k6}7_6%7I7c1*6y6 7r6B6D4V6G877q3D7X7Z0(7.3u5,0p8e6R7,0v8i3E7:047=0v7@7|6b768t7l7~7K0v8178837Q853906888I895*5r7!7C6I5D0k0.8m7+6^8m6@8p7?7^823D7{8#3)0P0K4L8w016p8W6(6*8O6,6.7u8?5I8*8,8(6A8E7T8J8I7V7X0K5.8`7r8Q0K8T187i987w7%9b9f3)8^8:7%8h9j467F9p6t9n9c6/6:398K7$8R9v9e9y7V8Q8S8~7`188F4q929N6#8P6K6M8-6.0*8-5D0Y0e0e2u0k8-6}77746,9a9%186q9s7}0k9o8C8$7Q7S5(879F18581u0Z8!9E6I6.9x6O7V6X0E8-8|044~a36,8b8Naf799?a7a48k8W8o8q8s9I2q8%9@7H7b8z8B9*5I6B6Z9:5O8M8daF8x9iaj7r8U047-aJ8n7;8Z9-6d9W7m807Baw8 040waE8G9|9Q049 0ea1aVaaat1|acaeaB8D040za=a#4ka^aVa)am8@6T8mac4oa*9PagaH9maLb47gaoaR8Xara2a`9^aWa?8x7b7naV6C91a+bc7Yaibg9918al7p7VaOaQaM3YaqaUbq8.8vbN5Day6w8Aa!bn3)84bw8J94bdbj5,bf3Aa89.9m9=8TbibJ7H0Q6L0Z7M5ma{9L4y9O936I9597b;a$9)b*a,7(aR6.020V0Z0ma6bFa,b)7N75a%b/182k9$aRavbW9AbE2%9z7*18cbcdcfcv9}04cub`bobv86b~92cDa.a:bN6XaXaPb2a~cs9tcFb+a|9v0McB5La,cNbmc66|18cUc+79cic%b5040#b-c;cYa}cRcFcw2q6.c^b%9ucP18b34y8Hbb5I7X2X0Z0G0(8ld3c)a;cRbsaZb_c 7E18d2c3b08+4fcTdl7JbTaAcgc?dsbB3Db8b23:0;5k5f50dM0;531G0Z55dR2-2)27292+0Y1@dO531McG3)2X0P0s0!0Y0.0j0s0y0l181y1A1C1E0nb|7N1T3q2{3D0Y0k0P1p2R0K1p0n156c1Me3e5e72S0#150Z24040t0Qde0D1_0od}2K0(0,0#0D3G0D0G1^aI1W1R040-0qdf0n9Y2O5$660n0G1q9!0G0n0k000j0!2sez0D2R0,0B0neaeT5%eFeC3q1-a-eAeCeP360,3Gd!1^2G6_0n1^ebe|0j6L0n0L0NeVd|ew1ccc0Yb^0n2OeKf10e0K2Xf90|ez0|0g0h0oe)0h0L0w9/e;1ae;0DewePf17Z0v2Ze91q1C0K0n2@0nd.2R0nd{f0fl1_0@0n2X0v0I0q0FfE0YfY0,2O0v0Q0j9V0;fz1Ge/1adP5c1X1Z3D1~1,1.1:d)462D2u2w182J0WfC160Z2K0F2e1p5i5eb`3a5hdLg24k5P7Y5t8-5;9W5D5F0ygs5zbNgp5ReN73dC795!5$3$5)467X5-gy5LbQ5_045e5}e?0VaVc5cj9+aY0)dBgZaCb,d3bS7zbUb_cYcIba7Ua,b?9Sc9b6cqc-d73Mbx796)9vc$dp3Q8o30gEg(a{gYgn7}gHh9hd8ubpa 7}dmg$bVgFaN9d9mhmg%c=7g7thsdzg-huh57s049DdFaxhz7Lbu9`g=hCahaIdt9;c;hCbHdhhQ3ubL8rc*habohccDhthoh#bX90cJb by8cb-c~bGb:hG4dhYashkhih%a,g,hJd5a%d~19cKb#bzhPh_9t9Bc9h^hpbKaThZgXabdvb9cVaug*hW8xh2g`048_ir01dHi3g;9McKda7rc1c_9CiHiuiwib9;h?a4hrd3b.iu0Th4cDidix9rix9GaVi5d9iD88cDg^b^9T18f:h}8xeM9#gXh g!9haV9/i!8ghKgJh0bCa-0qa0h!hvhq6/8ma9il18a_ig8Li99miO8@ifcC8Ph{j7cYi_79i1g.bug~j88ab$i~cSie8VbjjpikbQg#hug:jxi(hC5Ddji3c.h+46b1i3c|bNjVi;bOcZiTb7im91i8h;d3hSh@jEi!jGi3jsj3h)g/ckiBb}b!c0jAiM8fcEcmaPhVk1h6iih|ioh~dy6vhAh*hh7Pi4bZh/dbk0jg9Ac`cki}k76Jd4iYjmjyb=b@j`c,04i%i)g?by96jbbPj!9,iuczcebebuk4cokJhjkb8xiSiYcycckPd3cXj{kEkFj29gjQj!cQjIjCk/d6jSkhkuk(kCjxhT7tiVc(j5a/jqckk^cDj.iPc@iJk?a|l6a,jkhwlaiRk{g)j$8GjNi8dddfk6ko9tk.4qgKlul2cOkZjad3gTez0VeBgWj?jd04fsi|j(18fvkR5(i8gNbNgtgQ7x5 8*f-636_0K66kBllj@9gj_lNg+hIjviAk*kGkm8p0@lr9mlvc/a{lei`l.iudElt2qizlcjXkL7xdAkgk~liixm8kWj#jM1GgmdN2(d%5b2|46e4e60ve8eaec18ee3)muehfJej2Remeoeq1_0Leu0R151-f.0(f0f)0Q0F0P0,2,l(1P3q1NeIeKeRfg2M1@0:2G0n2Q8*0 fV6H2,1p0)040Y0I2Yf01_320P0/fm2U7n0n0,0)3G1_f5n2n41_2Uaza!m_8r04e)0`fgeJ2W0_gc0u2,1_m*eTfg1m0|eYe!0YereV001n0`0KmRmTm:mWmY0(l(eVeU23f4eUf7e)fX2UfOep0q0Dd:0(dKgVeP1CnHn#0je@0ne6e80,f:eF1N0d1_0D0beK0keUdLf90Il(e 3G3+68eFe23)f~201/2y6,g42F2Hg8gaa/gdgfls7Ngi3;gkb*mnl1lAkta5hy7 hndobGg{jBjuhulx7}l~jnc?l0kC0Em18{dvjfoPl_j,jBlgaNkxjOj=lcl,7Hl8c?iLm6a@j)iAk}j+bAo;aKk4bIktbkbMo+cR58oAl cHmll1j6dkjYoWdxpcjedIj%aRmi4yo_iao{kuo.bhj:o o*mjcrp67Hp4l4kCj|g iEjzjik%o}oskyh`k9pAl+cRpqj9o:oY7rpkjT9Jkjh.i*j pGjBc8lckspo8Qo$3DhU9mi,l*b{kkp!kHc2ktpwpWhR9vkOoRc:lRkwcn0vcpixp|k_p,p k#q1j3lka{pCi6kFi8kIj-9vm5pT9gp(oBcy0)cAjjqoh=i$p@i7p9l3pbmbk=pvk@c}phlBc#l}lzpNm0pPqyiRkqk|oUqfqTp%qgbojMk+i80j0{qQbol@k+jO9~qPqFmj5DqVllmaq@bDqLqtivqek-q=jRqKm4qzjWqX9gpQp.drlbqIlm4qmm592(ouf_0I3qrme1f|mCegmw2Seb16mA1Refmvmx0vmGel2HmJ0GnF0leu0fl(0G0Om+exlFlHfEd|mZ7?1^obm$040X0V0n0j0OnKa1fnn?mY0y590|0enAr(eZ0Ke#d|fhmS0)0,0v0,2XmSrYebnQr?0@r=ge0y0Y0)3+r`o70Qn`r!mOnJnL0 m:2,rIdefm1g272X0Qer6_ng001ge%3Jr(eps60:nBr_r{e)1fnK0nno0FeLeQfOmXgf2Um;s8sPsz3i0,1Y0_fm0c0n27rIeDm:o1n;rP0D0H0Z0,0Qe)rSe@s41_m_nK0Km.0je)0Is296l(mSn.no1Egc0/o7r(l%66sjf{ms4kofg0oi5Iokg62I0ng9s7gc0-sbgg4 ou3b4 oyi`p;h3kU6Y4ipFo!o b(pIappMjHqGm3lcqiloc70K4wlBr17HqspoiZtQi{pZpmr7q4k5tT8YijlJk;oKkgg:q.k,t*0pt%q t)ctiIljp@iW0.u4t,oIt.1Yudqq9khxljuiqjklj3iXu5t^2MeRq7rfo,7$hftVq|7%ucj0pZu1gL5Qp`poq9iWt$c!h=unmfiUb-9HlBhFp+5,uVrfhLoB5KkTg|kVpx9Au!ue0402qv0mlOadbuu0j~tIkAi.04i:uCi?q6i^cRt+p}hip*uju7iAu$pldKrjmo52f`virnf^0?0^0`0Q04.

###(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

.128013:pbv(40i2+Dedm3;s7= 1jo5w_lSnatf-)9Kh]6,qcrg.*[yPku8/050n0m0F0E0i0B0r0u0Q0B0E0r0r0t010F0i0c010406050r0Z0o0o0E0R0W040C0x0B0Z0_0x0D050#101214160~0c041f1m051p0#1p1r1m0~0n0i0e0.0:0=0@0L0i0S0L0B1F0L0F0|050)0d0B0m1A0;0?011E1G1I1G0F1O1Q1M0F0d0x0n161N0R1n0F0L0.190r0c0E0D0@0j011S1C010G0+0m0D0E0o0m1M1@1_1~1U211Q24260|0a0u0X0R0x0c0x0r0i1c0D0u0%1=0R0R0m0Q2r1f290D1n0#1:2E0F1.1-1/0n2b0@1I0D232o1M1x1z0/1T2O0i2Q0D1*1y1M0c2x1n2C2E2,0 1^2s2W1 2#0R130B0|0u0v2B2:0}2/2a2=1U2@2_2{0j2~1_302C2N01350E2`040u0p392D0~3c330@3f3h0u0g3l3b2:3d3r2{0y3v3n3x3p3e0x2^3g2{0N3C312;1B343H363i0s3M3o3P3q3R3J3i0!3V3E3X3G3I3s0J3%323)3z040v0h3.3O2X3*3S0v2}1g2 3D3/3`3;0v383 3a413_2?3Z3h0v3k473m3N3y4c0|0v3u4g3w424b3+4l3B4o494j4s3=3L4v4i3F443U4B3W434k3=3$4G3(4I4y0v3-4M4q3Q4y0j3@4o1o2*1f2U2H0n2L3d0Q1*271n4$1q4!2.4Y4+0%2+4N1 0Y0D0|0G2l0o3v4C3)0z2{524H2?4}04131:574`1U553i5e4T0@4|0|0i0o2n0R0F3v0u53430|0r0P5r3C4w3F0Y0|0%0G5j4a5g564Y58340G0|0D0d0A0Q0L0m0o2Z0r0A230_0m0R0r5I3d0{040f5*4D5Q5S1Y2Q5)5M5f0@5,0O5t5v2?5;5T191d5@5/3)5,0I0b3C0u6c5u5N3q5x0E1b5^2,6e5`010x0|0t5~6f015,0V0M6b6d5 340|0l0K6s6n6p046r4o6m5k3e0d5n0D5s5_6M5,5.6S5J6g045y5A6W5+0|6V2.6t5a5R0A5?0m6k2 6L6X6o0|0U6F6M6,5=1F656K6A0@6H0k6{6@6}620B646:763d6H6`716+614+7a0D706*6n680I6y6c72015E040G3H7d5:041x7A3)0x5h2Z7E436O040R1_0S0m663`6U7R60046-6/6;3a7u686a4v6d7)6?3d7w7y0R7J7V0n0w7:1U7G6P7@3q7L7N0D7P7U1U7T6$7B6-7k7b7Z2D7#0|697s7*7)7u7-7z7h6n5a0n0Y7{6o7H1e8k6|7}7O7Q84676(810@5X4l8B6u0|5}8t776C6E8J7e0|758N3F8D3=8F7$8e8f8f8h5n5H8R3:5F0i8p7f8p8m8*8%3`748-5F7?8:1 8,8_6B7C8^6l7u6H0t6J907i7C8o8|736_8?978V0|7%2,068Y9j7*7u5a0r6i0F894_6M6H0T8F5a0E0c0c230n9e5-6)2 9m8)9D8I958l8@9D0I7r4v9i6z964+5p0F8x9L9t6q8p6v0V8F8T4X9Z6@8i7/993e0|8 6=918r8-8v7 9Y9G6t837o6|7j637m7c8y7S8c6x9:9.9c8/9,7e9_9:5R0|7~80a71 a09~9M7W6~0S7naq6Ta98e9H049V0c9X9D9(an1U9*9D0MaGa16@aJaH5{0|aaaf3F928p8T3~9h8g6tacai5n8+ahaU3:9{amaN6%5-9w617Y9O9g409j8!7x8ja,5w049?3a7+aVa+9@6+a.9}7!9 8AaQ9;as7988a_8X8Ya}7.9c7Dbf5|bpb32Db57Fb7b4aA9o6j9Da`489kbma$8#9$bea:7Bbqb08`0|020B0F0q94b8araeaw6@68a*0|1_9C9:apbcar7=8+bRbTbV9cbu9sb#8cbE3mbGbGaAaCaEbr0|aMb!3ya)c304aLa?b2aKb:040kbWbz9U0x9Wbb8abd04c5b-a204bZcj6G0|0Hbpcvco7paScrcCctb^bw8;cybtce9Ra#6n7w2x0F0Z0R8sbP8}c1cnb_a;cFc#85atavcw9!04cz9:aYaKc%aA86a4c+bv91cLc:0i8Ec9aT401f4@0m2E2)d64#1y4%2H2J2F1)1+2H0E1Pd90#4$0~dm0(0*0,04.