Suite de Fibonacci (2)

Les premiers termes de la suite de Fibonacci sont :

\[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \cdots\]

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

Il existe une formule récursive efficace pour calculer deux nombres de Fibonacci consécutifs.

$F_0=0$, $F_1=1$ et pour $k>0$, on admet que :

\[\begin{cases} F_{2k-1} = F_{k}^{2} + F_{k-1}^{2}\\ F_{2k} = F_{k}^{2} + 2×F_{k}×F_{k-1}\\ F_{2k+1} = F_{2k} + F_{2k-1} \end{cases}\]

Écrire une fonction récursive fibonacci qui prend en paramètre un entier n strictement positif et renvoie le couple $(F_{n-1}, F_n)$

Méthode appliquée à n = 9

L'appel fibonacci(9) souhaite renvoyer $(F_8, F_9)$
$9$ est impair, on va demander $(F_7, F_8)$, on pourra en déduire $F_9$
On appelle fibonacci(8)
$8$ est pair, on va demander $(F_3, F_4)$
On appelle fibonacci(4)
$4$ est pair, on va demander $(F_1, F_2)$
On appelle fibonacci(2)
$2$ est pair, on va demander $(F_0, F_1)$
On appelle fibonacci(1)
$1$ est un cas de base, fibonacci(1) renvoie (0, 1)
On déduit
- $F_1 = F_1^2 + F_0^2 = 1$
- $F_2 = F_1^2 + 2×F_1×F_0 = 1$
- l'appel fibonacci(2) renvoie (1, 1)
On déduit
- $F_3 = F_2^2 + F_1^2 = 2$
- $F_4 = F_2^2 + 2×F_2×F_1 = 3$
- l'appel fibonacci(4) renvoie (2, 3)
On déduit
- $F_7 = F_4^2 + F_3^2 = 13$
- $F_8 = F_4^2 + 2×F_4×F_3 = 21$
- l'appel fibonacci(8) renvoie (13, 21)
On déduit
- $F_9 = F_8 + F_7 = 34$
- l'appel fibonacci(9) renvoie (21, 34)

Indice : Algorithme

Si n est le cas de base, on renvoie la réponse directement.
Sinon,
- on fait un appel récursif avec n//2 pour obtenir le couple $(F_{k-1}, F_k)$, (k vaut n//2)
- on calcule $F_{2k-1}$ et $F_{2k}$
- si n est pair, (n vaut 2 * k), alors on renvoie le couple $(F_{2k-1}, F_{2k})$
- sinon, n est impair, (n vaut 2*k + 1, $F_{2k+1}=F_{2k-1}+F_{2k}$), et alors on renvoie le couple $(F_{2k}, F_{2k+1})$

Exemples

>>> fibonacci(1)
(0, 1)
>>> fibonacci(2)
(1, 1)
>>> fibonacci(3)
(1, 2)
>>> fibonacci(9)
(21, 34)
>>> fibonacci(4)
(2, 3)

Évaluations restantes : 10/10

