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 : 5/5

.65038.9875.128013.9888lS^te-UdA5f18%umaèg,_F/R=V{in 6@)yàqPhcDL\(bùsx.p;r4jC'90"ov+w73Ok:é *}2I030f0c0b0o0z080R0;0K080o0R0R0w0%0b0z0U0%020B030R0m0n0n0o0W0F02090'080m190'0A0;000o0n0U0V0;0v0c1j0W0H0m0c0R030u1g1i1k1m1e0U02031R1K1U0u1R1e0f0z0(111315170J0z0q0J081+0J0b1c030|0P080c1%14160%1*1,1.1,0b1@1_1=0b0W1S0b0J111p0R0U0o0A170@0%1{1(0%0i0~0c0A1x0c1=2e2g2l1}2o1_2r0n2t02060;0I0W0'0U0'0R0z1s1u0`2c0W0W0c0K2O1K2v0A1S0u2a2!2729281?0f2x171.0A2q2L1=1!1$121|2-0z2/0A0'2?1=0U2T1S2Y2!341f2f1u2^2m2}0W1j081c0;0j2X381d372w3a1}3c3e3g0@3j2g3l2Y2,0%3q0o3f020;0,3u2Z1e3x3o173A3C0;0X3G3w383y3M3g0h3Q3I3S3K3z0'3d3B3g0C3X3m391'3p3$3r3D0+3*3J3-3L3/3'3D0k3?3Z3^3#3%3N0#3~3n403U020j0$453,2_413:0j3i1L3k3Y464e480j3t4j3v4l4d3b3`3C0j3F4r3H3+3T4w1c0j3P4A3R4m4v424F3W4I4t4D4M493)4P4C3!4o3=4I1V321K2?2%0f292+3!0K2~2D0_1#1S310c333k3Q034-0`4^4K1}0.1c0`0i3Q0;4W470i1c2o0P1t0o0K0K0z4`3@4e1b020O5i3 4n1c0A5o4 175l0E0/4c3y0*3g0;5D5t4u1}0R0f1c001G0'0b0V5L0m5N5P5M5O1C0A0(0'0z1`0O0t0s0y1u0d3h0?0r0;5%5(0?0E5z3!5I5C5D5`0;0`0m0S0;2}0n0P2T102Q0t0z5c2r5f0z2c0A0R0:0K1r0z0i1J4V5j2m5^3D5`5Q5S6s5O6u0V3X5{574e0K0j1c0111145|1`0P140c6y5`6A2m51026j556P3p5r6U6n1}0'1c0w0w6Y5p2m0n0z4F5F3y5l5y4P5{6z6Z176R2T0b0m0W5s4I566^0%5l5n4!726+1c4b766)1}5l0r6(5u0%78496.3!5w3X0B6@7c176C6E6G100q0:0A0:0W3B6N5E720A1c0m7l407e7g5G3L1c0(7M3y6#026'706V7O025b5d6b7J5k1c75367F6X7b7h7T0u0u7%6*6,024q7*7r731c5=70717{7t026F0m0;0w5.0s0O0.0d0j0E0;0{0;1$875%0.7D807h826F0K3B6h086I0;858j890@8b8d8f0b8h86888A8m7X3z7P7_3k8n7N0%7T7V348P3T7P7R3!7T0=8Y478X6=6O7+027I7-8Q7L7W8*7Q8:7{8S8$5q020(8N3v8V8Z1c0)8_3b7H7=6!1c8#8-8W8+965v1c7f8?7h7G8{8}2Z8 407T929h8Q7j9l4~8Q8!9d8L9c9a9002997`9i8'347p8)7{6R6T9r9b6 8U8K7T0l931}9t9V178S8T8O8K7j7a9F8.1c6;8U9n6B6D830;2T5X5Z1`0f854-0m0U1_0;5$8z8B0E5-5%8A7~9I6?9K7h6`0{6}9Q9$72749y9j8,9)6/9f9Y9z8=an7m7}8J729M549O4X7,9R729Taq9XaA9o6$9#8~9%7@4iat7K9+559.2m8p9=2q5Y5!5|9{0'9}9 a18Aa5a20)8da84kaa7E9L1c6{afaqaj9B8%8{9y8/aD7{alaq9paq9jas4_aiav4V0u4|4@4#bf0u4'1K0b4)bk2)2#0o1^bh4'1Q9v3y2T0n0s0i0o0.0c0s0J0,1c1C1E1G1I0;9,4_1X3l1R096c1taX0q1k2Q1_102J7A0o2O109|0b0c0m0R1I5-0~0;0R0!0o0q2N8w0A0zbK2C0A8E0`100n0m08199~0z8rb'8fb 2T6I5~0;0q7B0A0f1061631I0T0;0^8u0Fcb0;0o0;275Z100G110J0obK0;0icz0;1G0!bUbAb_0m1u0o0U0U0c8u0W6g6}2M0i0T1VbQ020-1u7BcScU9 cF9 cmcd2QcH0zb!0Q0;bUcT1r5|1#c@0c0Wb`cb19d10;2fd25}5 1I8EaY0z2I1u0RbU080'bW0W2N0J2Ccu6Kb-0;0@c#bPbu0M1`b)8v4{4.7Z687#5g0O0A7~be3Ddc5|1t0Kcb0(dfbU8K1kdo1jb*0S1c0N0O0,0Ndk0qdJ0E0Na/8~c3c51a1.c90z1t102q271`ch2gckd45!0W0Rcp0Z0!dO2/231Dd|d71qd{0i2o8r0K1`cKcP1`0n0:2a4.0;2Nb$190(dA3-b|1HcJ0m6ccN8EdWdn2adZ0cd#02d%0Ad.550o0f1!cad|cdd cjd{b e3e5c$1e0J0jet0f7s8sc40d0n2~c40}2T1=0z0n0qcvc517072k3!0b0*1D0'0Y6,b;0W0K1)230U0R0/7:0K0f0A0T0Y5IcU1#0W0Tea0u1,0u0Y0`0KbC0f2#f4e;f70D0j0h0T0$0T0,0u1|0{0R1L0(0q0u0@0C0ofJ0RfR2k190b1_170/0*1kb{0A0q0/2k0u3D0Ze.8ue;9`13df6Mcw3!0J0ceSd12.510;0J2T0i17018r088te:e=f`e^cx2Nf%0%0Id11j2|8Eg31c05041K0o2!e)3l1^0'fy5U4@bu0I1kb@c*f d7a%d2bZ0;0:080pexe!0;dZ0Jd{0ScT0Wb*b!852qd7cW2f5-a%gL6}0;gO2qb-1+2rb 6l1Y1KgAgC5Rb*c%1o0mexb g,dh0!2{0b7A1Idt0o85cW1gc5b%5|0!enc`0Uevd_1uf^c40'aU1}dXeJb%eLd$0O0neQ700'c_eHdYhzeMd%hDd/9mdOcPe2d61G6cd5b 5|2g10hR0`6+ge8E1j0K1*2/a0hIhyd!hBhN55dOhe156cd8c?h!1uc:1`4?6+d10Ecp0L1`dig#el0mhl1u31e=b_hWdd0A4-c;hZd34-b 2qb+d91`13cx0}089 0ficgV5NgV5eh+0ccpc(d7b+8E3B3$10cNcdhmcW9`2VhqiBf_huh.dphKh;hE8U8g270o0(iw1_d2cPeAechXhsdkhv17hxi!h:eNhCi%3kdwg{1R0gebe#1t5-ek5g60e80R8Ei+13breCi0gMg:bLb#7BcaizeSeUhq5-dib,i)iUbU8gd;c6d@b%hqcp0IjkgO2?c@hq0Rj8jc8E0P5!idefcx2U0Jb{bK0Tj!e'1T020x5ZjaiMe4b`1`exe4iV2QdD4}7!6a5g1KdMeCh`9?2+hRd81x0pd}b;9}9~0:b~0|f{i^0%i`eKhLi~hO3D9 i?hu9`9=0:hh0|iLj59`j13l2?3yeSe;b{2OhYf,d11c1Qkz0fkB2Nhq0df#2502i6cf2Kh910b*h*jY1Hg`c%dz109~b,cvj/19cl5Nd11tc0b+5 h*2LbL6;g{c43l1.6S8ubAc}cFiZkgi$kjb;5Zgq0:0q0pbxedk(k'0{b_c.cwe;kM0:hkhRe;h(iE2{iG2GjU316gc@k9d|b/5gb/l0he8El372kfi#i}0,0n0a0@i 8~hWh,0fimlqiCh)iFdwk~1ek~l4lMhMlShPjdd3d|e360bU0Ac48D56k|l'0z022Kg/l)i|hM000q5O0jl,02h6cv56dMe*0lgVj{dEj}8fl.lb3B0;cBj?4@4idM1Kl%03k~1jc@kE109 7Bcd8rc^kdlLm2hC0wm7kjmacwmq490;mf0nmh4}gPbW8umpdM7amt0umvk~ek8Ea%1^6chQh,jvfa9_e82Sir5|gQc8hzmul}l|02cr601`l1c0dQd76H6gdncdmq3y1 1-1/1;bv3!ad6|6~aGaO4`bdmiheg:5!85j=bene1/211:2ua?02a^nnaI4e7jaPah8@1c9UnI9402mU4!nr4}m~3l0ul{nX1enZ08nYbt4:2@40nfnBni8K2z2q2s1c2F090Kdn0U8E0I0Ferag3v1T4$364!mtax520cazb19i59dF695ej`a|7'5makaCb97{b0nM9GnSa 7}bN4s8K5B6q5Eoj6o5J026woG5U0V5WaZ5#5/0A8c5,885:8eh*5elYiXmg6m7{6pa;ce5 h 651`67og6b6d6f6h196k5?40o#6roIoHg 6x8(a=8o9:8q6H2Qds6Mo~kdayb6onaMaEaKno6-oC7daSp77qaca@aenHoc9*olph179'oum9pf7kpt7|02kj0B9Jo 8QaWmFcg7yb$08awb295pAoqpcpPa~nQ977UpaofdH5hpR7(om02o12Z9S1c7:9yaHaQok9gpq9bnTp;2m7np78Kb3p%pxpW7Yb8pT7.6$a`p'pAb79y9xqa9Hor9w91pZamooq69Dp(qko2bapCqcnOp(p_qlprp?qgaopsp`6WpVqD9Z98pw7)qx9bq49mp,029qp@3!p:qL9C9EqVa}qpp+qr0EkjqPnPqG9zqw4spl8Qp9q29zp*3Dq(py9ukd9!py9(qYokow3Ho$8Knla_q;a{q*p q*pSqO8;pwpDq.3yq:qSa}q?q{quq;qUq5qh7UaLrd7{nKpwr11dr3o8nFporm8Kr8q nRqNnjaRq1rkokqKqqpUq!rL4eb5qeqFrIpiqspAaFrXq,q#opbb9ImVbh4?2!n)1R0e1ub*8unyg!2Ck;6Ggcc4d6bA5g1_kajl100#6I6~e$cC6j0i64dClKeIi{hAi}5/4a0a0y0j0C0?0?m8e}iNeCb?exdRhmeper2Qeujo1#ey1|i:lFcGhe0f7Bb_lgnvj,6+ix0zbX65b?0A7zbL2Qgb8tj!kw1Z1#nz20nhnD7hn;2B2D2F0Zd`1p1`n~o04`r/3+354_o77{0q5lm46vm55Pta56rX0i0s0A0nnLrR7hrcq@8*tfrFpdpYq;9jj^ohp$rbq9q*nKq~tkrs0=qXtD3ynK4UtyrNqAqTaOtCr)qmtFp/7@44q0pD8Kt65Ktat8tb5Otdr95atgo?4e0q7T0h0C0$0h0X0C0k0+4Or,nVr.4$bi4;bu0g2{2MmHsil5sl5'snspsr0?8G0Nfi5N10t;t?t^t`0hm8j$bi0{iw0R02.