Aller au contenu

Ajouter un à une représentation

Le cadre

Une représentation de Zeckendorf d'un entier est son écriture comme une somme de nombres de Fibonacci distincts.

On souhaite ajouter un à cette représentation.

S'il était absent, aucun problème... Sinon, il faut travailler.

On pourra travailler sur la première tranche remplie de uns. Cette tranche a probablement une écriture minimale plus simple afin de pouvoir ajouter un.

Exemple

  1. Si on prend une représentation de Zeckendorf de \(100\) : [0, 0, 1, 0, 1, 0, 0, 0, 0, 1], et qu'on ajoute un, on doit obtenir \(101\), dont une représentation possible est [1, 0, 1, 0, 1, 0, 0, 0, 0, 1].
  2. Si on prend une représentation de Zeckendorf de \(14\) : [1, 1, 1, 0, 1], et qu'on ajoute un, on doit obtenir \(15\), dont les deux représentations possibles sont [0, 1, 0, 1, 1] et [0, 1, 0, 0, 0, 1], en effet
\[15 = 2 + 5 + 8 = 2 + 13\]

Exercice

Coder une fonction zeckendorf_ajout_un

  • qui prend en paramètres
    • une liste bits, une représentation quelconque de Zeckendorf d'un entier \(n\)
  • et modifie en place bits pour obtenir la représentation de Zeckendorf de \(n + 1\)

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

👍 Toute représentation de Zeckendorf sera acceptée.

Contraintes
  • ⚠ La longueur de la liste bits est inférieure à \(10^5\)
  • 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)vdM461z3kAméhtsP(S0à+2j[-i:050E0w0Q0v0$0u0R0p0y0u0v0R0R0s010Q0$0x010406050R0B0N0N0v0l0t040U0r0u0B0{0r0n050e12141618100x04051o1h1r0e1o100E0$0D0:0=0@0_0P0$0A0P0u1F0P0Q0~050+0o0u0w1A0?0^011E1G1I1G0Q1O1Q1M0Q0l1p0Q0P1S1C010f0-0w0n0v0N0w010:1b0R0x0v0n0_0Y1M1}1 1-1U1:1Q1?1^0~0a0p0S0l0r0x0r0R0$1e0n0p0)1{0l0l0w0y2m1h240n1p0e1+2z1(1*1)1N0E260_1I0n1=2j1M1x1z0;1T2J0$2L0n0r2P1M0x2s1p2x2z2%111~2n2R1.2W0l150u0~0p0I2w2+0 2*252-1U2/2;2?0Y2_1 2{2x2I01300v2=040p0K342y10372~0_3a3c0p0G3g362+383m2?0c3q3i3s3k390r2:3b2?0H3x2|2,1B2 3C313d0j3H3j3K3l3M3E3d0k3Q3z3S3B3D3n0d3Y2}3!3u040I0V3)3J2S3#3N0I2^1i2`3y3*3=3,0I333`353|3;2.3U3c0I3f423h3I3t470~0I3p4b3r3}463$4g3w4j444e4n3-3G4q4d3A3 3P4w3R3~4f3-3X4B3Z4D4t0I3(4H4l3L4t0Y3/4j1s2#1h2P2C0E1*2H3A0y2X1_1p4X1q4V2)4T4%0)2$4I1.0L0~0)0f3q4x3!0z2?4|4C2.0f0~0J2t0L1=0E3C0f0q0v0Z0r1d0q0B1g4T521U0}040T514?2 0~0o2l0R5r4O0_5o0C0%3:384 3d0p5I5y451U0R0E0~015Q5E3A5N2?5I0p0F2X0$1:1R1=0p0x0=0y1R0=0p2s2!0O0R1=0+2m2o1R0i57595b5_0p5k2%4r5T5O5H5W5W0r0g600p0w0R0Q6c6e0p0u005?0$0w0l5.0w5:5=0n0Q0O5(160p5v0Q5x4N5L0_5U660p0M5f1d1R0I0p0W6i0v6p6r5?0v2v6C386F675Q013x674}3~5u5w5K380r0~0h6,4y0~0v0x0x596;3!5o5q5l5s0_0N0$0~4S2)5m5A0~0C3x066%77390~0$3q0p6(1.6.040s7i7k1U72746$5W7q0_4^040z1E1Q7p7e0n6*6A6{3=5o0!7I2.7g7M5n0~0b7D70017m0s7o4j7j7e7s3-7P78045D4q677d7U7F047h7Z7w7V0~0X7Y2%7!7U7$3_627c7v7E5u7T5z7^7n866D017 7u5J7e7y7A1;8a3t7O7?7e7m020A0Q0m7{2`7}877$752`7@5o7+627-837/7G6B767U7K7(7f7;8N5o7S8n7U7W8k6=040o8e7-7@7:8Z8T878V8)8b8d8,6-0~0#8W3+857Z8w8b0y0I0~036H0u0Q6n1?0n5+8!7.877:7=7|7@7m0#8u358`388.81988b7y5!8?6)8Y6+6 878M9u8b9e8N9k8A7e8R9q7l0~7X9F7r73048z358B0~8D3{8F8f8H9s7H9x8:046:9Y8X2i0x8Q0~0T7a4w0e4:0w2z2!9;4W1y4Y2C2F2A0v1P9@0e4X10a10*0,0.04.