Aller au contenu

Modélisation en binaire d'une représentation

⏰ : une série de trois exercices utiles et très simples à faire en quelques minutes.

Représentations de Zeckendorf

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

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]

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

Il en existe d'autres, comme \(100 = 1+2+8+34+55\)

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

Le cadre

On souhaite compresser une représentation sous la forme d'un unique entier dont la représentation binaire est le tableau de bits renversée.

Exemples
  • le tableau [0, 0, 1, 0, 1, 0, 0, 0, 0, 1] correspond à l'entier '0b1000010100' qui vaut \(4+16+512=532\)
  • le tableau [1, 1, 0, 0, 1, 0, 0, 1, 1] correspond à l'entier '0b110010011' qui vaut \(1+2+16+128+256=403\)

L'objectif étant d'obtenir un représentant immuable compressé pour chaque représentation. Le choix du binaire est naturel.

On souhaite également la fonction réciproque.

On souhaite aussi une fonction qui renvoie une chaine de caractères associée à une représentation de Zeckendorf.

Exemples
  • # Nb Fib 1 2 3 5 8 13 21 34 55 89 ...
  • tableau = [0, 0, 1, 0, 1, 0, 0, 0, 0, 1] correspond à la chaine "3 + 8 + 89"
  • tableau = [1, 1, 0, 0, 1, 0, 0, 1, 1] correspond à la chaine "1 + 2 + 8 + 34 + 55"

Exercice 1

