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

.339.128013sô3_8èufvIy n7aêS1me(P24:Kjtwi]D[h*)6o;bcdUgM/0lqAp.rL-,=+k95Rxé050R0v0D0q0F0X0c0n0Q0X0q0c0c0*010D0F0!010406050c0i0u0u0q0$0m040s0N0X0i150N0o0n020q0u0!0O0n0/0v1f0$0Y0i0v0c050V1c1e1g1i1a0!041G1N051Q0V1Q1S1N1a0R0F0k0}0 11130J0F0T0J0X1*0J0D18050^0P0X0v1#1012011)1+1-1+0D1?1^1;0D0P0N0R1i1=0$1O0D0J0}1l0c0!0q0o130y011`1%010j0`0v0o1t0v1;2i2k2p1|2s1^2v0u2x040b0n0x0$0N0!0N0c0F1o1q0?2g0$0$0v0Q2S1G2z0o1O0V2e2(0D2c2b2d0R2B131-0o2u2P1;1Y1!0~1{2=0F2@0o281Z1;0!2X1O2$2(391b2j1q2}2q320$1f0X180n0t2#3d193c2A3f1|3h3j3l0y3o2k3q2$2;013v0q3k040n0e3z2%1a3C3t133F3H0n0z3L3B3d3D3R3l0.3V3N3X3P3E0N3i3G3l0M3$3r3e1$3u3+3w3I0p3:3O3?3Q3^3-3I0g3|3(3~3*3,3S0-443s463Z040t0W4b3=2~473_0t3n1H3p3%4c4k4e0t3y4p3A4r4j3g403H0t3K4x3M3;3Y4C180t3U4G3W4s4B484L3#4O4z4J4S4f3/4V4I3)4u3{4#3}4t4K4f434*454,4Y0t4a4:4Q3@4Y0y4h4O1P371G2{2+0R2/3D0Q282H0=1Z1O360v383p3V05580?5g4`130,0o180j2M0u5i4+2q0E3l5v4;3g5q041f2e5A5n015y3I5H4A1|5p180F1u3+0D3V0n4$4d180c0Y0$5U4V4W3)0,180?0j5M3D5K5W4 5w3u0j180o0P0f0Q0J1z300c0f2u150v0$1F5?5B1|17040w5/4%5`5|202@683b5@136c0)5V5X4t6h5}1l1p6k6f466c0L0A3$0n6F5W6n3E5Z0q1n6l3p6H6a130N180*6r6I6c0I0G6E6G6s3g180H0B6V6Q016S046U4O6P5I5{5Q0o5%6m6,6c6e696?5Z5#6`5h6W186~6{70045{0f6j1E6+5I6.0K7f5N3Q6u7d6N3A6=7k6-180+7j3Y6u580X6x7e6;6$1|7h7v6g7a5|7y7A7o2%7D6o180L0L6!6F7O015+040j3+7G5Y041Y7#4k0N5K307)3g0P180$2k0T0v6z4k6}7_6%7I7c1*6y6 7r6B6D4V6G877q3D7X7Z0$7.3u5,0C8e6R7,0o8i3E7:047=0o7@7|6b768t7l7~7K0o8178837Q853906888I895*5r7!7C6I5D0R0,8m7+6^8m6@8p7?7^823D7{8#3)0u0F4L8w016p8W6(6*8O6,6.7u8?5I8*8,8(6A8E7T8J8I7V7X0F5.8`7r8Q0F8T187i987w7%9b9f3)8^8:7%8h9j467F9p6t9n9c6/6:398K7$8R9v9e9y7V8Q8S8~7`188F4q929N6#8P6K6M8-6.0#8-5D0q0!0!2u0R8-6}77746,9a9%186q9s7}0R9o8C8$7Q7S5(879F18581u0D8!9E6I6.9x6O7V6X0I8-8|044~a36,8b8Naf799?a7a48k8W8o8q8s9I2q8%9@7H7b8z8B9*5I6B6Z9:5O8M8daF8x9iaj7r8U047-aJ8n7;8Z9-6d9W7m807Baw8 040LaE8G9|9Q049 0!a1aVaaat1|acaeaB8D040Ga=a#4ka^aVa)am8@6T8mac4oa*9PagaH9maLb47gaoaR8Xara2a`9^aWa?8x7b7naV6C91a+bc7Yaibg9918al7p7VaOaQaM3YaqaUbq8.8vbN5Day6w8Aa!bn3)84bw8J94bdbj5,bf3Aa89.9m9=8TbibJ7H0c6L0D7M5ma{9L4y9O936I9597b;a$9)b*a,7(aR6.020X0D0Oa6bFa,b)7N75a%b/182k9$aRavbW9AbE2%9z7*18cbcdcfcv9}04cub`bobv86b~92cDa.a:bN6XaXaPb2a~cs9tcFb+a|9v0+cB5La,cNbmc66|18cUc+79cic%b5040(b-c;cYa}cRcFcw2q6.c^b%9ucP18b34y8Hbb5I7X2X0D0i0$8ld3c)a;cRbsaZb_c 7E18d2c3b08+4fcTdl7JbTaAcgc?dsbB3Db8b23:0V5k5f50dM0V531G0D55dR2-2)27292+0q1@dO531McG3)2X0u0f0j0q0,0v0f0J0e181y1A1C1E0nb|7N1T3q2{3D0q0R0u1p2R0F1p0n156c1Me3e5e72S0(150D24040Z0cde0Q1_0td}2K0$0;0(0Q3G0Q0i1^aI1W1R040x0Ndf0n9Y2O5$660n0i1q9!0i0n0R000v0j2sez0Q2R0;0)0neaeT5%eFeC3q1-a-eAeCeP360;3Gd!1^2G6_0n1^ebe|0v6L0n0y0HeVd|ew1ccc0qb^0n2OeKf10!0F2Xf90|ez0|0w0z0te)0z0y0L9/e;1ae;0QewePf17Z0o2Ze91q1C0F0n2@0nd.2R0nd{f0fl1_0@0n2X0o0k0N0mfE0qfY0;2O0o0c0v9V0Vfz1Ge/1adP5c1X1Z3D1~1,1.1:d)462D2u2w182J0sfC160D2K0m2e1p5i5eb`3a5hdLg24k5P7Y5t8-5;9W5D5F0Jgs5zbNgp5ReN73dC795!5$3$5)467X5-gy5LbQ5_045e5}e?0XaVc5cj9+aY0TdBgZaCb,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.iu0*h4cDidix9rix9GaVi5d9iD88cDg^b^9T18f:h}8xeM9#gXh g!9haV9/i!8ghKgJh0bCa-0Na0h!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.4qgKlul2cOkZjad3gTez0XeBgWj?jd04fsi|j(18fvkR5(i8gNbNgtgQ7x5 8*f-636_0F66kBllj@9gj_lNg+hIjviAk*kGkm8p0@lr9mlvc/a{lei`l.iudElt2qizlcjXkL7xdAkgk~liixm8kWj#jM1GgmdN2(d%5b2|46e4e60oe8eaec18ee3)muehfJej2Remeoeq1_0yeu0S151-f.0$f0f)0c0m0u0;2,l(1P3q1NeIeKeRfg2M1@0h2G0n2Q8*0 fV6H2,1p0T040q0k2Yf01_320u0Pfm2U7n0n0;0T3G1_f5n2n41_2Uaza!m_8r04e)0`fgeJ2W0_gc0r2,1_m*eTfg1m0|eYe!0qereV001n0`0FmRmTm:mWmY0$l(eVeU23f4eUf7e)fX2UfOep0N0Qd:0$dKgVeP1CnHn#0ve@0ne6e80;f:eF1N0%1_0Q0aeK0ReUdLf90kl(e 3G3+68eFe23)f~201/2y6,g42F2Hg8gaa/gdgfls7Ngi3;gkb*mnl1lAkta5hy7 hndobGg{jBjuhulx7}l~jnc?l0kC0Im18{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:lRkwcn0ocpixp|k_p,p k#q1j3lka{pCi6kFi8kIj-9vm5pT9gp(oBcy0TcAjjqoh=i$p@i7p9l3pbmbk=pvk@c}phlBc#l}lzpNm0pPqyiRkqk|oUqfqTp%qgbojMk+i80v0{qQbol@k+jO9~qPqFmj5DqVllmaq@bDqLqtivqek-q=jRqKm4qzjWqX9gpQp.drlbqIlm4qmm592(ouf_0k3qrme1f|mCegmw2Seb16mA1Refmvmx0omGel2HmJ0inF0eeu0Ul(0i0:m+exlFlHfEd|mZ7?1^obm$040l0X0n0v0:nKa1fnn?mY0J590|0!nAr(eZ0Fe#d|fhmS0T0;0o0;2XmSrYebnQr?0@r=ge0J0q0T3+r`o70cn`r!mOnJnL0 m:2,rIdefm1g272X0cer6_ng001ge%3Jr(eps60hnBr_r{e)1fnK0nno0meLeQfOmXgf2Um;s8sPsz3i0;1Y0_fm0A0n27rIeDm:o1n;rP0Q0d0D0;0ce)rSe@s41_m_nK0Fm.0ve)0ks296l(mSn.no1Egc0Po7r(l%66sjf{ms4kofg0oi5Iokg62I0ng9s7gc0xsbgg4 ou3b4 oyi`p;h3kU6Y4ipFo!o b(pIappMjHqGm3lcqiloc70F4wlBr17HqspoiZtQi{pZpmr7q4k5tT8YijlJk;oKkgg:q.k,t*0Ct%q t)ctiIljp@iW0,u4t,oIt.1Yudqq9khxljuiqjklj3iXu5t^2MeRq7rfo,7$hftVq|7%ucj0pZu1gL5Qp`poq9iWt$c!h=unmfiUb-9HlBhFp+5,uVrfhLoB5KkTg|kVpx9Au!ue0402qv0OlOadbuu0j~tIkAi.04i:uCi?q6i^cRt+p}hip*uju7iAu$pldKrjmo52f`virnf^0?0^0`0c04.

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

