Aller au contenu

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

Voisins d'une représentation

Sachant que pour tout \(n\in \mathbb N, F_{n} + F_{n+1} = F_{n+2}\), on peut souvent, en utilisant cette formule une fois, obtenir une nouvelle représentation à partir d'une première. On parlera de voisin pour une telle représentation.

Ainsi les voisins de \(100 = 3 + 8 + 89\) sont :

  • \(100 = 1 + 2 + 8 +89\)
  • \(100 = 3 + 8 + 34 + 55\)

D'autre part, on pourra vérifier que \(63 = 3+5+21+34\) possède 4 voisins :

  • \(63 = 3+5+55\)
  • \(63 = 8+21+34\)
  • \(63 = 1+2+5+21+34\)
  • \(63 = 3+5+8+13+34\)

On notera également que \(37=1+2+34\) n'est pas un voisin de \(37=3+5+8+21\), elles en ont deux chacune.

Cette notion de liste de voisins est essentielle pour construire le graphe des représentations d'un entier.

Exercice

Coder une fonction zeckendorf_voisins qui prend en paramètre une liste bits d'entiers qui valent 0 ou 1 et qui renvoie la liste des voisins de la représentation de Zeckendorf donnée par bits.

👍 La liste des voisins pourra être donnée dans un ordre quelconque.

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 : ∞/∞
.128013],59/f.Z78r;nb N_o=ylaepcwgu)vd461z3kRméhtsP(S0+2[-i:050F0x0Q0w0!0v0R0p0z0v0w0R0R0t010Q0!0y010406050R0C0N0N0w0l0u040U0s0v0C0_0s0n050f101214160~0y04051m1f1p0f1m0~0F0!0E0.0:0=0@0P0!0B0P0v1D0P0Q0|050)0o0v0x1y0;0?011C1E1G1E0Q1M1O1K0Q0l1n0Q0P1Q1A010g0+0x0n0w0N0x010.190R0y0w0n0@0X1K1{1}1+1S1.1O1;1?0|0a0p0S0l0s0y0s0R0!1c0n0p0%1_0l0l0x0z2k1f220n1n0f1)2x1$1(1%1L0F240@1G0n1:2h1K1v1x0/1R2H0!2J0n0s2N1K0y2q1n2v2x2#0 1|2l2P1,2U0l130v0|0p0I2u2)0}2(232+1S2-2/2;0X2@1}2_2v2G012~0w2:040p0K322w0~352|0@383a0p0G3e342)363k2;0d3o3g3q3i370s2.392;0H3v2`2*1z2}3A2 3b0j3F3h3I3j3K3C3b0k3O3x3Q3z3B3l0e3W2{3Y3s040I0V3%3H2Q3Z3L0I2?1g2^3w3(3:3*0I313^333`3/2,3S3a0I3d403f3G3r450|0I3n493p3{443!4e3u4h424c4l3+3E4o4b3y3}3N4u3P3|4d3+3V4z3X4B4r0I3$4F4j3J4r0X3-4L434N3L0X3@2#4p4w4C0X3 4X4v3)4!484%4A4k4U4g4,4G4.3T0X4n4;4M3R4O4t4`4S4|4U4y4 4q4U4E544Z4O4K584)4r0K4Q5c4H3L0K4W3_4(5i3T0K4$5m4-4T5p4+5s4=5u3a0K4:5x4{3;5p4_5D505F5A4~2^1q2Z1f2N2A0F1(2F3y0z2V1@1n5R1o5P2%4h055X0%2!5y0@0L0|0%0g3o5n1,0A2;5@5t3j0g0|0J2r0L1:0F3A0g0r0E0s0!2i0n0R5|5.010{040T6f5E0n0|0o2j6e5)5}6h0|0D0#3.365`3b0p6C6l5J0R0F0|016J6y3y6G2;6C0p0M1:690!1P0:0p1G0R0Q1P0%0-2q2Y0O0R1:0)2k0-6T6c0x6r5h1,6N6B6C2n6p0Q0-0F1}0-1O0p0B0l0w0y0P6#1P0i6264662m1P1e4R366_6P0p0T0y0x0C0p0!0N2g0l6!6X003A0F2q0D6L3Y7l6P6J013v7m5^2}0|6:2S6?2^0p7M0@0s0|0t3o7T6t6i0Y0b7K6P7U370|0w6E366i0c7Z7+6n040o7?6t7W047Y4h7!6g0L0z0|0q1d0x7/3y7;7{828404862J7)6D6t5:040g3A8c6m0|0!893Y8b807@0|0z8p5J0s6A2S8A3r0o0|1:110x766!8t3:6i6k6s6g7^6}7R337+6i6w8i7m815E8l0!5?8w6t7^8s8,6g7}020B0Q0m8F3y0N0!4e8O1,6i6x4o8$948%5J8)8+2#963r7-8`3Y7}0t7 9a8x7_8 1S918#958$9k8W2w9b3y9g9e3|9d8:5E7}0W9y2,6o9F1S9D9I3j8y9p9q7*8k8r997S9s9L019g9i9U6t8|8~8S5E9o9B5J0z0I0|030p0V9;2=0p0Z8?8^0p1.0=0!1d9O9P9r6t9-9/0p1x0#a76a6ca1a29Q8T7O9W9x9+9c7_6q9m7V0|0hao7,045X0y0uas8Q7D93ae9q9k0Eay0|0Yas8.ai0|0Z9W9$045r8X7#0|7(ak9w7XaO8}3+adaCaEaG04aI9(5JaKaW9faMaZ9%2%aT04aV9j7|aYa/3:aP5l41aCaD8-aha,7:aHaJ8ra)a`9!8;a}a{6gaP5g3_b3957+989Wa.bh9C7X9Z339v3)8H0427a)8Ra@ag04aFb78a6vaL04aNa~1,b0a)924Xbma2a(bIa:04arbX9z042g0ybCaAbTbU7Lb5bGab7Qas7}b!bE8q04777p0n0FbCbabGa)b+blbUbo8I1G9Tbw9VbO9Jbua=aQbR9Wa5049:0I9@9=9_8@0m9|0C2ia0aBb-8j6gck9:a8aa6b8EcxcybWbs8Bbgbeb`8Vb?aqc1avaxb#900|0Tc4b2cyczb`bHb_5J7$c18/cK367}bNc.8{a!aR2w8YaUbLbv9u7+bja$aecJ5Na^a+c)alc-cNcLbMcgb1c_a^bdcba|7~cgbkc!c#d3aS6gc+cV7N04d9dq9)c{cdapdkdA01bQcHb-aEb;6dcQbZc1b|64c0dt9Mc2dR6u04cZ3fb4bF7.dU8vc=3)9HdDajd(b$7`d$0|7=dD7^8zcHc7dvcac~b/d#d-1,9Ybqd*e0ce7~c}3bc a!de5-dy04bSc594dpd}bfdCe5dScPdUb@cS2fcUd7bJ6jdX0}dZc%a)d6d4elc;eE5EaPc^edc*dzen9XcMdibia!dmdYbnb/c(eHeMa*dLeGdx5JdFev8ueNdac/eQekeIeTadejeLe/dMdU7^dOb~dQe+a ebc3e@eXdJ9te_aXe{f19Gb{0yb}b d:6jc1eYe(b8dW8#d`2q0Q0C0l7ieO7^7PdK4u0f5+0x2x2YfD5Q1w5S2A2D2y0w1NfG0f5R0~fQ0(0*0,04.