Coder une fonction zeckendorf_bin qui prend en paramètre un tableau de bits et qui renvoie l'entier dont l'écriture binaire correspond au tableau renversé.

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/fZ78r;nb _o=ylaepcwgu)*vdV461z3kRméhtsP(S0à+2i:050E0v0Q0u0Z0t0R0o0x0t0u0R0R0r010Q0Z0w010406050R0A0N0N0u0k0s040U0q0t0A0^0q0m050f0 1113150}0w04051l1e1o0f1l0}0E0Z0D0-0/0;0?0P0Z0z0P0t1C0P0Q0{050(0n0t0v1x0:0=011B1D1F1D0Q1L1N1J0Q0k1m0Q0P1P1z010g0*0v0m0u0N0v010-180R0w0u0m0?0Y1J1`1|1*1R1-1N1:1=0{0a0o0S0k0q0w0q0R0Z1b0m0o0$1^0k0k0v0x2j1e210m1m0f1(2w1#1%1$1K0E230?1F0m1/2g1J1u1w0.1Q2G0Z2I0m0q2M1J0w2p1m2u2w2!0~1{2k2O1+2T0k120t0{0o0I2t2(0|2%222*1R2,2.2:0Y2?1|2^2u2F012}0u2/040o0K312v0}342{0?37390o0G3d332(353j2:0d3n3f3p3h360q2-382:0H3u2_2)1y2|3z2~3a0i3E3g3H3i3J3B3a0j3N3w3P3y3A3k0e3V2`3X3r040I0V3$3G2P3Y3K0I2=1f2@3v3%3/3)0I303@323_3.2+3R390I3c3 3e3F3q440{0I3m483o3`433Z4d3t4g414b4k3*3D4g1p2Y1e2M2z0E1%2E3x0x2U1?1m4x1n4v2$4t4D0$2Z3W3/0L0{0$0g3n4a3x0y2:4V3O3{0g0{0J2q0L1/0E3z0g0p0n2R4!4P1+0`040T4?4i2|0{4;0Q0R4|421R4_0B0!3-354Y3a0o5d53350R0E0{015k593x5h2:5d0o0M1/0D0q0Z1O0t001/0^0v0k0o1/0o4;1:0Z2p0o1Q0q0x0Z0O0o0W5m3X5o5c5q5q0/0o2p2X0O0R5A0u2j2l1O0h4*4,4.2l1c0m0O1O0u0D2q0o1N0o1Y0v0u0A5G2i524n4W5U5i5W0o5k013u5X683{0{0R0q110v3n0o6h1+0q0{0r6o6q1R0N0Z0{3,4n6g4#2+0{0w0A0Z0;1|0x0v0p0$0A0b6v6E1R6s046u4g6p6T0?6y4d6f5q6w0?4R040g3z6S4@4~040n6:4}0?0q5b4=6Y6*364 655f3x4_586C5X6)6!016,0Z4U6~7a0m4 6^546`6t6X2!6Z6;6#6z3*733X756(78786 7h046k6m7j356V0X7n2@7p6_70046H6J0R6L6N6P6R777y7A6G6I6K0m6M6O0v6Q7F3x6V0C7J327L7k016$043~2!066D7q7b0{2p0Q0A0k1d7f7}7B7D1=3u4o3x6,4T7u3/5b6p4t7g4%044)0x4+0m4-0k4/5H8f4^0{4{8j8671518v550{577x7;350x0I0{030o0F5C2h1c5L5{0x0o0R0Q0s5~6.7$2j2I0t0o0l0o0A2I5}1C2I8H6 6,8082847o7A0n6j108D0?4_8y2$7a7@7_7K6 7-0C7+3(0{0Z9c4Q0{6.0k9g6F049f8z7M4_0c9l6=6@857M6{9e8`987g8}041/105C5*6n9p7=92907N5066947}569t6+9e7e8{7g7i9w7=6V0r7/2v8I3x7@3?9R9q8F3E0f4M0v2w2X9^4w1v4y2z2C2x0u1M9{0f4x0}a50%0)0+04.

Exercice 2

Coder une fonction zeckendorf_list qui prend en paramètre un entier positif n et qui renvoie un tableau de bits dont le renversement correspond à l'entier n écrit en binaire.

Contraintes
  • \(0 \leqslant n < 10^{1000}\)
  • Fonction récursive interdite
  • Modules math et functools interdits
  • Code source limité à 2000 caractères

Exemple : \(20 = 4 + 16\), donc son écriture binaire est '0b10100' la liste de bits attendus est donc [0, 0, 1, 0, 1]

Sinon, on attend que zeckendorf_bin(zeckendorf_list(n)) == n pour tout entier n, puisqu'il s'agit de la fonction réciproque.

###(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.78r;nb _o=ylae%pcwgu)vd461z3kRméhtsP(Sà02[i:050D0u0O0t0X0s0P0n0x0s0t0P0P0q010O0X0w010406050P0A0L0L0t0j0r040S0p0s0A0?0p0l050e0}0 11130{0w04051j1c1m0e1j0{0D0X0C0+0-0/0;0N0X0z0N0s1A0N0O0_050$0m0s0u1v0.0:011z1B1D1B0O1J1L1H0O0j1k0O0N1N1x010f0(0u0l0t0L0u010+160P0w0t0l0;0V1H1^1`1(1P1+1L1.1:0_0a0n0Q0j0p0w0p0P0X190l0n0!1?0j0j0u0x2h1c1 0l1k0e1$2u1Z1#1!1I0D210;1D0l1-2e1H1s1u0,1O2E0X2G0l0p2K1H0w2n1k2s2u2Y0|1_2i2M1)2R0j100s0_0G2r2$0`2#202(1P2*2,0_0V2:1`2=2s2D012`0t2-040I2~2t0{312^0;34360E39302$323f0_0c3i3b3k3d330p2+350_0F3p2?2%1w2_3u2{040h3z3c3C3e3E3w040i3I3r3K3t3v360d3i1n2W1c2K2x0D1#2C3s0x2S1;1k3#1l3Z2!1d2;053+0!2X3R2N010J0_0!0f3X3J3}0y0_0n433|2)0f0_0H2o0J1-0D3u0f0o1D0P0O492@3S0^040R4p3B3}0l0_1b3?2 3A324s0B0Y3Q4q45470n4M4v320P0D0_014T4I4w1)4Q4L4M0K1-0C0p0X1M0-0n4m0O1M2k0m2g0*1O0p0x0X0M1M0T4,001-0?0u0j0n4A2Y3q4J4X4R044M4M4T013p5c48442)0_4;0O0P3i5i4a1P0p0_0q5p4D3s4s0W0b5g5c5x3S3 040y1z1L5w5j2_4z5L5r0;5t04020z0O0k5P581P0L0X0_0U4O5y0_4H4B3a5h5h5E4x5l4=5)3S5S0g5^5=040t0w0w4h5|1)4s4u5-3{5Z3e5O675q69015S0v5Y4W5!5$042}675;640_0B5C5/6d6j6a04552;6v325S0e0e5v6c6p6k2|6t6B3s5G2n0O0A0j6z2 6M3S4y045m5o670{0e3_0u2u2V6)3!1t3$2x2A2v0t1K6,0e3#6$0!0$0(0P04.

Exercice 3

Coder une fonction zeckendorf_txt qui prend un tableau de bits en paramètre et qui renvoie la chaine de caractères associée à la représentation de Zeckendorf décrite avec bits.

Exemples
  • # Fibonacci 1 2 3 5 8 13 21 34 55 89 ...
  • assert zeckendorf_txt([0, 0, 1, 0, 1, 0, 0, 0, 0, 1]) == "3 + 8 + 89"
  • assert zeckendorf_txt([1, 1, 0, 0, 1, 0, 0, 1, 1]) == "1 + 2 + 8 + 34 + 55"
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/fTZ78rnb _o=ylaepcwgu)vd46F1z3kRméhtsP(S0à+2èi:050D0v0P0u0Z0t0Q0o0x0t0u0Q0Q0r010P0Z0w010406050Q0A0M0M0u0l0s040T0q0t0A0^0q0m050f0 1113150}0w04051l1e1o0f1l0}0D0Z0C0-0/0;0?0O0Z0z0O0t1C0O0P0{050(0n0t0v1x0:0=011B1D1F1D0P1L1N1J0P0l1m0P0O1P1z010g0*0v0m0u0M0v010-180Q0w0u0m0?0X1J1`1|1*1R1-1N1:1=0{0a0o0R0l0q0w0q0Q0Z1b0m0o0$1^0l0l0v0x2j1e210m1m0f1(2w1#1%1$1K0D230?1F0m1/2g1J1u1w0.1Q2G0Z2I0m0q2M1J0w2p1m2u2w2!0~1{2k2O1+2T0l120t0{0o0H2t2(0|2%222*1R2,2.2:0X2?1|2^2u2F012}0u2/040o0J312v0}342{0?37390o0E3d332(353j2:0d3n3f3p3h360q2-382:0F3u2_2)1y2|3z2~3a0j3E3g3H3i3J3B3a0k3N3w3P3y3A3k0e3V2`3X3r040H0U3$3G2P3Y3K0H2=1f2@3v3%3/3)0H303@323_3.2+3R390H3c3 3e3F3q440{0H3m483o3`433Z4d3t4g414b4k3*3D4n4a3x3|3M4g1p2Y1e2M2z0D1%2E3x0x2U1?1m4C1n4A2$4y4I0$2Z3W3/0K0{0$0g3n4u3X0y2:4!3O3{0g0{0I2q0K1/0D3z0g0p0P0b0P4)4U1+0`040S4|4i2|0{0n2i0Q52421R4 0B0!3-354%3a0o5j59350Q0D0{015q5f3x5n2:5j0o0L1/0C0q0Z1O0/0-0O0)2I2l1O0x130u2r0Y2p0,1Q0q0x0Z0N1O0V5s3X5u5i5w5w5E2p2X0N0Q1/0(2j5J0o0i4/4;4?2l1c0m5W0o0u0C2q0o1N0o1Y0v0u0A0o560P584t4*1+5#5%5q013u5%4#3{0{0u5l3x4 0c3n0o6m2+556u6w1R0q0{0r6z6e1R0M0Z4d6q3X6s6F4}6H6J043~2!5k6G0?0x0H0{030o0G0Z0n0S0Z0B0o0%6$6(6*0o0W2;0B6k5w6A3i0{0x5G2R0v6O530?6C046E4g6v6W010Q1 045r4n6l7a0m0{2X0v6I0v0l725a746D7q350K0x0{0h0l0A717g6`7a4W040g3z7u4v552i7K3X0q5h2R7O6n046a6c2$7a4 5e7D5%6V6P0?7G0Z4Z786{367M4{7.7a750r776U7/6I6K4y7Z0{7#2!067%85797)017+7-7{7i7k2p7n7p7 887!6_86867/7j047l8g7T1+7^8t1R7w0{0G385-8l8m8773890{0v0+7C7Y8j818D8E7E888p6~5H8L2@8F7r01750W7`8X7/7c5p6=0o6j7$8E8o6}6 2I8w7s048$8^360n0{0Q1#6L3/4 518i8G8p6p968Z5c8P8R976o924~0{6t7?8S6y9l8G8v9o8Z8p0n9h5b9j8|988|8#9y9n837h887G2p0P0A0l1d9r3q8=8V3E0f4R0v2w7l2w4M2x4E1e2A9#0u1M9U4B1v2^0f0$0(0*0Q04.