Suite de Fibonacci (3)
Définition
On rappelle que la suite de Fibonacci est définie par
\[F_n = \begin{cases}
n & \text{si } n < 2\\
F_{n-1} + F_{n-2} & \text{si } n \geqslant 2
\end{cases}\]
On a le tableau de valeurs :
| \(n\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) |
|---|---|---|---|---|---|---|---|---|---|---|
| \(F_n\) | \(0\) | \(1\) | \(1\) | \(2\) | \(3\) | \(5\) | \(8\) | \(13\) | \(21\) | \(34\) |
Formule efficace
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}\]
Exercice
Coder une fonction récursive fibonacci qui prend en paramètre un entier n strictement positif et qui renvoie le couple \((F_{n-1}, F_n)\)
- Contraintes
-
- \(0 < n < 10^7\)
- Code source limité à 2000 caractères
Méthode appliquée à n = 9
- L'appel
fibonacci(9)souhaite renvoyer \((F_8, F_9)\) - \(9\) est impair, on va demander \((F_3, F_4)\), on pourra en déduire \(F_7, F_8, F_9\)
- On appelle
fibonacci(4) - \(4\) est pair, on va demander \((F_1, F_2)\), on pourra déduire \(F_3, F_4\)
- On appelle
fibonacci(2) - \(2\) est pair, on va demander \((F_0, F_1)\), on pourra déduire \(F_3, F_4\)
- On appelle
fibonacci(1) - \(1\) est le cas de base,
fibonacci(1)renvoie(0, 1)directement. - On applique alors les formules.
- 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)pour \((F_1, F_2)\)
- 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)pour \((F_3, F_4)\)
- On déduit
- \(F_7 = F_4^2 + F_3^2 = 13\)
- \(F_8 = F_4^2 + 2×F_4×F_3 = 21\)
- et de plus, comme \(9\) est impair
- \(F_9 = F_8 + F_7 = 34\)
- l'appel
fibonacci(9)renvoie(21, 34)pour \((F_8, F_9)\)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
.128013 x,59/f7}8rnb _o=ylae{%pcwgu)*vdV46F13kRméhtsP(S0+2-i:U 050F0u0R0t0!0s0S0n0y0s0t0S0S0q010R0!0x010406050S0B0O0O0t0k0r040V0p0s0B0`0p0l050f111315170 0x04051n1g1q0f1n0 0F0!0E0/0;0?0^0Q0!0A0Q0s1E0Q0R0}050*0m0s0u1z0=0@011D1F1H1F0R1N1P1L0R0k1o0R0Q1R1B010g0,0u0l0t0O0u010/1a0S0x0t0l0^0Y1L1|1~1,1T1/1P1=1@0}0a0n0T0k0p0x0p0S0!1d0l0n0(1`0k0k0u0y2l1g230l1o0f1*2y1%1)1(1M0F250^1H0l1;2i1L1w1y0:1S2I0!2K0l0p2O1L0x2r1o2w2y2$101}2m2Q1-2V0k140s0}0n0K2v2*0~2)242,1T2.2:2=0Y2^1~2`2w2H012 0t2;040n0L332x0 362}0^393b0n0H3f352*373l2=0d3p3h3r3j380p2/3a2=0I3w2{2+1A2~3B303c0h3G3i3J3k3L3D3c0j3P3y3R3A3C3m0e3X2|3Z3t040K0W3(3I2R3!3M0K2@1h2_3x3)3;3+0K323_343{3:2-3T3b0K3e413g3H3s460}0K3o4a3q3|453#4f3v4i434d4m3,3F4p4c3z3~3O4v3Q3}4e3,3W4A3Y4C4s0K3%4G4k3K4s0Y3.4M444O3M0Y3^2$4q4x4D0Y404Y4w3*4#494(4B4l4V4h2(1t2!1g2O2B0F1)2G3z0y2W1^1o4_1p4@4=2(4 0(2#4H1-0M0}0(0g3p4)3;0z2=5h4.2~0g0}1/0m1e0t0y0y0!5m5b1T0|040U5y4N3k0}1f4i5i1-5B0C0#3/375k3c0n5T5E4T0^0S0F0}015#5P3z5Y2=5T0n0N1;0E0p0!1Q0U0J0o0v2m0Z2?0i0c0n5@5_0i0C5%3Z5)5S5+5+0(0B0b0n2V0O0m2r0.2o0J0!5s1=5v0!1`0l0S0P0y1c0!0g0S643;66685#013w685K1T5d046w3p0n6H5G045I2$6N5n0^0p0}0q0q6M6O010O0!4f5V375B5O4p686G6U016J2r0R0B0k6R2_6T5z0^5B5D5J6;6%0}4R2(6;5B0c6!736(3,6*3z5M6F5+6#6J0u0-0u7f3Z6,7i6/6}5F380}0M7b6~016W046Z4i7u5W7w6Q7z7v7C0f0f7K7H74044%3`7t5U6;0y0K0}030n0B0n0q5 0o0U0M0Z0K636.7V6#7Y7!0n1y7)5@7y7;7t6#0l0}0B7p3;797P3s0}0E873z7C7E6S805q6l5t6o845L0}71777A81047}8p7v7h4p067V7G377@047#0$7(7*0U0Y7-7/7s6/8g040$8b3Z8d8R3}898U1-7C0D8X2~8W7F8A8c0}0X6M8)3*828#6V0}8!7F8O837~8N7X7Z8D0n0G8G5@8J8M6:8q0}0G8;7B6X9a8r8a8^6;8Z9d8%6S8.3;7C8,8(6#7R7T349m8Y8?9j048`8f9h9x9g97049f4Y8y7=6;6J6L9E7v8r6{9u6#7C0w9a9s9a8d8e6|9r7d762_6#7r8{8z7?8~7#5?7+8J7.0C5~930M7:4Y8z967v6?0)6_9R2x9v5A8n8l8$8Pa96 0}7a9O7H8r99727A8w9}9K7A7l7nac019+an9~a60^8C9:9`9_9=0M0X7/9|7Uawax6=0}6@a39a70asaias86ag88abaV8*049p9B9Faj8u7Ham3`1g580u2y2Za/4^1x4`2B2E2z0t1Oa=0f4_0 a 0)0+0-04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)