.9888.128013.9875.65038,%è OVw*5e(8CR0pkDojic6S1vqA{d:xIFy24f@ln-93m=U)rhu}s;^b/.àt_gLéaùP+7050H0n0/0@0y0R0(0h0z0R0@0(0(0X010/0y0t010406050(0$0W0W0@0!0M040B0w0R0$1c0w0S0h020@0W0t0)0h0r0n1m0!0E0$0n0(050,1j1l1n1p1h0t041N1U051X0,1X1Z1U1h0H0y0D1416181a0#0y0;0#0R1;0#0/1f050 0+0R0n1,1719011:1=1@1=0/1}1 1{0/0+0w0H1p1|0!1V0/0#141s0(0t0@0S1a0N01211.010P110n0S1A0n1{2p2r2w232z1 2C0W2E040b0h0_0!0w0t0w0(0y1v1x0}2n0!0!0n0z2Z1N2G0S1V0,2l2/0/2j2i2k0H2I1a1@0S2B2W1{1)1+15222|0y2~0S2f1*1{0t2(1V2-2/3g1i2q1x342x390!1m0R1f0h0C2,3k1g3j2H3m233o3q3s0N3v2r3x2-2{013C0@3r040h0V3G2.1h3J3A1a3M3O0h0O3S3I3k3K3Y3s0m3$3U3(3W3L0w3p3N3s0A3-3y3l1-3B3=3D3P0{3`3V3}3X3 3@3P0p433/453;3?3Z0U4b3z4d3*040C0s4i3|354e400C3u1O3w3.4j4r4l0C3F4w3H4y4q3n473O0C3R4E3T3{3)4J1f0C3#4N3%4z4I4f4S3,4V4G4Q4Z4m3_4$4P3:4B424V1W3e1N322=0H2_3K0z2f2O0|1*1V3d0n3f3w3$054}0}554X230u1f0}0P57444r0k3s5i4c4A0P1f2z2e2C0z0z0y5n5c1a1e040o5y4H3B1f0S5E3K5B0Z0I4p3K5l3P0h5S5J3:0(0H1f015Z1F0S0D0w0y200o0L0:0G1x0T3t0%0e0h5,5.0%0Z5O5V5X5R5S600h0}0$0J0h390W0+2(132#0L0y5t0@5v0y2n0S0(0?0z1u0y0P1M4,5j2x5W3s605Z013-614-4d0z0C1f03141762200+170n6A606C4r5e046p3$0h6R3n5H6W6Y230w1f0X0X6#6t230W0y4S5U4d5B5N4$616B6-1a6T2(0/0$0!5I4V6X6|015B5D4;766/1f4o7a5o2x5B0e6,7g6.6:4m6=4r5L3-066{7l1a6E6G6I130;0?0S0?0!3N6P5T760S1f0$7p7h1f7j746$3X1f0D7k5z016(046+7R7J5r6e1w6g5w7N23787-7T04733i767Z0,0,7:017c044D7@7v771f5{7475827x046H0$0h0X5@0:0o0u0T0C0Z0h0~0h1+8e5,0u7H877X896H0z3N6n0R6K0h8c8q8g0N8i8k8m0/8o8d8f8H8t7S3L7U803w8u5F1a7Z7#3g8W3)7U7W8X7Y1f0l8)8%047V6_6Q7%047M7f7X7i8.4.8(7$828Z8}4k8T934r7Z0`966Z8^7|7Z8-8`8*7K9c9g5K7P9a5G8:8U3H8$3:989n1a7~9q2.8R9e7|9i8_817X9B9k8~8:8Q766T6V907X9i7?8V9A1f0f9v7}7n9y3P9U7!8!9T7b7n7e9F8*6@6W9s6D6F8a0h2(5$5(200H8c4}0$0t1 0h5+8G8I0Z5?5,8H853g7t6`7I826~0~719S9r8R7/9I949j9-9l047Q8#8R9i8;ar3:7r8=af7X9N5h9P9h6!aH3K7Z9WaK3:9x9X8Z9(al9*6;ao7q1f6^8#9;4r8w9^2B5%5)629~0wa0a2a48Ha8a50`8kab4xaeaD8*ah70729Xanazapay56768|aOap9E9)911f99bb4A8 b5aY04a{4F1N59544=bs0,4^1N0/4`bx2@2:2e2g2=0@1~bu4^1T5b8*2(0W0:0P0@0u0n0:0#0V1f1F1H1J1L0ha!561!3x1U0B6i1wa)0;1n2#1 132U7E0@2Z139 0/0n0$0(1L5?110h0(000@0;2Y8D0S0yb!2N0S8L0}130W0$0R1ca10y8yb{8mcg2(6K640h0;7F0S0H1367691L0-0h0K8B0Mcs0h0@0h2?5(130.140#0@b!0h0PcQ0h1J00b.bQca0$1x0@0t0t0n8B0!6m712X0P0-1Wb*040i1x7Fc-c/a2cWa2cDcu2#cY0yb@0^0hb.c.1u621*d90n0!cbcs1cdj0h2qdk63651L8La*0y2T1x0(b.0R0wb:0!2Y0#2NcL6Mc10h0Nc_b)bK0=20b}8C584~045s7*6h0o0S85br3Pdu621w0zcs0Ddxb.8R1ndG1mb~0J1f090o0V09dC0;d#0Z09bo2.0hckcm1d1@cq0y1w132B2?20cy2rcBdm5)0!0(cG0q00d*2~291Gegdp1tef0P2z8y0z20c#c*200W0?2l4~0h2Yb_1c0DdS3}cd1Kc!0$6ic(8Ld=dF2ld^0nd`04d|0Se46W0@0H1)cregcuejcAefcgenepc`1h0#0CeN0H7w8zcl0T0W2fcl102(1{0y0W0;cMcm1a0a2v3:0/0k1G0w0x6:c50!0z1/290t0(0I7`0z0H0S0-0x5Wc/1*0!0-eu0,1=0,0x0}0zbS0H2:fpf9fs0Q0C0A0-0s0-0C0,220~0(1O0D0;0,0N0A0@f(0(f:2v1c0/1 1a0I0k1ncc0S0;0I3s0qf68Bf99}16dx6OcN3:0#0ne:dj2}5e0h0#2(0P1a038y0R8Af8fagefdcO2Yf 010_dj1m388Lgn1f0c0d1N0@2/f13x1~0wfT1J0wb~c{0_1nc8c gjdpa/dkb?0h0?0R0geRe{e7b`0#ef0Jc.0!b~b@8c2Bdpc;2q5?a/g*710hg-2Bc11;2Ccg6r1%1NgUgW0$gY54bK1r0$eRcgh5dz00370/7E1LdL0@8cc;1jcmb`6200eHdc0tePed1xgccl0wa$2xd?e%b`e)d{0o0We.740wdbe#d@hWe*d|h!e5d)0(8Lc*emdo1J6idncg622r13h?0}6/gy8L1m0z1:2~a3h)hVd_hYh.6Wd*hB186idqd8h 1xd520536/dj0ZcG0v20dAg}eF0$hI1x3dfacah{dv0S4}d6h~dl4}cg2Bb dr2016cO100Ra20HiBe7gYg@i6370ncGc}dpb 8L3N3=13c(cuhJc;9}2*hNi!gdhRiadHh+idh#8#8n2?0@0DiV1 dkc*eUewh|hPdChS23hUj0ice+hZj33wdOhh1U0Feve|1w5?eE5w66esh;8o3NbGd2eV2Vh8g-b^7FcriYe:e=hN5?dAc0j6i`b.8ne8cnebb`hNcG0_g+h9b#32d9hN0(jyjC8L0+5)iCezcO2)0#ccb!0-k1e 1Y040j5(jAi/eocb20eReoi{2#dV5adY5u7,0,d(eWij9_2`h?dq1A0gehc5a0a10?cf0 gfji1ajke(h,joh/j,i|hQa-9^0?hE0 i.jv9}jr3x323Ke:f9cc2Zh}g5dj1f1TkZ0Hk#2YhN0Tf}2b04ivcw2Vhw13b~i6j 1Khgc{dR13a1c0cMkd1ccChmdychb 65i62Wb#6^hhcl3x1@6U8BbQdfcWi kHj2kKdAca0R0?0;0gbNexl6l50~cad3cNf9k:0?hHh?f9i46gi7i)2Rj{3d6md9kAegc35wc3lqhB8Llt76kGj1jn0V0W0*0Njp9rh{i80HiLlQi#i5lUdOlo1hlolul:h-l_e6d*h?egen66b.0Scl8K6Xlmm50y04jJdkm7jmh-020;0/0)0Cmaatdcc+6Xd(f20fe7bqdWko8mjDlB3N0hcSkh544vd(1Nm405lo1md9k(13a27Fcu8ydakE01l/mthZ0Xmzh/htcMmEdWmGmIkmmKmO8BmRd(7emV0,mXloeE8La/1~6imci8jUfv9|es2%iQ62g/cphWmWmomn04cI6620lrchd,dp6J6mdFcumS3K251?1^1`bL3Kb0aj9X7~4v3im~5acM8c1@b dUbrnG1^271_2Fag1f6 nObi2xnQaR9V9X9i0W57nTbumX0,mmnq3xn}0Ro0bJ50334dnHn%nK8R2K2B2D1f2Q0B0zdF0t8L0_0MeLak9z53bL3h56mV9M5f0naGbl2x5Q6XaX3n5qdX7)kk5xoE7.1f79oA9oopnLaA9mn.9on^oL5A84b%bp76oC6QoY016v046y5#a+5*5^0S8j5=8f5_8li66gl i}m}ac8Ro,a}cv65io6b206d6f6h6j6l6n1c6q5|4dp36x5Z9L889?8x6J2#dK6OaCm-aFn?aJav7^6)aTe68Rn:o*9/pv7uaEn+aib2oVoZ5C7|7~9,b882bapA82pGoPpQh/06ada~4|pp7zcx7Cb_0Rpn9Q7L7|pXbep?9KpP8+7!pyoHpbklp#83pRo*9R9d1f7`pS9Zp^oUpYp{oXq4aBacpKaIaqpV8{qfp`qnb7aUbfp p}b4qpqtq9049fq4axn;04bhqgqnbd3H9$qEqA8/qM9zb984qCaNqF1fqiqQoTatb3oN9Cbkq#4d9Hqjq)q7q+qv9GbgnPqdo*q.q,bjqoqNqUbnh/9$qXq}9bq!4FqmnM1f9OqK8/oRm-aMq_1f9!rhpCrj04pUr0pWaZ8tra3:nNpOreq$oOr69oqSoS6?qrq?qBpHqVpv8Rpxp}q8p}rip}aQrRrnrT7nnRrCpQo#3Tp4rNpMb1rgamq:qYp|q/q%qyr.r!8Sq qTqwqJr^qGrKbnqWq*04r8r{qqs14,n`2/or4@51bK0Y1xb~8Bn!g|2Nle6IgwcldobQ5w1 kBj,130U6K72e}cT6p0P6adUl.e$jlhXjn5^4n0*0Gf#0%0%mAfii:eWc7eRd-hJeJeL2#eOjN1*eS22jdl)cXhB0H7FcalG5)c?e7111@b;6bc70S7Dj-dSgak1kW1(1*n#26nJn)7Xoc2M2O2Q0qee1s20omoo57scnS3iov820;5Bmvmxtw0)tyoDr/0P0:0S0WrZrrs7auqs8/tDr,pBqxrzapkj7+oKr;rBtI8*nQrqs68*9eqPtY3KnQ4+r;tKrIt+rYt#rF978,t)t$t;1f4hs0p%8Rtu1ftyu4mw1Ds3tNpi4r0;7Z0m0A0s0m0O0A0p0{4#p1sabt2/o4jt372Xm-m/sKd|sM0ssOsQ0%8N09fDgY13ueuguiuk0mmAk3bv0~iV0(04.