Aller au contenu

Correspondance Łukasiewicz (2)

Série d'exercices

Cet exercice fait partie d'une série :

Suite de l'exercice précédent

Dans l'exercice précédent, on a construit une fonction qui renvoie un chemin pour un arbre enraciné donné.

Ici, il s'agit de la fonction réciproque, ce qui établit une correspondance entre arbre enraciné et chemin de Łukasiewicz.

Méthode approximative

Comment faire sur cet exemple ?

  1. Le chemin est bien dans le quadrant en haut à droite.
  2. Le chemin est associé à une liste de valeurs [2, -1, 4, -1, 1, -1, -1, -1, -1, -1]
  3. On ajoute \(1\) à chaque élément, et on ajoute \(0\) à la fin de la liste. On obtient [3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0]
  4. La difficulté est ici ; le découpage. Il y a 3 sous arbres à la racine.
    • Le découpage est 3, [0], [5, 0, 2, 0, 0, 0, 0, 0], [0].
    • Le découpage de [5, 0, 2, 0, 0, 0, 0, 0] est 5, [0], [2, 0, 0], [0], [0], [0].
    • Enfin, le découpage de [2, 0, 0] est 2, [0], [0]
  5. Les [0] obtenus sont les feuilles de l'arbre.

⚠ Programmer le découpage est délicat.

Écrire une fonction chemin_vers_arbre qui implémente l'autre partie de la correspondance de Łukasiewicz.

Exemples

qui correspond à la liste [1, -1], donne un arbre

représenté en interne avec [[], []].

🐍 Console Python
>>> chemin_vers_arbre([1, -1])
[[], []]

qui correspond à la liste [2, -1, -1, 1, -1], donne un arbre

représenté en interne avec [[], [], [[], []]].

