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

.65038.128013.9875.9888s3_8èuf^vIy 7naS1me(P4C2V:jtwiDh*@)6Oo;bcdUgù/0làqAp.rFL-,}=+k%{95Rxé050T0w0F0s0H0Z0e0p0S0Z0s0e0e0/010F0H0%010406050e0j0v0v0s0)0o040t0P0Z0j1c0P0r0p020s0v0%0Q0p0_0w1m0)0#0j0w0e050X1j1l1n1p1h0%041N1U051X0X1X1Z1U1h0T0H0m1416181a0J0H0V0J0Z1;0J0F1f050 0R0Z0w1,1719011:1=1@1=0F1}1 1{0F0R0P0T1p1|0)1V0F0J141s0e0%0s0r1a0B01211.010k110w0r1A0w1{2p2r2w232z1 2C0v2E040b0p0y0)0P0%0P0e0H1v1x0}2n0)0)0w0S2Z1N2G0r1V0X2l2/0F2j2i2k0T2I1a1@0r2B2W1{1)1+15222|0H2~0r2f1*1{0%2(1V2-2/3g1i2q1x342x390)1m0Z1f0p0u2,3k1g3j2H3m233o3q3s0B3v2r3x2-2{013C0s3r040p0f3G2.1h3J3A1a3M3O0p0z3S3I3k3K3Y3s0^3$3U3(3W3L0P3p3N3s0N3-3y3l1-3B3=3D3P0q3`3V3}3X3 3@3P0h433/453;3?3Z0@4b3z4d3*040u0Y4i3|354e400u3u1O3w3.4j4r4l0u3F4w3H4y4q3n473O0u3R4E3T3{3)4J1f0u3#4N3%4z4I4f4S3,4V4G4Q4Z4m3_4$4P3:4B424V1W3e1N322=0T2_3K0S2f2O0|1*1V3d0w3f3w3$054}0}554X230;1f0}0k57444r0G3s5i4c4A0k1f2z2e2C0S0S0H5n5c1a1e040x5y4H3B1f0r5E3K5B0M0D4p3K5l3P0p5S5J3:0e0T1f015Z1F0r0m0P0H200x0*0g0?1x0,3t0.0-0p5,5.0.0M5O5V5X5R5S600p0}0j0`0p390v0R2(132#0*0H5t0s5v0H2n0r0e0{0S1u0H0k1M4,5j2x5W3s605Z013-614-4d0S0u1f03141762200R170w6A606C4r5e046p3$0p6R3n5H6W6Y230P1f0/0/6#6t230v0H4S5U4d5B5N4$616B6-1a6T2(0F0j0)5I4V6X6|015B5D4;766/1f4o7a5o2x5B0-6,7g6.6:4m6=4r5L3-066{7l1a6E6G6I130V0{0r0{0)3N6P5T760r1f0j7p7h1f7j746$3X1f0m7k5z016(046+7R7J5r6e1w6g5w7N23787-7T04733i767Z0X0X7:017c044D7@7v771f5{7475827x046H0j0p0/5@0g0x0;0,0u0M0p0~0p1+8e5,0;7H877X896H0S3N6n0Z6K0p8c8q8g0B8i8k8m0F8o8d8f8H8t7S3L7U803w8u5F1a7Z7#3g8W3)7U7W8X7Y1f0K8)8%047V6_6Q7%047M7f7X7i8.4.8(7$828Z8}4k8T934r7Z0:966Z8^7|7Z8-8`8*7K9c9g5K7P9a5G8:8U3H8$3:989n1a7~9q2.8R9e7|9i8_817X9B9k8~8:8Q766T6V907X9i7?8V9A1f0=9v7}7n9y3P9U7!8!9T7b7n7e9F8*6@6W9s6D6F8a0p2(5$5(200T8c4}0j0%1 0p5+8G8I0M5?5,8H853g7t6`7I826~0~719S9r8R7/9I949j9-9l047Q8#8R9i8;ar3:7r8=af7X9N5h9P9h6!aH3K7Z9WaK3:9x9X8Z9(al9*6;ao7q1f6^8#9;4r8w9^2B5%5)629~0Pa0a2a48Ha8a50:8kab4xaeaD8*ah70729Xanazapay56768|aOap9E9)911f99bb4A8 b5aY04a{4F1N59544=bs0X4^1N0F4`bx2@2:2e2g2=0s1~bu4^1T5b8*2(0v0g0k0s0;0w0g0J0f1f1F1H1J1L0pa!561!3x1U0t6i1wa)0V1n2#1 132U7E0s2Z139 0F0w0j0e1L5?110p0e000s0V2Y8D0r0Hb!2N0r8L0}130v0j0Z1ca10H8yb{8mcg2(6K640p0V7F0r0T1367691L0(0p0n8B0ocs0p0s0p2?5(130!140J0sb!0p0kcQ0p1J00b.bQca0j1x0s0%0%0w8B0)6m712X0k0(1Wb*040O1x7Fc-c/a2cWa2cDcu2#cY0Hb@0W0pb.c.1u621*d90w0)cbcs1cdj0p2qdk63651L8La*0H2T1x0eb.0Z0Pb:0)2Y0J2NcL6Mc10p0Bc_b)bK0+20b}8C584~045s7*6h0x0r85br3Pdu621w0Scs0mdxb.8R1ndG1mb~0`1f090x0f09dC0Vd#0M09bo2.0pckcm1d1@cq0H1w132B2?20cy2rcBdm5)0)0ecG0A00d*2~291Gegdp1tef0k2z8y0S20c#c*200v0{2l4~0p2Yb_1c0mdS3}cd1Kc!0j6ic(8Ld=dF2ld^0wd`04d|0re46W0s0T1)cregcuejcAefcgenepc`1h0J0ueN0T7w8zcl0,0v2fcl102(1{0H0v0VcMcm1a0d2v3:0F0G1G0P0E6:c50)0S1/290%0e0D7`0S0T0r0(0E5Wc/1*0)0(eu0X1=0X0E0}0SbS0T2:fpf9fs0L0u0N0(0Y0(0u0X220~0e1O0m0V0X0B0N0sf(0ef:2v1c0F1 1a0D0G1ncc0r0V0D3s0Af68Bf99}16dx6OcN3:0J0we:dj2}5e0p0J2(0k1a038y0Z8Af8fagefdcO2Yf 010ydj1m388Lgn1f0c0a1N0s2/f13x1~0PfT1J0Pb~c{0y1nc8c gjdpa/dkb?0p0{0Z0ieRe{e7b`0Jef0`c.0)b~b@8c2Bdpc;2q5?a/g*710pg-2Bc11;2Ccg6r1%1NgUgW0jgY54bK1r0jeRcgh5dz00370F7E1LdL0s8cc;1jcmb`6200eHdc0%ePed1xgccl0Pa$2xd?e%b`e)d{0x0ve.740Pdbe#d@hWe*d|h!e5d)0e8Lc*emdo1J6idncg622r13h?0}6/gy8L1m0S1:2~a3h)hVd_hYh.6Wd*hB186idqd8h 1xd520536/dj0McG0I20dAg}eF0jhI1x3dfacah{dv0r4}d6h~dl4}cg2Bb dr2016cO100Za20TiBe7gYg@i6370wcGc}dpb 8L3N3=13c(cuhJc;9}2*hNi!gdhRiadHh+idh#8#8n2?0s0miV1 dkc*eUewh|hPdChS23hUj0ice+hZj33wdOhh1U0$eve|1w5?eE5w66esh;8o3NbGd2eV2Vh8g-b^7FcriYe:e=hN5?dAc0j6i`b.8ne8cnebb`hNcG0yg+h9b#32d9hN0ejyjC8L0R5)iCezcO2)0Jccb!0(k1e 1Y040C5(jAi/eocb20eReoi{2#dV5adY5u7,0Xd(eWij9_2`h?dq1A0iehc5a0a10{cf0 gfji1ajke(h,joh/j,i|hQa-9^0{hE0 i.jv9}jr3x323Ke:f9cc2Zh}g5dj1f1TkZ0Tk#2YhN0,f}2b04ivcw2Vhw13b~i6j 1Khgc{dR13a1c0cMkd1ccChmdychb 65i62Wb#6^hhcl3x1@6U8BbQdfcWi kHj2kKdAca0Z0{0V0ibNexl6l50~cad3cNf9k:0{hHh?f9i46gi7i)2Rj{3d6md9kAegc35wc3lqhB8Llt76kGj1jn0f0v0l0Bjp9rh{i80TiLlQi#i5lUdOlo1hlolul:h-l_e6d*h?egen66b.0rcl8K6Xlmm50H04jJdkm7jmh-020V0F0Q0umaatdcc+6Xd(f20=e7bqdWko8mjDlB3N0pcSkh544vd(1Nm405lo1md9k(13a27Fcu8ydakE01l/mthZ0/mzh/htcMmEdWmGmIkmmKmO8BmRd(7emV0XmXloeE8La/1~6imci8jUfv9|es2%iQ62g/cphWmWmomn04cI6620lrchd,dp6J6mdFcumS3K251?1^1`bL3Kb0aj9X7~4v3im~5acM8c1@b dUbrnG1^271_2Fag1f6 nObi2xnQaR9V9X9i0v57nTbumX0Xmmnq3xn}0Zo0bJ50334dnHn%nK8R2K2B2D1f2Q0t0SdF0%8L0y0oeLak9z53bL3h56mV9M5f0waGbl2x5Q6XaX3n5qdX7)kk5xoE7.1f79oA9oopnLaA9mn.9on^oL5A84b%bp76oC6QoY016v046y5#a+5*5^0r8j5=8f5_8li66gl i}m}ac8Ro,a}cv65io6b206d6f6h6j6l6n1c6q5|4dp36x5Z9L889?8x6J2#dK6OaCm-aFn?aJav7^6)aTe68Rn:o*9/pv7uaEn+aib2oVoZ5C7|7~9,b882bapA82pGoPpQh/06ada~4|pp7zcx7Cb_0Zpn9Q7L7|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@51bK0U1xb~8Bn!g|2Nle6IgwcldobQ5w1 kBj,130@6K72e}cT6p0k6adUl.e$jlhXjn5^4n0l0?f#0.0.mAfii:eWc7eRd-hJeJeL2#eOjN1*eS22jdl)cXhB0T7FcalG5)c?e7111@b;6bc70r7Dj-dSgak1kW1(1*n#26nJn)7Xoc2M2O2Q0Aee1s20omoo57scnS3iov820V5Bmvmxtw0QtyoDr/0k0g0r0vrZrrs7auqs8/tDr,pBqxrzapkj7+oKr;rBtI8*nQrqs68*9eqPtY3KnQ4+r;tKrIt+rYt#rF978,t)t$t;1f4hs0p%8Rtu1ftyu4mw1Ds3tNpi4r0V7Z0^0N0Y0^0z0N0h0q4#p1sabt2/o4jt372Xm-m/sKd|sM0YsOsQ0.8N09fDgY13ueuguiuk0^mAk3bv0~iV0e04.