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

.9875.128013.65038.98884A2nygFIù )rPCq-;joàè{*u@5(é:,Vtsh^07w+8f/U63pODv1x=a_%ckm}iLeS9lRb.d050{0;0J0(0/0@0K0n0+0@0(0K0K0%010J0/0X010406050K0B0-0-0(0p0i040=0w0@0B1c0w0h0n020(0-0X0u0n0^0;1m0p0s0B0;0K050T1j1l1n1p1h0X041N1U051X0T1X1Z1U1h0{0/0!1416181a0L0/0j0L0@1;0L0J1f050 0_0@0;1,1719011:1=1@1=0J1}1 1{0J0_0w0{1p1|0p1V0J0L141s0K0X0(0h1a0g01211.010S110;0h1A0;1{2p2r2w232z1 2C0-2E040b0n0q0p0w0X0w0K0/1v1x0}2n0p0p0;0+2Z1N2G0h1V0T2l2/0J2j2i2k0{2I1a1@0h2B2W1{1)1+15222|0/2~0h2f1*1{0X2(1V2-2/3g1i2q1x342x390p1m0@1f0n0#2,3k1g3j2H3m233o3q3s0g3v2r3x2-2{013C0(3r040n0W3G2.1h3J3A1a3M3O0n0e3S3I3k3K3Y3s0D3$3U3(3W3L0w3p3N3s0V3-3y3l1-3B3=3D3P0O3`3V3}3X3 3@3P0R433/453;3?3Z0?4b3z4d3*040#0N4i3|354e400#3u1O3w3.4j4r4l0#3F4w3H4y4q3n473O0#3R4E3T3{3)4J1f0#3#4N3%4z4I4f4S3,4V4G4Q4Z4m3_4$4P3:4B424V1W3e1N322=0{2_3K0+2f2O0|1*1V3d0;3f3w3$054}0}554X230,1f0}0S57444r0P3s5i4c4A0S1f2z2e2C0+0+0/5n5c1a1e040E5y4H3B1f0h5E3K5B0o0G4p3K5l3P0n5S5J3:0K0{1f015Z1F0h0!0w0/200E0k0)0z1x0t3t0.0H0n5,5.0.0o5O5V5X5R5S600n0}0B0$0n390-0_2(132#0k0/5t0(5v0/2n0h0K0F0+1u0/0S1M4,5j2x5W3s605Z013-614-4d0+0#1f03141762200_170;6A606C4r5e046p3$0n6R3n5H6W6Y230w1f0%0%6#6t230-0/4S5U4d5B5N4$616B6-1a6T2(0J0B0p5I4V6X6|015B5D4;766/1f4o7a5o2x5B0H6,7g6.6:4m6=4r5L3-066{7l1a6E6G6I130j0F0h0F0p3N6P5T760h1f0B7p7h1f7j746$3X1f0!7k5z016(046+7R7J5r6e1w6g5w7N23787-7T04733i767Z0T0T7:017c044D7@7v771f5{7475827x046H0B0n0%5@0)0E0,0t0#0o0n0~0n1+8e5,0,7H877X896H0+3N6n0@6K0n8c8q8g0g8i8k8m0J8o8d8f8H8t7S3L7U803w8u5F1a7Z7#3g8W3)7U7W8X7Y1f0A8)8%047V6_6Q7%047M7f7X7i8.4.8(7$828Z8}4k8T934r7Z0Q966Z8^7|7Z8-8`8*7K9c9g5K7P9a5G8:8U3H8$3:989n1a7~9q2.8R9e7|9i8_817X9B9k8~8:8Q766T6V907X9i7?8V9A1f0*9v7}7n9y3P9U7!8!9T7b7n7e9F8*6@6W9s6D6F8a0n2(5$5(200{8c4}0B0X1 0n5+8G8I0o5?5,8H853g7t6`7I826~0~719S9r8R7/9I949j9-9l047Q8#8R9i8;ar3:7r8=af7X9N5h9P9h6!aH3K7Z9WaK3:9x9X8Z9(al9*6;ao7q1f6^8#9;4r8w9^2B5%5)629~0wa0a2a48Ha8a50Q8kab4xaeaD8*ah70729Xanazapay56768|aOap9E9)911f99bb4A8 b5aY04a{4F1N59544=bs0T4^1N0J4`bx2@2:2e2g2=0(1~bu4^1T5b8*2(0-0)0S0(0,0;0)0L0W1f1F1H1J1L0na!561!3x1U0=6i1wa)0j1n2#1 132U7E0(2Z139 0J0;0B0K1L5?110n0K000(0j2Y8D0h0/b!2N0h8L0}130-0B0@1ca10/8yb{8mcg2(6K640n0j7F0h0{1367691L0`0n0l8B0ics0n0(0n2?5(130x140L0(b!0n0ScQ0n1J00b.bQca0B1x0(0X0X0;8B0p6m712X0S0`1Wb*040Y1x7Fc-c/a2cWa2cDcu2#cY0/b@0m0nb.c.1u621*d90;0pcbcs1cdj0n2qdk63651L8La*0/2T1x0Kb.0@0wb:0p2Y0L2NcL6Mc10n0gc_b)bK0:20b}8C584~045s7*6h0E0h85br3Pdu621w0+cs0!dxb.8R1ndG1mb~0$1f090E0W09dC0jd#0o09bo2.0nckcm1d1@cq0/1w132B2?20cy2rcBdm5)0p0KcG0r00d*2~291Gegdp1tef0S2z8y0+20c#c*200-0F2l4~0n2Yb_1c0!dS3}cd1Kc!0B6ic(8Ld=dF2ld^0;d`04d|0he46W0(0{1)cregcuejcAefcgenepc`1h0L0#eN0{7w8zcl0t0-2fcl102(1{0/0-0jcMcm1a0d2v3:0J0P1G0w0v6:c50p0+1/290X0K0G7`0+0{0h0`0v5Wc/1*0p0`eu0T1=0T0v0}0+bS0{2:fpf9fs0C0#0V0`0N0`0#0T220~0K1O0!0j0T0g0V0(f(0Kf:2v1c0J1 1a0G0P1ncc0h0j0G3s0rf68Bf99}16dx6OcN3:0L0;e:dj2}5e0n0L2(0S1a038y0@8Af8fagefdcO2Yf 010qdj1m388Lgn1f0a0c1N0(2/f13x1~0wfT1J0wb~c{0q1nc8c gjdpa/dkb?0n0F0@0yeRe{e7b`0Lef0$c.0pb~b@8c2Bdpc;2q5?a/g*710ng-2Bc11;2Ccg6r1%1NgUgW0BgY54bK1r0BeRcgh5dz00370J7E1LdL0(8cc;1jcmb`6200eHdc0XePed1xgccl0wa$2xd?e%b`e)d{0E0-e.740wdbe#d@hWe*d|h!e5d)0K8Lc*emdo1J6idncg622r13h?0}6/gy8L1m0+1:2~a3h)hVd_hYh.6Wd*hB186idqd8h 1xd520536/dj0ocG0Z20dAg}eF0BhI1x3dfacah{dv0h4}d6h~dl4}cg2Bb dr2016cO100@a20{iBe7gYg@i6370;cGc}dpb 8L3N3=13c(cuhJc;9}2*hNi!gdhRiadHh+idh#8#8n2?0(0!iV1 dkc*eUewh|hPdChS23hUj0ice+hZj33wdOhh1U0feve|1w5?eE5w66esh;8o3NbGd2eV2Vh8g-b^7FcriYe:e=hN5?dAc0j6i`b.8ne8cnebb`hNcG0qg+h9b#32d9hN0KjyjC8L0_5)iCezcO2)0Lccb!0`k1e 1Y040I5(jAi/eocb20eReoi{2#dV5adY5u7,0Td(eWij9_2`h?dq1A0yehc5a0a10Fcf0 gfji1ajke(h,joh/j,i|hQa-9^0FhE0 i.jv9}jr3x323Ke:f9cc2Zh}g5dj1f1TkZ0{k#2YhN0tf}2b04ivcw2Vhw13b~i6j 1Khgc{dR13a1c0cMkd1ccChmdychb 65i62Wb#6^hhcl3x1@6U8BbQdfcWi kHj2kKdAca0@0F0j0ybNexl6l50~cad3cNf9k:0FhHh?f9i46gi7i)2Rj{3d6md9kAegc35wc3lqhB8Llt76kGj1jn0W0-0M0gjp9rh{i80{iLlQi#i5lUdOlo1hlolul:h-l_e6d*h?egen66b.0hcl8K6Xlmm50/04jJdkm7jmh-020j0J0u0#maatdcc+6Xd(f20*e7bqdWko8mjDlB3N0ncSkh544vd(1Nm405lo1md9k(13a27Fcu8ydakE01l/mthZ0%mzh/htcMmEdWmGmIkmmKmO8BmRd(7emV0TmXloeE8La/1~6imci8jUfv9|es2%iQ62g/cphWmWmomn04cI6620lrchd,dp6J6mdFcumS3K251?1^1`bL3Kb0aj9X7~4v3im~5acM8c1@b dUbrnG1^271_2Fag1f6 nObi2xnQaR9V9X9i0-57nTbumX0Tmmnq3xn}0@o0bJ50334dnHn%nK8R2K2B2D1f2Q0=0+dF0X8L0q0ieLak9z53bL3h56mV9M5f0;aGbl2x5Q6XaX3n5qdX7)kk5xoE7.1f79oA9oopnLaA9mn.9on^oL5A84b%bp76oC6QoY016v046y5#a+5*5^0h8j5=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@51bK0U1xb~8Bn!g|2Nle6IgwcldobQ5w1 kBj,130?6K72e}cT6p0S6adUl.e$jlhXjn5^4n0M0zf#0.0.mAfii:eWc7eRd-hJeJeL2#eOjN1*eS22jdl)cXhB0{7FcalG5)c?e7111@b;6bc70h7Dj-dSgak1kW1(1*n#26nJn)7Xoc2M2O2Q0ree1s20omoo57scnS3iov820j5Bmvmxtw0utyoDr/0S0)0h0-rZrrs7auqs8/tDr,pBqxrzapkj7+oKr;rBtI8*nQrqs68*9eqPtY3KnQ4+r;tKrIt+rYt#rF978,t)t$t;1f4hs0p%8Rtu1ftyu4mw1Ds3tNpi4r0j7Z0D0V0N0D0e0V0R0O4#p1sabt2/o4jt372Xm-m/sKd|sM0NsOsQ0.8N09fDgY13ueuguiuk0DmAk3bv0~iV0K04.