Suite de Fibonacci en récursif (2)

Source : Wikimedia Commons, domaine public, A portfolio of portraits of eminent mathematicians, 1905.

La suite dite "suite de Fibonacci" est une suite d'entiers qui commence par 0 et 1. Chacun des autres termes est la somme des deux précédents : ainsi les termes suivants sont 1 (car 0 + 1 = 1), 2 (car 1 + 1 = 2), puis 3 (car 1 + 2 = 3) et ainsi de suite. Les premiers termes sont donc : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

On dit que le terme d’indice 0 est \(u_0=0\), celui d’indice 1 est \(u_1=1\), celui d’indice 2 est \(u_2=1\) … celui d’indice 7 est \(u_7=13\) etc.

Compléter la fonction fibonacciqui prend en paramètre un entier n et renvoie le terme d'indice n de la suite de Fibonacci.

La fonction récursive naïve présentée dans l'exercice Suite de Fibonacci en récursif (1) devient très lente à parir de n = 35 environ, car les mêmes calculs sont répétés de très nombreuses fois.

Pour éviter cela, on peut stocker les valeurs déjà calculées dans une liste python. On applique ici une approche descendante de la programmation dynamique.

Version vide Version à compléter

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

.128013s3_8ufvy n7aïS1me(P24C:Vtwi]D[hE)6Oo;bcdg?/T0lqABp.r-,=+zk%95Rxé050O0r0z0m0B0U0b0j0N0U0m0b0b0%010z0B0Y010406050b0f0q0q0m0!0i040o0K0U0f140K0k0j020m0q0Y0L0j0.0r1e0!0V0f0r0b050R1b1d1f1h190Y041F1M051P0R1P1R1M190O0B0h0|0~10120F0B0P0F0U1)0F0z17050@0M0U0r1!0 11011(1*1,1*0z1=1@1:0z0M0K0O1h1;0!1N0z0F0|1k0b0Y0m0k120u011_1$010g0_0r0k1s0r1:2h2j2o1{2r1@2u0q2w040a0j0t0!0K0Y0K0b0B1n1p0=2f0!0!0r0N2R1F2y0k1N0R2d2%0z2b2a2c0O2A121,0k2t2O1:1X1Z0}1`2;0B2?0k271Y1:0Y2W1N2#2%381a2i1p2|2p310!1e0U170p2!3c183b2z3e1{3g3i170u3m2j3o2#2:013t0m3j040c3x2$193A3r123D3F0v3I3z3c3B3O170-3R3K3T3M3C0K3h3E170I3Y3p3d1#3s3%3u040l3R1O361F2`2*0O2.3B0N272G0;1Y1N350r373n3^410=493q3/3N170h3E0r0f0!1E1G3n0j3-3B0K170%3R4r3L4g0116040E3^4z2}010q0B170T4F3!4A4C0$4x4s3#4J3k4N4f4H4C0C3Y3Z4Y2p0*170=0g4X3.4H0A174r4p3y4T4A0k0g172r262u0N0N0B4.3B4C0s543#0k170k584P170H0x3Y0j5j4y4O4H4*040B4-4@2$5l4(3s5b4S4G2p4u04020P0z0L5y5m3f0M172D5d4Z17575s4e4/3f4i4k4m4o3a5z1{4C0H5H5v125B0#5(5T1{4V043l5R4_5O045h5R065k5}5u5.4h044~0d5c5R5 4t4v5-3U4}0B4 0m51535?5!12565N5U046538673#5+6a4U4K5;6m5#5f6u4A5B0(6B4H5a626d1o6f526y6k5P6N3C5x665@5A175,6T6j4I6w3w6i5I6z045%666r4A0N0p17030j0W0Y0Y0r0U0j0!0:0N5X5q5i5~5j6U5w044j1@5X6Q5B0Z6Q6H0m6^2t0O6Q6l6%5)6R6I0M647k6A5{5}75125o2W0z4m6p4q7w7o784l4n7s4D7e6S5Z6(6O044#5{1F4c483_7V0R3|1F0z3~7!2,2(26282*0m1?7X3|1L5S3B2W0q0d0g0m0*0r0d0F0c171x1z1B1D0j5`3a1S3o1P0m0j0F2W0g1%210Y0b0x0R0R0A8o0Z2W6 4n0B1o0h0B1b3E0B0)0r0!0Z410q0R0Q0g0f0k2Y8u0k0d4,2 2Q8N0%7G5X0+0u0T0+0c0D8X8Z0-0X8Z0u0w8%0p0+0-8$0T0W0+8?4,8%4~6K6g8X0e0k8X0,8!8@8?8%978Y8%5q8%91990c0G8%2D8 8V4n928%0#8.948^8@999t8+9v989v639d8Z8#8{6J50528 9A9o8Y8/0u939t0X9D6e8~0u909n8%0u9m969u9x9#9u9k0b0Z7g6_0k0O8 9z9Y9s9w9u7z7B8%9(8:0X918;1r1t0L8J8L2R0d0N3E0U0%8|9F0B8 0I922n0@0!0P0?120d1?2j5o0y8x0f8z0b0m2R0j2N4m0j0U009+6`0j2Tab6L0B0s0I0Hay0KaA0N0?0z1^0h8C2P1o0j0maV0N0j0q0:0q0K0nav2Z0R0m2%1V1Q040J3d1o0b0@aT0j0M0B2t0j84aB85310q0M2W0f0/0|3E6 0`6|0r0O1o0O2j0z0{1o0z0j0:0z0:bq8wbs9)1O8aa@1p8c0B520j1m0_8xbt8K1^9+2L0N0FbL7h0U0:1^010S2M0#0D0K0A5aby197Y0?0^0`04.

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

