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.128013bqO,9v@ià3o_x;}jlpwf( gù06-)2As1^+8Ve%né4èm5tCLRPhk:c.a=DryFS*Iu/7{Ud050{0O0W0*0l0u0I0z0(0u0*0I0I0+010W0l0v010406050I0?0U0U0*0-0.040:0o0u0?1c0o0Q0z020*0U0v0r0z0Z0O1m0-0f0?0O0I050@1j1l1n1p1h0v04051U1N1X0@1U1h0{0l0j1416181a0#0l0A0#0u1/0#0W1f050 0e0u0O1*1719011.1:1=1:0W1{1}1_0W0-1V0W0#141s0I0v0*0Q1a0G011 1,010x110O0Q1A0O1_2i2k2p212s1}2v0U2x040d0z0!0-0o0v0o0I0l1v1x0}2g0-0-0O0(2S1N2z0Q1V0@2e2(2b2d2c1`0{2B1a1=0Q2u2P1_1%1)15202=0l2@0Q0o2{1_0v2X1V2$2(391i2j1x2}2q320-1m0u1f0z0J2#3d1g3c2A3f213h3j3l0G3o2k3q2$2;013v0*3k040z0n3z2%1h3C3t1a3F3H0z0S3L3B3d3D3R3l0V3V3N3X3P3E0o3i3G3l0D3$3r3e1+3u3+3w3I0^3:3O3?3Q3^3-3I0M3|3(3~3*3,3S0i443s463Z040J0C4b3=2~473_0J3n1O3p3%4c4k4e0J3y4p3A4r4j3g403H0J3K4x3M3;3Y4C1f0J3U4G3W4s4B484L3#4O4z4J4S4f3/4V4I3)4u3{4O1Y371N2{2+0{2d2:3)0(332H0|1(1V360O383p3V054@0}4 4Q210$1f0}0x513}4k0w3l5c454t0x1f2s0e1w0*0(0(0l5h561a1e040y5t4A3u1f0Q5z3D5w0F0%4i3D5f3I0z5N5E3)0I0{1f021J0o0W0r5U0?5W5Y5V5X1F0Q0j0o0l1~0y0/0p0_1x0E3m0s0h0z5:5=0s0F5J5Q5S5M5N640z0}0?0q0z320U0e2X132U0/0l5n2v5q0l2g0Q0I0R0(1u0l0x1M4#5d2q5R3l645Z5#6C5X6E0r3$654$460(0J1f031417661~0e170O6I646K4k58046t3V0z6Z3g5C6(6*210o1f0+0+6-6x210U0l4L5P465w5I4V656J6^1a6#2X0W0?0-5D4O6)74015w5y4*7e6`1f4h7i5i2q5w0h6@7o6_6{4f6}4k5G3$06737t1a6M6O6Q130A0R0Q0R0-3G6X5O7e0Q1f0?7x7p1f7r7c6.3Q1f0j7s5u016:046?7Z7R5l6i5o6l7V217g7@7#047b3b7e7+0@0@7`017k044w7~7D7f1f5 7c7d897F046P0?0z0+5{0p0y0$0E0J0F0z0~0z1)8l5:0$7P8e7)8g6P0(3G6r0u6S0z8j8x8n0G8p8r8t0W8v8k8m8O8A7!3E7$873p8B5A1a7+7-398%3Y7$7(8(7*1f0;8:8.047%716Y7/047U7n7)7q8^4%8/7.898*944d8!9a4k7+0L9d6+8 837+8@918;7S9j9n5F7X9h5B8`8#3A8-3)9f9u1a859x2%8Y9l839p90887)9I9r958`8X7e6#6%977)9p7}8$9H1f0P9C847v9F3I9#7,8+9!7j7v7m9M8;6 6(9z6L6N8h0z2X5*5,1~0{8j4@0?0v1}0z5/8N8P0F5`5:8O8c397B727Q89760~799Z9y8Y7_9P9b9q9@9s047Y8,8Y9p8{ay3)7z8|am7)9U5b9W9o6,aO3D7+9%aR3)9E9(8*9/as9;6|av7y1f708,9{4k8D9 2u5+5-66a50oa7a9ab8Oafac0L8rai4qalaK8;ao787a9(auaGawaF507e93aVaw9L9:981f9gbi4t96bca)04b24y1N534~4+bz0@4.1N0W4:bE2.2)0*1|bB4.1T558;2X0U0p0x0*0$0O0p0#0n1f1F1H1J1L0za+501!3q1U0:6m1wa:0A1n2U1}132N7M0*2S13a60W0O0?0I1L5`110z0I000*0A2R8K0Q0lb(2G0Q8S0}130U0?0u1ca80l8Fb 8tck2X6S680z0A7N0Q0{136b6d1L0)0z0=8I0.cw0z0*0z2b5,130m140#0*b(0z0xcU0z1J00b=bUce0?1x0*0v0v0O8I0-6q792Q0x0)1Yb.040g1x7Nc;c?a9c!a9cHcy2Uc$0lb{0B0zb=c=1u661(dd0O0-cfcw1cdn0z2jdo67691L8Sa;0l2M1x0Ib=0u0ob@0-2R0#2GcP6Uc50z0Gc}b-bO0Y1~c18J524^045m7=5r0y0Q8cby3Idy661w0(cw0jdBb=8Y1ndK1mc20q1f090y0n09dG0Ad)0F09bv2%0zcocq1d1=cu0l1w132u2b1~cC2kcFdq5-0-0IcK0X00d.2@271Gekdt1tej0x2s8F0(1~c)c.1~0U0R2e4^0z2Rb}1c0jdW3?ch1Kc(0?6mc,8Sd_dJ2ed|0Od~04e00Qe86(0*0{1%cvekcyencEejckeretc~1h0#0JeR0{7E8Gcp0E0U33cp102X1_0l0U0AcQcq1a0a2o3)0W0w1G0o0t6{c90-0(1-270v0I0%810(0{0Q0)0t5Rc?1(0-0)ey0@1:0@0t0}0(bW0{2)ftfdfw0k0J0V0)0J0)0C0@200~0I1O0j0A0@0G0D0*0C0)0If@2o1c0W1}1a0%0w1ncg0Q0A0%2o0@3I0Xfa8Ifda416dB6WcR3)0#0Oe@dn2?580z0#2X0x1a038F0u8HfcfeglfhcS2Rg4010!dn1m318Sgu1f0b0c1N0*2(f53q1|0ofX5%4~bO0!1nccd3gqdta_dob`0z0R0u0TeVe ebb~0#ej0qc=0-c2b{8j2udtc^2j5`a_g:790zg?2uc51/2vck6v1#1Ng#g%5!c2c 1r0?eVckhbdD00300W7M1LdP0*8jc^1jcqb~6600eLdg0veTeh1xgjcp0oa-2qd`e+b~e-d 0y0Ue=7c0odfe)d{h#e.e0h)e9d-0I8Sc.eqds1J6mdrck662k13h{0}6`gF8S1m0(1.2@aah.h!d}h%h?6(d.hG186mdudci41xd91~4}6`dn0FcK0,1~dEh3eJ0?hN1x36fecei0dz0Q4@dai3dp4@ck2uc3dv1~16cS100ua90{iGeb5Wg}ib300OcKd1dtc38S3G3+13c,cyhOc^a42ZhSi)gkhWifdLh:iih*8,8u2b0*0ji!1}doc.eYeAi1hUdGhX21hZj5ihe/h(j83pdShn1U0Hezf01w5`eI5r6aewh_8v3GbKd6eZ2Oheg?b|7Ncvi%e@e_hS5`dEc4jbi b=8ueccrefb~hScK0!g;hfb)2{ddhS0IjDjH8S0e5-iHeDcS2Y0#cgb(0)k6f31W040N5,jFi@escf1~eVesj02UdZ54d$6k5rbxd!e!ioa02:h{du1A0Telc9a7a80Rcj0 gmjn1ajpe,h;jth@j;j1hVa@9 0RhJ0 i?jAa4jw3q2{3De@fdcg2Si2gadn1f1Tk(0{k*2RhS0Eg22904iAcA2OhB13c2ibk41Khmc dV13a8c4cQki1ccG5Wdn1wclc369ib2Pb)70hncp3q1=6$8IbUdjc!j4kMj7kPdEce0u0R0A0TbReBlbla0~ced7cRfdk^0RhMh{fdi95pici.2Kk0366qddkFekc75rc7lwhG8Slz7ekLj6js0n0U0K0Gju9yi0id0{iQlWi*ial!dSlu1hlulAl_h=l ead.h{eker6ab=0Qcp8R6)lsmb0l04jOdomdjrh=020A5X0JmgaAdgc/6)d,f60Pebkr54kt8tjIlH3G0zcWkm4~4od,1Nma05lu1mddk-13a97Ncy8FdekJ01l^mzh(0+mEh@hycQmJd!mLmN0@d,g@b@8ImWd,7mm!0@m$lueI8Sa_1|6mmiidjZfza3ew2WiV66g^cth#m#mumt04cM6a1~lxcld:dt6R6qdJcymX3D231;1?1^bP3Db7aq9(854o3bn3kshGhf5-8jklbynM1?251@2yan1f77nUbp2qnWaY9$9(9p0U51nZ54nw3q0@mso21ho40uo3bN4`2|46nNn-nQ8Y2D2u2w1f2J0:0(dJ0v8S0!0.ePar9G4}bP3a50m!9T590OaNbs2q5L6)a(3g5kd#7;kp5soL7^1f7hoH9vownRaH9tn@9vn~oS5v8bb+bw7eoJ6Yo)016z046Go^5%0r5)a=5.5|0Q8q5_8m5}8sib5pm5j2n2aj8Yo?b4cz69it6f1~6h6j5pjFiS6p6r1c6u6046pd6Bo`o_hr6HaJm=a/m:8JdO6WpB8YaMn|aQaC7 6;a!ea8Yn_o;9_pB7CaLn;apb9o$o*5x83859?bf89bhpN89pToWp%h@06akb53DpD6R7J7L7N0u9S899K83p.bl9Xbrq78;99p$8ZoOpl7?pUoU9JpMp,9N1f81p)9*q5o#p/q804o(p=8abuq2qvbk3Aatqtqa8_bea#bm7,baqjo;aE9k8?qk9Rqd9Bqdq4o;9OqyqYqyaIqyaTqTqxqm9^qGqK92qOq#q9qEpO049mq%q=q-qIn`04boqu8;aXqZqSqP7Tqsbuh@9-aUq?qwqBb61f9Vr38_oYm=q*qdr5rl9ApPnV9=rao,3MpepJpZb8rnqFp(r8axq~o!aApLqUq|qApIoD6$oGqH9QrEq_rerU46rrrZ9erurq7vnXrJ6~a*8ApXri04n=p#rsr-rGrfqJ9Gbgq/pRr~r`r,bqrIq^qLr2s39ir|oZr_rcrXq+rap@mObBoy4-4{bO0`1xc28In*h22Glk6QgDcpdsbU5r1}kGj;130i6S7af1cX6t0x6edYl@e*jqh$js5|4g0K0_0J0D0s0smFfmi^e!cbeVd;hOeNeP2UeSjS1(eW20jil/c#hG0{7NcelMn%kf6`i#0lb^6fcb0Q7Lj=dWghk6k#1$1(n+24nPn/7)oj2F2H2J0Xei1s1~otov51slnY3boC890A5wmB6FmC5YtIoKrf0x0p0Q0Ur+s6q;rLqX5ltOr0pQ9,8~kopmoRrOoVs97u4Lp+tSqb8?q{t+9Dr*4!rOaBr$n^r*t.r}qL0;t=t/3D854aqirPpb7etE5TtItGtJ5XtLt?qetNoY4W3)0A7+0V0D0C0V0S0D0M0^4Upbo0sk4,bCsnk90H302Qm=m@sTe0sV0CsXsZs#8U09fH5W13urutuvux0VmFk8bC0~i!0I04.