Suite de Fibonacci (3)

Les premiers termes de la suite de Fibonacci sont :

\[0\rightarrow1\rightarrow1\rightarrow2\rightarrow3\rightarrow5\rightarrow8\rightarrow13\rightarrow21\rightarrow34\rightarrow\cdots\]

Les deux premiers termes sont \(0\) et \(1\). À partir du troisième, un terme est la somme des deux précédents.

Il est possible de calculer les termes de cette suite par une fonction récursive. Cependant, étant donné que chaque appel nécessite \(2\) autres appels interdépendants, le calcul du rang \(n\) demande \(2^n\) appels. Une version récursive simple ne peut fonctionner que pour des valeurs de \(n\) faibles, inférieures à \(25\).

Pour pouvoir calculer des termes de rangs élevés, il faut éviter de calculer plusieurs fois le même terme. On va donc utiliser une liste fibonacci_mem pour stocker les termes déjà calculés, fibonacci_mem[n] stocke ainsi le résultat de fibonacci(n).

Écrire la fonction fibonacci qui prend en paramètre un entier positif ou nul n et renvoie le terme d'indice \(n\) de la suite de Fibonacci.

Exemples 
>>> fibonacci(0)
0
>>> fibonacci(3)
2
>>> fibonacci(7)
13
>>> fibonacci(8)
21
>>> fibonacci(9)
34

On a bien fibonacci(9) égal à fibonacci(7) + fibonacci(8)

Approche Top-Down

Dans cette version, on utilise une méthode récursive efficace : avant de calculer un terme, on vérifie qu'il n'a pas déjà été calculé.

On appellera fib_n le terme d'indice n.

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

