Aller au contenu

Représentation minimale de Zeckendorf

Représentation minimale de Zeckendorf

À un entier positif n, on peut associer un tableau de bits qui indique si le nombre de Fibonacci est présent dans l'unique somme d'effectif minimal issue du théorème de Zeckendorf.

Exemple : \(100 = 3 + 8 + 89\)

On ne peut pas écrire de somme égale à \(100\) avec moins de termes de Fibonacci.

🐍 Script Python
# Nombres de Fibonacci          1  2  3  5  8 13 21 34 55 89 (144 ...
assert zeckendorf_repr(100) == [0, 0, 1, 0, 1, 0, 0, 0, 0, 1]

La représentation minimale de Zeckendorf de \(100\) est \(3+8+89\),

  • ou sous forme de tableau de bits [0, 0, 1, 0, 1, 0, 0, 0, 0, 1]

Exercice

Coder une fonction zeckendorf_repr qui prend en paramètre un entier positif n et qui renvoie une liste bits d'entiers qui valent 0 ou 1, la représentation minimale de Zeckendorf de n.

  • La liste ne peut pas se terminer avec un 0
  • La liste ne contient pas deux 1 consécutifs.
Contraintes
  • \(0 \leqslant n < 10^{1000}\)
  • 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],59/f!Z78r;nb _o=ylaepcwgu)vd*461z3kRméhtsP(S0+2[j-i:050E0w0Q0v0#0u0R0p0y0u0v0R0R0s010Q0#0x010406050R0B0N0N0v0l0t040U0r0u0B0`0r0n050f111315170 0x04051n1g1q0f1n0 0E0#0D0/0;0?0^0P0#0A0P0u1E0P0Q0}050*0o0u0w1z0=0@011D1F1H1F0Q1N1P1L0Q0l1o0Q0P1R1B010g0,0w0n0v0N0w010/1a0R0x0v0n0^0X1L1|1~1,1T1/1P1=1@0}0a0p0S0l0r0x0r0R0#1d0n0p0(1`0l0l0w0y2l1g230n1o0f1*2y1%1)1(1M0E250^1H0n1;2i1L1w1y0:1S2I0#2K0n0r2O1L0x2r1o2w2y2$101}2m2Q1-2V0l140u0}0p0I2v2*0~2)242,1T2.2:2=0X2^1~2`2w2H012 0v2;040p0K332x0 362}0^393b0p0G3f352*373l2=0d3p3h3r3j380r2/3a2=0H3w2{2+1A2~3B303c0j3G3i3J3k3L3D3c0k3P3y3R3A3C3m0e3X2|3Z3t040I0V3(3I2R3!3M0I2@1h2_3x3)3;3+0I323_343{3:2-3T3b0I3e413g3H3s460}0I3o4a3q3|453#4f3v4i434d4m3,3F4p4c3z3~3O4v3Q3}4e3,3W4A3Y4C4s0I3%4G4k3K4s0X3.4M444O3M0X3^2$4q4x4D0X402(1t2!1g2O2B0E1)2G3z0y2W1^1o4,1p4*4(2(4=0(2#4H1-0L0}0(0g3p4w3Z0z2=574B2-0g0}0J2s0L1;0E3B0g0q2r2Z5c511T0|040T5r4N3k0}1f4i583;5u0C0$3/375a3c0p5M5x4T0^0R0E0}015U5I3z5R2=5M0p0M1;0D0r0#1Q0;0p5p0l0O0R1;0*2l0p0N2T0#2:1Q2o0i5i5k5m2n1Q5B4Y5D1-5Y5L5M5U013w5!0p671T53040#564i6g5d2~5A3p6o5s0^0r0}0s0s6s6h0^5_0}4R2(6p0^5u5H4p6f6f6B016j2r0Q0B0l652_6t5y015u0Y0b3w066N6H380}0Z6A6*6w046z6n6O6D046F3`6)6u6+041/0o0q6-5C6*5u0c6.6}0n0}700q0L786Y6:6=2$6X5P016^4X2_6O767f7l6^4%6{5!6O6j0z1D1P7s3s7b0#717e6?6/0}020u0Q0m7i6W6O7a046V347q0}6K4Y6M7x6*7T7c736G6}7r7J797F7H7D3z7h7=3*7:7d5O377-7j7S7`7*7R7K040W7^3}7`7I7!7#7k7E0482348d7?0}0W7Q8h6@0#4f6%6|6Y7T0o2k0R871-7@7.6Y6!7|3z6^6`7W750}6$8B7l6:0F8y5t0}5w747/8f8Q6v8k8X7m8p3,8E3Z5F6e7$6}7z7B0w8!7(7G728!6:0h8m2x8i3Z8G8(5E7Y8+7#7y0}6l8;818^7L7N7P987U901-6J938c5N7%0}8v0Q8x8U8C0}0Y9g6q8W9r7l5u8L7 848{3c8o8q6L9k8,8t6r8M376:0!9E8}886 8?8g3g9k809U719W509s04779N4x899a6;9e7c8a836}9P9:9V9v6I0}9*9C8V7)9j8s7l7T9$9S8z0}9Q8!7n8r9K7l6Q0)6T7V8|9Z9o9q660f4~0w2y2Zar4+1x4-2B2E2z0v1Oau0f4,0 aE0)0+0-04.