Aller au contenu

Évaluation d'une représentation de Zeckendorf

Représentation 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\)

⚠ 0 ne fait pas partie des nombres de Fibonacci utilisés pour la représentation. Les nombres doivent être distincts.

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

Évaluation d'une représentation

Réciproquement, on peut évaluer une représentation sous forme de tableau de bits.

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

Exercice

Coder une fonction zeckendorf_eval qui prend en paramètre une liste bits d'entiers qui valent 0 ou 1 et qui renvoie la somme des nombres de Fibonacci associés aux 1 dans la représentation de Zeckendorf donnée.

Contraintes
  • La longueur de la liste bits est inférieure à \(10^4\).
  • Fonction récursive interdite
  • Modules math et functools interdits
  • Code source limité à 2000 caractères

👍 La fonction acceptera les représentations minimale, maximale ou toute autre valide.

###(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 : ∞/∞
.128013x,59/f.qZ78rnb _o=ylaepcwgu)vdM46F1z3kRméhtsP(S0+2j-Di:E050E0w0R0v0$0u0S0p0y0u0v0S0S0s010R0$0x010406050S0B0O0O0v0m0t040V0r0u0B0|0r0n050f13151719110x04051p1i1s0f1p110E0$0D0;0?0^0`0Q0$0A0Q0u1G0Q0R0 050,0o0u0w1B0@0_011F1H1J1H0R1P1R1N0R0m1q0R0Q1T1D010g0.0w0n0v0O0w010;1c0S0x0v0n0`0Y1N1~201.1V1;1R1@1_0 0a0p0T0m0r0x0r0S0$1f0n0p0*1|0m0m0w0y2n1i250n1q0f1,2A1)1+1*1O0E270`1J0n1?2k1N1y1A0=1U2K0$2M0n0r2Q1N0x2t1q2y2A2(121 2o2S1/2X0m160u0 0p0J2x2,102+262.1V2:2=2@0Y2`202|2y2J01310v2?040p0L352z11382 0`3b3d0p0G3h372,393n2@0d3r3j3t3l3a0r2;3c2@0H3y2}2-1C303D323e0k3I3k3L3m3N3F3e0l3R3A3T3C3E3o0e3Z2~3#3v040J0W3*3K2T3$3O0J2_1j2{3z3+3?3-0J343{361t2$1i2Q2D0E1+2I3B0y2Y1`1q481r462*432z054e0*2%3!3?0M0 0*0g3r3J390z2@4y3S3 0g0 0K2u0M1?0E3D0g0q0w0D3c4D4s1/0~040U4T3~2/0 0o2m0S4Z3=4V0 0C0%3;4A2@0p4?4*390S0E0 014}4:3B4`4=4?0N1?0D0r0$1S0u000P4R1d0v2n2p590v0p2t2#0P0S1?0,5g2q0j4J4L4N4 3#513e4?5B4?0v0D2u0p0?5H0$0S0R1S2q4%0R0:4M0n0n0P0w5x3?5z5C4}013y5C4z3B0n0 1;0o0q0Z4^3B4W0c3r0p5)3,5,0$5.0M5^5`3?0r0 0s604E1/0O0$0 3`2*671V5?664U1V690 422(065(6e3m0 0S0r155W4m3e611/6304656x5_6q016k043:6x6o5B6z1V4u040g3D6h4!304$2m6U4+1V0r4B042V6Z3u6X5Q5;3#4W4/6L5C6p6i0`6Q0$4x6E6O6r045P6*3B6B0s6D2(6F6^6H6a3.6.3?6:5%6?7h6~3a6s6u1_723#6B0X762{786V6 5-5/7g7i6G5+6R5}7y6x7j6g6}7B5|5~7o62647N4#7D7M7G6G7I777j7C7x5:7J797q7Q6W7S0q5 6=6N6G6Q2t0R0B0m1h7$7v7k046t6v3I0f4p0w2A2#83471z492D2G2B0v1Q860f48118g0+0-0/2|2Q390v0E0O1g2m0$1g0p0z170n2V0A0 1o8p8r8t2n0!0|0R1%040#0P0y3c0v0A5N200:5I132m5N1S0I5}1g0v0y0y0$1t2|0B0u2|1J040(2o161,0P8_0$0i0B0w0S0c0p0+0p2j7@5h0p2X0O0o2t0B5o0:0m0-6t0n5R5N1z5K5}0.2m0P928X0B8Z988$0o8(8*0$1|6v0n0y1S5E5G7j172m0Q8_0w0b0 090U0I0q0W0p0s0p0W090C3r929K0m9M9O9Q049S9U0J9X2^9#9%7u6!0`9L1,9,9R9T0q0Y0s0J9@6x920ha89_8p9*9}5f9P9 9U0d0s0da52(0h1i8=118=8@0p2V6S3E0|8~0w92960m2p000v1e2t9g9i1g910p8w1)0r0B5F95176S5K5H5j8Y5M2p8P3c5V929I0yaa3B9|9Nae9-9/9V9=a49$6xan0fap1i8/2|1p0#8V6FaO0n0A040RaPaZ9G1#1S5o2v8v7_5L2hb504922X9e0p0g0wbj0:0B2o0Ea#0?8T0p130x0x0u8{5p0-2t0h0p0-9k0$aA1d9l0p0K0P2hbm9C2qbu93bvaP1Q1ga`1w1r4r7{a-9~9.a09W9Ya@9^9)9+a/ag0q0J0s0Yal2{9(6Gb-b`b/9Ua20Lc036c279c45Ma:a00Lajca2za7a88-1o040F9i99aP0:1 0m1Rbs0pb80B0ZaP0mbQ12b4b69a9c909x8%1@9B2xcI3e942X2o1 bQaY1SaB0p5c8ZaC1R0:4e0n0g9ebg0Sb(a 8Nb2c*bKaGcMbe2naLbncv17cyaK98cHbjb69u8ZcRd73ea)aWa!1;8A5g4e2s2uaZ0U8_0Q8{5f8}8 0Cc=8i48.