Aller au contenu

Représentation minimale de Zeckendorf (Performance)

Représentation minimale de Zeckendorf

À un entier positif n, on peut associer un tableau de bits qui indique les nombres de Fibonacci présents dans une représentation de Zeckendorf de n.

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

🐍 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 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]

Dans la représentation minimale de Zeckendorf,

  • La liste ne peut pas se terminer avec un 0
  • La liste ne contient pas deux 1 consécutifs.

Il n'y en a pas d'autre avec moins de termes.

Exercice (performance)

Coder une fonction zeckendorf_min qui prend en paramètre une liste bits, une représentation quelconque de Zeckendorf et qui renvoie sa représentation minimale.

⚠ Les fonctions zeckendorf_eval et zeckendorf_repr sont disponibles pour les petits tests, mais impraticables avec les nouvelles contraintes. À ne pas utiliser dans le code !

Contraintes
  • ⚠ La longueur de la liste bits est inférieure à \(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]59/f.Z78r;nb _o=ylae%pcwgu)vd461z3kRméhtsP(S0+2[-i:050E0v0P0u0Z0t0Q0o0y0t0u0Q0Q0r010P0Z0x010406050Q0B0M0M0u0k0s040T0q0t0B0^0q0m050e0 1113150}0x04051l1e1o0e1l0}0E0Z0D0-0/0;0?0O0Z0A0O0t1C0O0P0{050(0n0t0v1x0:0=011B1D1F1D0P1L1N1J0P0k1m0P0O1P1z010f0*0v0m0u0M0v010-180Q0x0u0m0?0W1J1`1|1*1R1-1N1:1=0{0a0o0R0k0q0x0q0Q0Z1b0m0o0$1^0k0k0v0y2j1e210m1m0e1(2w1#1%1$1K0E230?1F0m1/2g1J1u1w0.1Q2G0Z2I0m0q2M1J0x2p1m2u2w2!0~1{2k2O1+2T0k120t0{0o0H2t2(0|2%222*1R2,2.2:0W2?1|2^2u2F012}0u2/040o0J312v0}342{0?37390o0F3d332(353j2:0c3n3f3p3h360q2-382:0G3u2_2)1y2|3z2~3a0i3E3g3H3i3J3B3a0j3N3w3P3y3A3k0d3V2`3X3r040H0U3$3G2P3Y3K0H2=1f2@3v3%3/3)0H303@323_3.2+3R390H3c3 3e3F3q440{0H3m483o3`433Z4d3t4g414b4k3*3D4n4a3x3|3M4t3O3{4c3*3U4y3W4A4q0H3#4E4i3I4q0W3,4K424M3K0W3?2!4o4v4B0W3~4W4u3(4Z474$4z4j4T4f4+4F4-3S0W4m4:4L3Q4N4s4_4R4{4T4x4~4p4T4D534Y4N4J574(4q0J4P2$1r2Y1e2M2z0E1%2E3x0y2U1?1m5k1n5i5g2$5q0$2Z4;1R0K0{0$0f3n4%3/0z2:5I4,2|0f0{0I2q0K1/0E3z0f0p0M2R5N5C0?0`040S5$4`360{0n2i0Q5,4 015)0C0!3-355L3a0o605?350Q0E0{01675|3x642:600o0L1/0D0q0Z1O0/0o2p2X0N0Q1/0(2j0o5!0m0Z2.1O2m0h5T5V5X2l1O5:0P5=4Q63655 6067013u6d0o5J2+0{6v0Z3n6T5O0?0q0{0r6Z6U1R5)0X0b6R6d6+3i0{0K6*6#016%046)4g6!5%015!0{5f3^6S6=5.046H6J2$6`6|0g624v0{0u0x0x5V7h3X5)5+4g7873047532785_6:616`5E040f3z6_710m5/7H5-0q5~5#6 787J7a5;7o3/5)5{4n6S777C0{0Z5H7Q6`7S0n7L5@6|0r6~2!705-7u4V2@7y0{7Y4W7!807@5@7S6^7*716|0V7=2@82357_7A7!787D0v0+0v7V1+7X8f818c3x7D7(7.3q6@8v3x6|0w8y3X7u4#8b787:8a328r8D0Z4d8m6,7}8p8q6;7+6W2R6Y7s7e0{7g8Z7I7j7l7n8%5-7q8P0?8e8,5@7z7Z8T7B8(04857?8H0{0e0e8J2v8L3/8E8S808h7%7)8~8V8|8C3/6|020A0P0l9g1+7u7w2v7|047~768_8g9e6X8/6{8#9A7S7k7m0m0E9A8.8=8d8N7v9J0{0C988T7R8W6w9A7f9D8)9G9I9L3x9K7d719p9P049R8^9w8U717D7F0k9n2|0{0p9`6$7O1d865-0m0n0{0k1|0A8l9%7p0{7r9*a38xa27/0{0Y9~729N7`7x6`5_9u409;8q9U049zab9h9CaA6V049F8+af8?ad9A8;aI358@7 av999y8X9XaCaN7iaF8*9H9-ae7{6`9,aD8Q9.9Saw9e8}8G8!6}amaM9v8_9a048j6q9-at3eaR8`agayaUa+6$aWa(8{aGa#b85^aKbfa*aXaca-9:avaxa;8K8 a@ai9M748fax7baV048$bk3{0{2f0xa$9/aQb45@8t9ca=8{bq94bs9j9la^9N9q5B8-8Rbn7#8{azbD1+9Ybf9Ea!9$b*a,a%aq9+ao9-bJa`951+8i8kb09Sa|1Q0v0k0Pam7Sb)bb7Mbab@b5bGbIam8IbWbwbna|2p0P0B0ka19db(b74$0e5z0v2w2Xcz5j1v5l2z2C2x0u1McC0e5k0}cM0%0)0+04.