🐍 Console Python
>>> chemin_vers_arbre([2, -1, -1, 1, -1])
[[], [], [[], []]]
###(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 : 10/10
.65038.321.128013.9875s3_8èufvy n7aS1me(P24V:twi][h)6Oo;bcdg/0làqp.rF-,À=+zk95Rxé050O0u0B0q0D0S0e0n0N0S0q0e0e0$010B0D0V010406050e0j0t0t0q0X0m040r0K0S0j120K0o0n020q0t0V0L0n0,0u1c0X0U0j0u0e050Q191b1d1f170V041D1K051N0Q1N1P1K170O0D0l0`0|0~100G0D0P0G0S1%0G0B15050=0M0S0u1Y0}0 011$1(1*1(0B1:1=1.0B0M0K0O1f1/0X1L0B0G0`1i0e0V0q0o100x011@1!010k0@0u0o1q0u1.2f2h2m1_2p1=2s0t2u040c0n0w0X0K0V0K0e0D1l1n0:2d0X0X0u0N2P1D2w0o1L0Q2b2#0B29282a0O2y101*0o2r2M1.1V1X0{1^2/0D2;0o251W1.0V2U1L2Z2#36182g1n2`2n2 0X1c0S150n0s2Y3a16392x3c1_3e3g3i0x3l2h3n2Z2.013s0q3h040n0f3w2!173z3q103C3E0n0y3I3y3a3A3O3i0+3S3K3U3M3B0K3f3D3i0I3Z3o3b1Z3r3(3t3F0p3-3L3:3N3=3*3F0h3_3#3{3%3)3P0*413p433W040s0R483/2{443?0s3k1E3m3!494h4b0s3v4m3x4o4g3d3}3E0s3H4u3J3.3V4z150s3R4D3T4p4y454I3Y4L4w4G4P4c3,4S4F3$4r3^4Y3`4q4H4c404%424)4V0s474L1M341D2^2(0O2,3A0N252E0/1W1L330u353m3S054 0:574N1_0)150:0k594(2n0C3i5k4.3d0k150N0G1w2}0g0l0u0X0e0g1d0M2U5p5e1014040v5H4x3r5t5v0t2}5N3A5K0H0A3Z0n5!0n4Z430e2k04014 2T1B2L0o0O2h0N1?2R0b0j0)0}0D0u0C0D0N0(013Z065#5$5l5f5h0u5j4?69105n3F5U4!5s040;0q0V0u6j435K5M6e5q5P040B1w0V6r4h5K0!3S686w3N150D6C2n5W5Y4S67675%4h5)15010Y1m2W0D1m0n0X0.0N0j5B1W1?2}6z0X2;646Q6R5!6T2n5g040D6d366H5I3B156z1r6M1_5K0F776J6}7b015K0E6G6`1_0K150$0$7i6f015S154e6v725K6P36666^6R7j106|2U0B6+0o7p6I7f150F0E6F4L715O107s4c5Z7B7D016|0u0^6q7v7T7M047y4n7B7C7q0o152U190S0=0B7K727l047o7R7Z797h6@7/6_7;740?0S1=0g0B0K0=1=7|7*7~80707Z7V4l7z865#7Z6|0k3(8i3V150g8x3$0K6h5T817;0M7?2h0P7(387q6t7e7=6y6A7e798Q6K8U150E5X7X8r6S88040e0K0j5C5E5G7)5V157Q8m8)0=0@8h8G7L8k8B4a156n6p8Y5L8W8S768;3$6E904q8X8}7}150%9d3d898{0u8d8f3D8M588O150H8$8%877L8R8`8b9o8e8g9s3x7S3A7~0%8l3m9J4!9m9D9x9y7Z8R7@0j7_0q7{9a437~0W976o6p5;956u8N9A158+8-5D0X5F9H2!829v9T8s7q7F0;7I9k6x9X9Z9#9:7w8?a57c9C8c9F9r658(9;986B9g8j7mad7+7a9$9e040mar9Lar8oar8u8wao8yaway8E7JaF9Q045u5waKaa7*7gay9iar8Vau2n7V7uaR8=04848qa0al8/9{5daSacaL916y8a8|8^8~aqa=av93a.9}96aY6x75ana$9ba;a`72a!959w859P43a27H6;ar8Ra-3-0Q5b564@br0Q4`1D0B4|bw2*2$24262(0q1;bt4`1Ja/3A2U0t0g0k0q0)9o0G0f151v1x1z1B0n7-3x1M3n0G0s0n0D0O105z6,1m0Z2O5A9!6-150z5A2N6$2O0.0Xb^5z050q3A5v0q0:0X2:5g0n0G2U0k1003b/b}0ob=6:c22u0n120B1=100w5A1c2~0B0ncb150d0a1D0q2#b)3n1K0J1n1k0@0D0e6.0N0D0n0:0j0-0n0V2q1C1Q3n2^c61+1}1,2v7L2A2r2t152G0r0N0X13cz0w0m2b1m5955a/3758bqbK3$6|5i7e6h5$b33N6laO5S0o5yb|9^9`9.97dg8Fb76s9vb#3Jak726V5+5-7@5:5=0o5@cU1?5`5|2N5 61639x9V15bna}2n8 dS787N7Oa)7.a+726|0C1$a_9OdPaN5Rdq9t7L7x9 9z728R9?8.9_8:baap7 aW7NdZ4v7/8t158v0Xbl8zaI6KaQd+8H8J0o8Ldndd7r0D4IaU049jdV7cdpeeb$7q9(972Lb6d:ab5L0Hbed~a%du169U8)d`dld}eCd 9)elbm0V9,0OekdravdReZdT15eSe$6xeA9.eFd?bge!d|b0exe(9*eV2reXel8PeT9=8,d{dme}9~bfe6047Ga4es7304e#eQ9Ke^e 04e,f4eEbod5bs2#bI1O04cLb+0o2O0D3DcP1?5a50fde=1Dd50n0q5z0NcAc5c9fw0i2U0n0k0u0j9n5$d57OfGfD0n1zcT0l5~0ocz0TfMfS2}cU0j2d5=8LeS1TfsfC5cdRfHcQ2d0o0e2)fVcz4 1b1?0j2;cY2qdG0nd`0Za-0e0!f$fVgf1mcz0u0-2)0?0B0_2L6+fSbFc_bY0X0nga0n2 0j5z0qf=gga-cY1j0_0Pc15;0W0n0#f.2p1nf|56f~f#gb4 f+f*cz1z00gE0.0S0.2Df+b!cA00gM2rgl1B2Pf_3nbu6n0@0e04.
Indice 0

On peut essayer une version itérative qui travaille avec chemin comme une pile, et avec une autre pile dans laquelle on stocke des sous-arbres... Pas évidente à imaginer...

Sinon, on peut envisager une version récursive avec les indices suivants.

Indice 1

Il sera utile de créer une fonction etape, récursive, qui prend une liste en paramètre, ainsi qu'une position de départ et renvoie la représentation de l'arbre indiqué à cette position, ainsi que la longueur utilisée dans la liste.

Par exemple

🐍 Console Python
>>> etape([3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0], 1)
([], 1)
>>> etape([3, 0, 5, 0, 2, 0, 0, 0, 0, 0, 0], 3)
([[], []], 3)
>>> etape([3, 0, 0, 2, 0, 0], 0)
([[], [], [[], []]], 6)
Indice 2

Cette fonction récursive pourra avoir le squelette

🐍 Script Python
def etape(temp, i):
    "Fonction récursive interne"
    if temp[i] == 0:
        return [], 1
    else:
        resultat = []
        taille_totale = 1
        for _ in range(temp[i]):
            sous_arbre, taille = etape(..., ...)
            taille_totale = ...
            resultat.append(...)
    return resultat, taille_totale