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.9875.65038.128013:Lp%(40^ed@3; 1j}Vo5_An)hù6,qcyFCuvà8i2+DxmsU7=wlSIatf-9O{Rrg.*éPkbè/050n0m0(0%0P0!0V0r0H0!0%0V0V0Y010(0P0g010406050V0L0U0U0%0/0I040#0w0!0L1c0w0A0r020%0U0g0q0r0.0m1m0/0G0L0m0V050{1j1l1n1p1h0g041N1U051X0{1X1Z1U1h0n0P0M1416181a0C0P0:0C0!1;0C0(1f050 0_0!0m1,1719011:1=1@1=0(1}1 1{0(0_0w0n1p1|0/1V0(0C141s0V0g0%0A1a0Q01211.010)110m0A1A0m1{2p2r2w232z1 2C0U2E040d0r0@0/0w0g0w0V0P1v1x0}2n0/0/0m0H2Z1N2G0A1V0{2l2/0(2j2i2k0n2I1a1@0A2B2W1{1)1+15222|0P2~0A2f1*1{0g2(1V2-2/3g1i2q1x342x390/1m0!1f0r0s2,3k1g3j2H3m233o3q3s0Q3v2r3x2-2{013C0%3r040r0p3G2.1h3J3A1a3M3O0r0j3S3I3k3K3Y3s0x3$3U3(3W3L0w3p3N3s0E3-3y3l1-3B3=3D3P0X3`3V3}3X3 3@3P0O433/453;3?3Z0+4b3z4d3*040s0k4i3|354e400s3u1O3w3.4j4r4l0s3F4w3H4y4q3n473O0s3R4E3T3{3)4J1f0s3#4N3%4z4I4f4S3,4V4G4Q4Z4m3_4$4P3:4B424V1W3e1N322=0n2_3K0H2f2O0|1*1V3d0m3f3w3$054}0}554X230^1f0}0)57444r0Z3s5i4c4A0)1f2z2e2C0H0H0P5n5c1a1e040i5y4H3B1f0A5E3K5B0B0e4p3K5l3P0r5S5J3:0V0n1f015Z1F0A0M0w0P200i0J0y0-1x0*3t0u0F0r5,5.0u0B5O5V5X5R5S600r0}0L0T0r390U0_2(132#0J0P5t0%5v0P2n0A0V0?0H1u0P0)1M4,5j2x5W3s605Z013-614-4d0H0s1f03141762200_170m6A606C4r5e046p3$0r6R3n5H6W6Y230w1f0Y0Y6#6t230U0P4S5U4d5B5N4$616B6-1a6T2(0(0L0/5I4V6X6|015B5D4;766/1f4o7a5o2x5B0F6,7g6.6:4m6=4r5L3-066{7l1a6E6G6I130:0?0A0?0/3N6P5T760A1f0L7p7h1f7j746$3X1f0M7k5z016(046+7R7J5r6e1w6g5w7N23787-7T04733i767Z0{0{7:017c044D7@7v771f5{7475827x046H0L0r0Y5@0y0i0^0*0s0B0r0~0r1+8e5,0^7H877X896H0H3N6n0!6K0r8c8q8g0Q8i8k8m0(8o8d8f8H8t7S3L7U803w8u5F1a7Z7#3g8W3)7U7W8X7Y1f0=8)8%047V6_6Q7%047M7f7X7i8.4.8(7$828Z8}4k8T934r7Z0R966Z8^7|7Z8-8`8*7K9c9g5K7P9a5G8:8U3H8$3:989n1a7~9q2.8R9e7|9i8_817X9B9k8~8:8Q766T6V907X9i7?8V9A1f0h9v7}7n9y3P9U7!8!9T7b7n7e9F8*6@6W9s6D6F8a0r2(5$5(200n8c4}0L0g1 0r5+8G8I0B5?5,8H853g7t6`7I826~0~719S9r8R7/9I949j9-9l047Q8#8R9i8;ar3:7r8=af7X9N5h9P9h6!aH3K7Z9WaK3:9x9X8Z9(al9*6;ao7q1f6^8#9;4r8w9^2B5%5)629~0wa0a2a48Ha8a50R8kab4xaeaD8*ah70729Xanazapay56768|aOap9E9)911f99bb4A8 b5aY04a{4F1N59544=bs0{4^1N0(4`bx2@2:2e2g2=0%1~bu4^1T5b8*2(0U0y0)0%0^0m0y0C0p1f1F1H1J1L0ra!561!3x1U0#6i1wa)0:1n2#1 132U7E0%2Z139 0(0m0L0V1L5?110r0V000%0:2Y8D0A0Pb!2N0A8L0}130U0L0!1ca10P8yb{8mcg2(6K640r0:7F0A0n1367691L0;0r0$8B0Ics0r0%0r2?5(130N140C0%b!0r0)cQ0r1J00b.bQca0L1x0%0g0g0m8B0/6m712X0)0;1Wb*040,1x7Fc-c/a2cWa2cDcu2#cY0Pb@0D0rb.c.1u621*d90m0/cbcs1cdj0r2qdk63651L8La*0P2T1x0Vb.0!0wb:0/2Y0C2NcL6Mc10r0Qc_b)bK0f20b}8C584~045s7*6h0i0A85br3Pdu621w0Hcs0Mdxb.8R1ndG1mb~0T1f090i0p09dC0:d#0B09bo2.0rckcm1d1@cq0P1w132B2?20cy2rcBdm5)0/0VcG0K00d*2~291Gegdp1tef0)2z8y0H20c#c*200U0?2l4~0r2Yb_1c0MdS3}cd1Kc!0L6ic(8Ld=dF2ld^0md`04d|0Ae46W0%0n1)cregcuejcAefcgenepc`1h0C0seN0n7w8zcl0*0U2fcl102(1{0P0U0:cMcm1a0a2v3:0(0Z1G0w0t6:c50/0H1/290g0V0e7`0H0n0A0;0t5Wc/1*0/0;eu0{1=0{0t0}0HbS0n2:fpf9fs0o0s0E0;0k0;0s0{220~0V1O0M0:0{0Q0E0%f(0Vf:2v1c0(1 1a0e0Z1ncc0A0:0e3s0Kf68Bf99}16dx6OcN3:0C0me:dj2}5e0r0C2(0)1a038y0!8Af8fagefdcO2Yf 010@dj1m388Lgn1f0b0c1N0%2/f13x1~0wfT1J0wb~c{0@1nc8c gjdpa/dkb?0r0?0!0`eRe{e7b`0Cef0Tc.0/b~b@8c2Bdpc;2q5?a/g*710rg-2Bc11;2Ccg6r1%1NgUgW0LgY54bK1r0LeRcgh5dz00370(7E1LdL0%8cc;1jcmb`6200eHdc0gePed1xgccl0wa$2xd?e%b`e)d{0i0Ue.740wdbe#d@hWe*d|h!e5d)0V8Lc*emdo1J6idncg622r13h?0}6/gy8L1m0H1:2~a3h)hVd_hYh.6Wd*hB186idqd8h 1xd520536/dj0BcG0S20dAg}eF0LhI1x3dfacah{dv0A4}d6h~dl4}cg2Bb dr2016cO100!a20niBe7gYg@i6370mcGc}dpb 8L3N3=13c(cuhJc;9}2*hNi!gdhRiadHh+idh#8#8n2?0%0MiV1 dkc*eUewh|hPdChS23hUj0ice+hZj33wdOhh1U0zeve|1w5?eE5w66esh;8o3NbGd2eV2Vh8g-b^7FcriYe:e=hN5?dAc0j6i`b.8ne8cnebb`hNcG0@g+h9b#32d9hN0VjyjC8L0_5)iCezcO2)0Cccb!0;k1e 1Y040v5(jAi/eocb20eReoi{2#dV5adY5u7,0{d(eWij9_2`h?dq1A0`ehc5a0a10?cf0 gfji1ajke(h,joh/j,i|hQa-9^0?hE0 i.jv9}jr3x323Ke:f9cc2Zh}g5dj1f1TkZ0nk#2YhN0*f}2b04ivcw2Vhw13b~i6j 1Khgc{dR13a1c0cMkd1ccChmdychb 65i62Wb#6^hhcl3x1@6U8BbQdfcWi kHj2kKdAca0!0?0:0`bNexl6l50~cad3cNf9k:0?hHh?f9i46gi7i)2Rj{3d6md9kAegc35wc3lqhB8Llt76kGj1jn0p0U0l0Qjp9rh{i80niLlQi#i5lUdOlo1hlolul:h-l_e6d*h?egen66b.0Acl8K6Xlmm50P04jJdkm7jmh-020:0(0q0smaatdcc+6Xd(f20he7bqdWko8mjDlB3N0rcSkh544vd(1Nm405lo1md9k(13a27Fcu8ydakE01l/mthZ0Ymzh/htcMmEdWmGmIkmmKmO8BmRd(7emV0{mXloeE8La/1~6imci8jUfv9|es2%iQ62g/cphWmWmomn04cI6620lrchd,dp6J6mdFcumS3K251?1^1`bL3Kb0aj9X7~4v3im~5acM8c1@b dUbrnG1^271_2Fag1f6 nObi2xnQaR9V9X9i0U57nTbumX0{mmnq3xn}0!o0bJ50334dnHn%nK8R2K2B2D1f2Q0#0HdF0g8L0@0IeLak9z53bL3h56mV9M5f0maGbl2x5Q6XaX3n5qdX7)kk5xoE7.1f79oA9oopnLaA9mn.9on^oL5A84b%bp76oC6QoY016v046y5#a+5*5^0A8j5=8f5_8li66gl i}m}ac8Ro,a}cv65io6b206d6f6h6j6l6n1c6q5|4dp36x5Z9L889?8x6J2#dK6OaCm-aFn?aJav7^6)aTe68Rn:o*9/pv7uaEn+aib2oVoZ5C7|7~9,b882bapA82pGoPpQh/06ada~4|pp7zcx7Cb_0!pn9Q7L7|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@51bK0W1xb~8Bn!g|2Nle6IgwcldobQ5w1 kBj,130+6K72e}cT6p0)6adUl.e$jlhXjn5^4n0l0-f#0u0umAfii:eWc7eRd-hJeJeL2#eOjN1*eS22jdl)cXhB0n7FcalG5)c?e7111@b;6bc70A7Dj-dSgak1kW1(1*n#26nJn)7Xoc2M2O2Q0Kee1s20omoo57scnS3iov820:5Bmvmxtw0qtyoDr/0)0y0A0UrZrrs7auqs8/tDr,pBqxrzapkj7+oKr;rBtI8*nQrqs68*9eqPtY3KnQ4+r;tKrIt+rYt#rF978,t)t$t;1f4hs0p%8Rtu1ftyu4mw1Ds3tNpi4r0:7Z0x0E0k0x0j0E0O0X4#p1sabt2/o4jt372Xm-m/sKd|sM0ksOsQ0u8N09fDgY13ueuguiuk0xmAk3bv0~iV0V04.