.128013s3o_8;bcdufvg/0lyq n7apS.r1-me,(P2=4:+Kjtwki9]D[5h*)6050j0E0P0w0S0q0b0t0i0q0w0b0b0J010P0S0x010406050b0k0D0D0w0A0r040y0d0q0k0_0d0u050o101214160~0x041f1m051p0o1p1r1m0~0j0S0m0.0:0=0@0Y0S0n0Y0q1F0Y0P0|050)0h0q0E1A0;0?011E1G1I1G0P1O1Q1M0P0h0d0j161N0A1n0P0Y0.190b0x0w0u0@0I011S1C010l0+0E0u0w0D0E1M1@1_1~1U211Q24260|0a0t0H0A0d0x0d0b0S1c0u0t0%1=0A0A0E0i2r1f290u1n0o1:2E0P1.1-1/0j2b0@1I0u232o1M1x1z0/1T2O0S2Q0u1*1y1M0x2x1n2C2E2,0 1^2s2W1 2#0A130q0|0t0B2B2:0}2/2a2=1U2@2_2{0I2~1_302C2N01350w2`040t0c392D0~3c330@3f3h0t0K3l3b2:3d3r2{0X3v3n3x3p3e0d2^3g2{0#3C312;1B343H363i0v3M3o3P3q3R3J3i0f3V3E3X3G3I3s0T3%323)3z040B0p3.3O2X3*3S0B2}1g2 3D3/3`3;0B383 3a413_2?3Z3h0B3k473m3N3y4c0|0B3u4g3w424b3+4l3B4o494j4s3=3L4v4i3F443U4B3W434k3=3$4G3(4I4y0B3-4M4q3Q4y0I3@4o1o2*1f2U2H0j2L3d0i1*271n4$1q4!2.4Y4+0%2+4N1 0R0u0|0l2l0D3v4C3)0Q2{524H2?4}04131:574`1U553i5e4T0@4|0|0S0D2n0A0P3v0t53430|0b0s5r3C4w3F0R0|0%0l5j4a5g564Y58340l0|0u0h0e0i0Y0E0D2Z0b0e230_0E0A0b5I3d0{040G5*4D5Q5S1Y2Q5)5M5f0@5,0F5t5v2?5;5T191d5@5/3)5,0!0L3C0t6c5u5N3q5x0w1b5^2,6e5`010d0|0J5~6f015,0W0U6b6d5 340|0V0N6s6n6p046r4o6m5k3e0h5n0u5s5_6M5,5.6S5J6g045y5A6W5+0|6V2.6t5a5R0e5?0E6k2 6L6X6o0|0Z6F6M6,5=1F656K6A0@6H0M6{6@6}620q646:763d6H6`716+614+7a0u706*6n680!6y6c72015E040l3H7d5:041x7A3)0d5h2Z7E436O040A1_0n0E663`6U7R60046-6/6;3a7u686a4v6d7)6?3d7w7y0A7J7V0j0O7:1U7G6P7@3q7L7N0u7P7U1U7T6$7B6-7k7b7Z2D7#0|697s7*7)7u7-7z7h6n5a0j0R7{6o7H1e8k6|7}7O7Q84676(810@5X4l8B6u0|5}8t776C6E8J7e0|758N3F8D3=8F7$8e8f8f8h5n5H8R3:5F0S8p7f8p8m8*8%3`748-5F7?8:1 8,8_6B7C8^6l7u6H0J6J907i7C8o8|736_8?978V0|7%2,068Y9j7*7u5a0b6i0P894_6M6H0z8F5a0w0x0x230j9e5-6)2 9m8)9D8I958l8@9D0!7r4v9i6z964+5p0P8x9L9t6q8p6v0W8F8T4X9Z6@8i7/993e0|8 6=918r8-8v7 9Y9G6t837o6|7j637m7c8y7S8c6x9:9.9c8/9,7e9_9:5R0|7~80a71 a09~9M7W6~0n7naq6Ta98e9H049V0x9X9D9(an1U9*9D0UaGa16@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|020q0P0g94b8araeaw6@68a*0|1_9C9:apbcar7=8+bRbTbV9cbu9sb#8cbE3mbGbGaAaCaEbr0|aMb!3ya)c304aLa?b2aKb:040MbWbz9U0d9Wbb8abd04c5b-a204bZcj6G0|0Cbpcvco7paScrcCctb^bw8;cybtce9Ra#6n7w2x0P0k0A8sbP8}c1cnb_a;cFc#85atavcw9!04cz9:aYaKc%aA86a4c+bv91cLc:0S8Ec9aT401f4@0E2E2)d64#1y4%2H2J2F1)1+2H0w1Pd90o4$0~dm0(0*0,04.