.8217.128013;]+ xl6[yg/éSv)iucbtqf489w0oRe5P.sa_d=(C7h2,-3n:1kûmpr050M0F0v0K0r0h0J0f0t0h0K0J0J0N010v0r0$010406050J0s0#0#0K0%0k040o0D0h0s0{0D0W0f020K0#0$0c0f0E0F150%0w0s0F0J050m12141618100$041w1D051G0m1G1I1D100M0r0p0:0=0@0_0R0r0l0R0h1W0R0v0~050+0u0h0F1R0?0^011V1X1Z1X0v1)1+1%0v0u0D0M181(0%1E0v0R0:1b0J0$0K0W0_0S011-1T010x0-0F0W1j0F1%282a2f1/2i1+2l0#2n040b0f0H0%0D0$0D0J0r1e1g0)260%0%0F0t2I1w2p0W1E0m242U0v2221230M2r0_1Z0W2k2F1%1O1Q0;1.2(0r2*0W1~1P1%0$2N1E2S2U2 11291g2:2g2^0%150h0~0Y2R330 322q351/37390~0S3d2a3f2S2%013k0K3a040V3o2T103r3i0_3u3w0y3z3q333s3F0~0G3I3B3K3D3t0D383v0~0i3P3g341S3j3U3l040Q3Z3C3$3E3(3W040z3,3R3.3T3V3w0A3I1F2}1w2.2X0M2#3s0t1~2x0(1P1E2|0F2~3e3~470)4f3h3_0W0~2i1}2l0t0t0r0L2w0#3I0f3!3s0D0~0N4y4A3S0}040j3~3-2;010#0r0~0C4L3^4N4I0T4F4M2g4P3b4T4l4V0~0d3P063Q4(2g0Z0~0)0x4%3#4N0B0~4z1x4g4Z3j0x4o0r4q0K4s0r4^3s4I0O593S4n040W5d3_4I0q0X3P0f5o4z500_4;040r4@4~3p5q4U360~5h5x2T5z4/1/4C04020l0v0c4Y5A3j0u0~2u5i4)045c5E4k4_5B044p1f564t4v1p5V2g5k5P5H0_5J0U5;5#1/4#043c5Z4G5j0~5m5Z065p665G5`3E530u0L5D2 684B4D5_3L6b5)575.1/5b6o6a5g6j3S5@6u3_5|5~315r015:5Z6g6v0~0e6x4N5f5(4r4t6r6D0~5Y6B5Q6s6e3e6G3_6w6F604N5|3n5 6C6E2 65675o6%5$6N5*4u4w6Q5J0I6Q5f0K0$0$2k0M6Q6q6+6V3t6b6d750~0q4,666=1/5t2N0v0s0%6X5y7h6s6@575,4x775=6R4J6~5C7c044+641w4i4e3 7I0m421w0v447N2Z2V1}1 2X0K1*7K421C5!3s2N0#0L0x0K0Z0F0L0R0V0~1o1q1s1u0f63311J3f1D0P0*0f3v0l3U2H0R2w0f7238802K1O4P0W1t0%0f1+260!0v0f0M0s882C0l0%1j872k0f0v1p0$0/0X810p2O8i1,0J0v0D0t0Z0K0l1,0)0/0p3v0F7m0/2?8y380n1O0,2N0J0T8i0K261k1+0g2H0n8n1,0h0a828424870)0p0r2k8m2)0n8$0F6}7|107L0*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

.8217.128013;]+ xl6[yg/éSv)iucbtqf489w0oRe5P.sa_d=(C7h2,-3n:1kûmpr050M0F0v0K0r0h0J0f0t0h0K0J0J0N010v0r0$010406050J0s0#0#0K0%0k040o0D0h0s0{0D0W0f020K0#0$0c0f0E0F150%0w0s0F0J050m12141618100$041w1D051G0m1G1I1D100M0r0p0:0=0@0_0R0r0l0R0h1W0R0v0~050+0u0h0F1R0?0^011V1X1Z1X0v1)1+1%0v0u0D0M181(0%1E0v0R0:1b0J0$0K0W0_0S011-1T010x0-0F0W1j0F1%282a2f1/2i1+2l0#2n040b0f0H0%0D0$0D0J0r1e1g0)260%0%0F0t2I1w2p0W1E0m242U0v2221230M2r0_1Z0W2k2F1%1O1Q0;1.2(0r2*0W1~1P1%0$2N1E2S2U2 11291g2:2g2^0%150h0~0Y2R330 322q351/37390~0S3d2a3f2S2%013k0K3a040V3o2T103r3i0_3u3w0y3z3q333s3F0~0G3I3B3K3D3t0D383v0~0i3P3g341S3j3U3l040Q3Z3C3$3E3(3W040z3,3R3.3T3V3w0A3I1F2}1w2.2X0M2#3s0t1~2x0(1P1E2|0F2~3e3~470)4f3h3_0W0~2i1}2l0t0t0r0L2w0#3I0f3!3s0D0~0N4y4A3S0}040j3~3-2;010#0r0~0C4L3^4N4I0T4F4M2g4P3b4T4l4V0~0d3P063Q4(2g0Z0~0)0x4%3#4N0B0~4z1x4g4Z3j0x4o0r4q0K4s0r4^3s4I0O593S4n040W5d3_4I0q0X3P0f5o4z500_4;040r4@4~3p5q4U360~5h5x2T5z4/1/4C04020l0v0c4Y5A3j0u0~2u5i4)045c5E4k4_5B044p1f564t4v1p5V2g5k5P5H0_5J0U5;5#1/4#043c5Z4G5j0~5m5Z065p665G5`3E530u0L5D2 684B4D5_3L6b5)575.1/5b6o6a5g6j3S5@6u3_5|5~315r015:5Z6g6v0~0e6x4N5f5(4r4t6r6D0~5Y6B5Q6s6e3e6G3_6w6F604N5|3n5 6C6E2 65675o6%5$6N5*4u4w6Q5J0I6Q5f0K0$0$2k0M6Q6q6+6V3t6b6d750~0q4,666=1/5t2N0v0s0%6X5y7h6s6@575,4x775=6R4J6~5C7c044+641w4i4e3 7I0m421w0v447N2Z2V1}1 2X0K1*7K421C5!3s2N0#0L0x0K0Z0F0L0R0V0~1o1q1s1u0f63311J3f1D0P0*0f3v0l3U2H0R2w0f7238802K1O4P0W1t0%0f1+260!0v0f0M0s882C0l0%1j872k0f0v1p0$0/0X810p2O8i1,0J0v0D0t0Z0K0l1,0)0/0p3v0F7m0/2?8y380n1O0,2N0J0T8i0K261k1+0g2H0n8n1,0h0a828424870)0p0r2k8m2)0n8$0F6}7|107L0*0,0.04.
Approche Bottom-Up

Dans cette version, on utilise une méthode itérative : on calcule chaque terme, depuis le premier terme jusqu'au terme du rang demandé.

Tant que la longueur de cette liste est insuffisante, on ajoute un nouveau terme. i est la taille de la liste, qui augmente de 1 à chaque tour de boucle.

Par la suite, on appellera fib_i le terme d'indice i.

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

.8217.128013;]+ Ll6[yg/éSv)iucbtqf489w0oRe5P.sa_d=(C7h2,-3n:1kûmpr050M0F0v0K0r0h0J0f0t0h0K0J0J0N010v0r0$010406050J0s0#0#0K0%0k040o0D0h0s0{0D0W0f020K0#0$0c0f0E0F150%0w0s0F0J050m12141618100$041w1D051G0m1G1I1D100M0r0p0:0=0@0_0R0r0l0R0h1W0R0v0~050+0u0h0F1R0?0^011V1X1Z1X0v1)1+1%0v0u0D0M181(0%1E0v0R0:1b0J0$0K0W0_0S011-1T010x0-0F0W1j0F1%282a2f1/2i1+2l0#2n040b0f0H0%0D0$0D0J0r1e1g0)260%0%0F0t2I1w2p0W1E0m242U0v2221230M2r0_1Z0W2k2F1%1O1Q0;1.2(0r2*0W1~1P1%0$2N1E2S2U2 11291g2:2g2^0%150h0~0f0Y2R330 322q351/37393b0S3e2a3g2S2%013l0K3a040f0V3p2T103s3j0_3v3x0f0y3B3r333t3H3b0G3L3D3N3F3u0D383w3b0i3S3h341S3k3X3m3y0Q3$3E3)3G3+3Z3y0z3/3U3;3W3Y3I0A3`3i3|3P040Y0C3L1F2}1w2.2X0M2#3t0t1~2x0(1P1E2|0F2~3f484h0)4p422;3u0~2i1}2l0t0t0r0L2w0#3L0f3%3t0D0~0N4I4K3V0}040j483:4w0#0r0~471x4q4W2g4S0T4P4(1/4Y0~3d4$3q4Q3|4S0d3S063T4v2g0Z0~0)0x4V3{4w0B3b544~3k0x4y0r4A0K4C0r593(4w4S0O5j3O0~0W5o4R0~0q0X3S0f5y4J4-3G0~5i4=2T5A552g4M044O5F3y4@4w0W0u0~2u5s4^0~5n5N5P365d5f5h4F1p5V5l5u5x5z5!1/50040B1V1+4,5I3k5D5`5a0_5K020h0v0c5M2 5H5 4x045r5Z5B014S5w5N065z6k685k5#044z0L5E675:604N5~6n5|6p5e1f5g4D5)4H6d5{0_4S4U6H690W5}5N6m4L0~0U6x3t4/455+4)0~4`6Q6u015K0e6V3V6O6A5%6E4G6Z1/6K6?5C046s3f6R3V5K6U6%6e6X3o6M6y6J6#5.6l6~435$6C5(6=766S040I6_6a0K0$0$2k0M7m5m7m6.6q6|4?6e4S0q7a6l6(6.7y5G6(5K666}7F6P6t6e6*6,3|6X4;2 6j5/6e5=2N0v0s0%6c7P6I6a4z7f6;5*7i5t4T7v5q7t796i1w4s4o497~0m4c1w0v4e832Z2V1}1 2X0K1*804c1C4u77012N0#0L0x0K0Z0F0L0R0V0~1o1q1s1u0f6h311J3g1D0g0K0f0p160r8c1+0f7-4B7/0#0f7q380*0f2K0J0v0D0t8p0%8W2a0/0=0f0#0n0#0D0r2N0:5g0R1,1+0/0%0n12630K0v0/2?0v0F380n1O0,2N0J0I0f0g3X0/0)0/7o7q0.0f124C1u2G0x9g8_8G0x1f2P0r1f0T0f0-0f0W0a1u0v8W9w8S0?0f0u1u8:2J1,2N0t3w0t0s1+8%0t8y8I1+7%9b1F8D040P0F7q0W0M2a0v9A8M2|0D0l0%1j2w0f8!9V7q8(8I0W0+0l1,2K0$0=9Z0f2k8,8.8:2N9Aab1s0r0f0K0s0l2wa4a79J0J1f260!9Had1u299Z7l8C10810*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

.8217.128013;]+ Ll6[yg/éSv)iucbtqf489w0oRe5P.sa_d=(C7h2,-3n:1kûmpr050M0F0v0K0r0h0J0f0t0h0K0J0J0N010v0r0$010406050J0s0#0#0K0%0k040o0D0h0s0{0D0W0f020K0#0$0c0f0E0F150%0w0s0F0J050m12141618100$041w1D051G0m1G1I1D100M0r0p0:0=0@0_0R0r0l0R0h1W0R0v0~050+0u0h0F1R0?0^011V1X1Z1X0v1)1+1%0v0u0D0M181(0%1E0v0R0:1b0J0$0K0W0_0S011-1T010x0-0F0W1j0F1%282a2f1/2i1+2l0#2n040b0f0H0%0D0$0D0J0r1e1g0)260%0%0F0t2I1w2p0W1E0m242U0v2221230M2r0_1Z0W2k2F1%1O1Q0;1.2(0r2*0W1~1P1%0$2N1E2S2U2 11291g2:2g2^0%150h0~0f0Y2R330 322q351/37393b0S3e2a3g2S2%013l0K3a040f0V3p2T103s3j0_3v3x0f0y3B3r333t3H3b0G3L3D3N3F3u0D383w3b0i3S3h341S3k3X3m3y0Q3$3E3)3G3+3Z3y0z3/3U3;3W3Y3I0A3`3i3|3P040Y0C3L1F2}1w2.2X0M2#3t0t1~2x0(1P1E2|0F2~3f484h0)4p422;3u0~2i1}2l0t0t0r0L2w0#3L0f3%3t0D0~0N4I4K3V0}040j483:4w0#0r0~471x4q4W2g4S0T4P4(1/4Y0~3d4$3q4Q3|4S0d3S063T4v2g0Z0~0)0x4V3{4w0B3b544~3k0x4y0r4A0K4C0r593(4w4S0O5j3O0~0W5o4R0~0q0X3S0f5y4J4-3G0~5i4=2T5A552g4M044O5F3y4@4w0W0u0~2u5s4^0~5n5N5P365d5f5h4F1p5V5l5u5x5z5!1/50040B1V1+4,5I3k5D5`5a0_5K020h0v0c5M2 5H5 4x045r5Z5B014S5w5N065z6k685k5#044z0L5E675:604N5~6n5|6p5e1f5g4D5)4H6d5{0_4S4U6H690W5}5N6m4L0~0U6x3t4/455+4)0~4`6Q6u015K0e6V3V6O6A5%6E4G6Z1/6K6?5C046s3f6R3V5K6U6%6e6X3o6M6y6J6#5.6l6~435$6C5(6=766S040I6_6a0K0$0$2k0M7m5m7m6.6q6|4?6e4S0q7a6l6(6.7y5G6(5K666}7F6P6t6e6*6,3|6X4;2 6j5/6e5=2N0v0s0%6c7P6I6a4z7f6;5*7i5t4T7v5q7t796i1w4s4o497~0m4c1w0v4e832Z2V1}1 2X0K1*804c1C4u77012N0#0L0x0K0Z0F0L0R0V0~1o1q1s1u0f6h311J3g1D0g0K0f0p160r8c1+0f7-4B7/0#0f7q380*0f2K0J0v0D0t8p0%8W2a0/0=0f0#0n0#0D0r2N0:5g0R1,1+0/0%0n12630K0v0/2?0v0F380n1O0,2N0J0I0f0g3X0/0)0/7o7q0.0f124C1u2G0x9g8_8G0x1f2P0r1f0T0f0-0f0W0a1u0v8W9w8S0?0f0u1u8:2J1,2N0t3w0t0s1+8%0t8y8I1+7%9b1F8D040P0F7q0W0M2a0v9A8M2|0D0l0%1j2w0f8!9V7q8(8I0W0+0l1,2K0$0=9Z0f2k8,8.8:2N9Aab1s0r0f0K0s0l2wa4a79J0J1f260!9Had1u299Z7l8C10810*0,0.04.