.128013s3_8ufvy n7aïS1me(P24C:Vtwi]D[hE)6Oo;bcdg?/T0lqABp.r-,=+zk%95Rxé050O0r0z0m0B0U0b0j0N0U0m0b0b0%010z0B0Y010406050b0f0q0q0m0!0i040o0K0U0f140K0k0j020m0q0Y0L0j0.0r1e0!0V0f0r0b050R1b1d1f1h190Y041F1M051P0R1P1R1M190O0B0h0|0~10120F0B0P0F0U1)0F0z17050@0M0U0r1!0 11011(1*1,1*0z1=1@1:0z0M0K0O1h1;0!1N0z0F0|1k0b0Y0m0k120u011_1$010g0_0r0k1s0r1:2h2j2o1{2r1@2u0q2w040a0j0t0!0K0Y0K0b0B1n1p0=2f0!0!0r0N2R1F2y0k1N0R2d2%0z2b2a2c0O2A121,0k2t2O1:1X1Z0}1`2;0B2?0k271Y1:0Y2W1N2#2%381a2i1p2|2p310!1e0U170p2!3c183b2z3e1{3g3i170u3m2j3o2#2:013t0m3j040c3x2$193A3r123D3F0v3I3z3c3B3O170-3R3K3T3M3C0K3h3E170I3Y3p3d1#3s3%3u040l3R1O361F2`2*0O2.3B0N272G0;1Y1N350r373n3^410=493q3/3N170h3E0r0f0!1E1G3n0j3-3B0K170%3R4r3L4g0116040E3^4z2}010q0B170T4F3!4A4C0$4x4s3#4J3k4N4f4H4C0C3Y3Z4Y2p0*170=0g4X3.4H0A174r4p3y4T4A0k0g172r262u0N0N0B4.3B4C0s543#0k170k584P170H0x3Y0j5j4y4O4H4*040B4-4@2$5l4(3s5b4S4G2p4u04020P0z0L5y5m3f0M172D5d4Z17575s4e4/3f4i4k4m4o3a5z1{4C0H5H5v125B0#5(5T1{4V043l5R4_5O045h5R065k5}5u5.4h044~0d5c5R5 4t4v5-3U4}0B4 0m51535?5!12565N5U046538673#5+6a4U4K5;6m5#5f6u4A5B0(6B4H5a626d1o6f526y6k5P6N3C5x665@5A175,6T6j4I6w3w6i5I6z045%666r4A0N0p17030j0W0Y0Y0r0U0j0!0:0N5X5q5i5~5j6U5w044j1@5X6Q5B0Z6Q6H0m6^2t0O6Q6l6%5)6R6I0M647k6A5{5}75125o2W0z4m6p4q7w7o784l4n7s4D7e6S5Z6(6O044#5{1F4c483_7V0R3|1F0z3~7!2,2(26282*0m1?7X3|1L5S3B2W0q0d0g0m0*0r0d0F0c171x1z1B1D0j5`3a1S3o1P0m0j0F2W0g1%210Y0b0x0R0R0A8o0Z2W6 4n0B1o0h0B1b3E0B0)0r0!0Z410q0R0Q0g0f0k2Y8u0k0d4,2 2Q8N0%7G5X0+0u0T0+0c0D8X8Z0-0X8Z0u0w8%0p0+0-8$0T0W0+8?4,8%4~6K6g8X0e0k8X0,8!8@8?8%978Y8%5q8%91990c0G8%2D8 8V4n928%0#8.948^8@999t8+9v989v639d8Z8#8{6J50528 9A9o8Y8/0u939t0X9D6e8~0u909n8%0u9m969u9x9#9u9k0b0Z7g6_0k0O8 9z9Y9s9w9u7z7B8%9(8:0X918;1r1t0L8J8L2R0d0N3E0U0%8|9F0B8 0I922n0@0!0P0?120d1?2j5o0y8x0f8z0b0m2R0j2N4m0j0U009+6`0j2Tab6L0B0s0I0Hay0KaA0N0?0z1^0h8C2P1o0j0maV0N0j0q0:0q0K0nav2Z0R0m2%1V1Q040J3d1o0b0@aT0j0M0B2t0j84aB85310q0M2W0f0/0|3E6 0`6|0r0O1o0O2j0z0{1o0z0j0:0z0:bq8wbs9)1O8aa@1p8c0B520j1m0_8xbt8K1^9+2L0N0FbL7h0U0:1^010S2M0#0D0K0A5aby197Y0?0^0`04.