Aller au contenu

Le mot de Fibonacci

Définition

Le mot de Fibonacci est une chaine de caractères infinie. Elle se construit par récurrence :

\(M_0 = \texttt{"0"}\), \(M_1 = \texttt{"01"}\), ensuite, chaque terme est la concaténation du précédent et de celui qui le précède.

  • \(M_0 = \texttt{"0"}\)
  • \(M_1 = \texttt{"01"}\)
  • \(M_2 = \texttt{"010"}\)
  • \(M_3 = \texttt{"01001"}\)
  • \(M_4 = \texttt{"01001010"}\)

On constate donc que pour tout \(k\), \(M_k\) est un mot préfixe des suivants.

Le mot de Fibonacci est la limite de cette suite. Pour obtenir au moins les n premiers caractères, il suffit d'avoir un terme \(M_k\) de longueur supérieure ou égale à n.

On pourra vérifier que ce mot commence par \(\texttt{"010010100100101001010"}\cdots\)

Exercice

Coder une fonction mot_fibonacci qui prend en paramètre un entier n et qui renvoie les n premiers caractères du mot de Fibonacci.

Contraintes
  • \(0 \leqslant n < 10^6\)
  • Fonction récursive interdite
  • Modules math et functools interdits
  • Code source limité à 2000 caractères
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
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
Évaluations restantes : ∞/∞
.128013],5/fr;nb _o=ylaepcwgu)vd46F13kRmhtsP(S0+2è[i:050z0r0J0q0T0p0K0k0t0p0q0K0K0n010J0T0s010406050K0w0H0H0q0g0o040N0m0p0w0/0m0i050e0_0{0}0 0@0s04051f181i0e1f0@0z0T0y0%0)0+0-0I0T0v0I0p1w0I0J0=050Y0j0p0r1r0*0,011v1x1z1x0J1F1H1D0J0g1g0J0I1J1t010f0!0r0i0q0H0r010%120K0s0q0i0-0Q1D1;1?1!1L1%1H1*1,0=0a0k0L0g0m0s0m0K0T150i0k0W1/0g0g0r0t2d181{0i1g0e1Y2q1V1X1W1E0z1}0-1z0i1)2a1D1o1q0(1K2A0T2C0i0m2G1D0s2j1g2o2q2U0^1=2e2I1#2N0g0|0p0=0D2n2Y0?2X1|2!1L2$2(0=0Q2,1?2.2o2z012?0q2)040E2`2p0@2}2;0-30320A352|2Y2~3b0=0d3e373g392 0m2%310=0B3e1j2S182G2t0z1X2y3o0t2O1-1g3z1h3x2W192-053F0W2T3n1s1L0F0=0W0f3v383U0-0u0=0k3!3T2J2 0f0=0H0m0J0l1%0j160q0t0t0T3+2:3$010;040M3 2Z410i0=173N2{2/473-430x0U3l0k4l3*3#3-0K1_04010G1)0y0m0T1I1H0$2e2R0r0H4y0g0$0t0}3{0J0R2j0$0z0w0k3;0J2f1I0C0T3_1*3|0T014k4m4e3h0=0q462~430c3e4n3,2#0=0j4=4*3o0m0=0n4{4o1#0K0D0=000O004.3o4:514@1L54560O0D594c364m4?403-3W040u1v1H5d5p2#0j0=205a4143455l3S5x2=4_5C4g0=0x5w4f1#4~04020p0J0h5P4+044b2W521L434j5G065n5n4|484,5L1#5c5G5o5Q5J044`5^5/3-5S505~5%3a5K5G5 5?0=4;635e655|5Y4}0=0P6g5:044-5+5.64015r2j0J0w0g5#2-5_5Z5}5$6d420=0S5*6C5I6e6x4d6q430b3l183Q0r2q4D2q3J2r3B182u6!0q1G6T3y1p2.0e0W0Y0!0K04.