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
.9875.65038.321.128013:p(40zed3; 1Vo5_n)h]6,qc[yFuvà8i2+xmÀs7=wlSatf-9ORrg.éPkbè/050l0k0W0V0J0T0P0o0B0T0V0P0P0R010W0J0f010406050P0F0N0N0V0$0D040U0r0T0F120r0u0o020V0N0f0n0o0#0k1c0$0A0F0k0P050.191b1d1f170f041D1K051N0.1N1P1K170l0J0G0`0|0~100w0J0%0w0T1%0w0W15050=0,0T0k1Y0}0 011$1(1*1(0W1:1=1.0W0,0r0l1f1/0$1L0W0w0`1i0P0f0V0u100K011@1!010X0@0k0u1q0k1.2f2h2m1_2p1=2s0N2u040d0o0*0$0r0f0r0P0J1l1n0:2d0$0$0k0B2P1D2w0u1L0.2b2#0W29282a0l2y101*0u2r2M1.1V1X0{1^2/0J2;0u251W1.0f2U1L2Z2#36182g1n2`2n2 0$1c0T150o0p2Y3a16392x3c1_3e3g3i0K3l2h3n2Z2.013s0V3h040o0m3w2!173z3q103C3E0o0h3I3y3a3A3O3i0s3S3K3U3M3B0r3f3D3i0y3Z3o3b1Z3r3(3t3F0Q3-3L3:3N3=3*3F0I3_3#3{3%3)3P0Z413p433W040p0i483/2{443?0p3k1E3m3!494h4b0p3v4m3x4o4g3d3}3E0p3H4u3J3.3V4z150p3R4D3T4p4y454I3Y4L4w4G4P4c3,4S4F3$4r3^4Y3`4q4H4c404%424)4V0p474L1M341D2^2(0l2,3A0B252E0/1W1L330k353m3S054 0:574N1_0+150:0X594(2n0S3i5k4.3d0X150B0w1w2}0t0G0k0$0P0t1d0,2U5p5e1014040g5H4x3r5t5v0N2}5N3A5K0v0e3Z0o5!0o4Z430P2k04014 2T1B2L0u0l2h0B1?2R0c0F0+0}0J0k0S0J0B0j013Z065#5$5l5f5h0k5j4?69105n3F5U4!5s040;0V0f0k6j435K5M6e5q5P040W1w0f6r4h5K0z3S686w3N150J6C2n5W5Y4S67675%4h5)15010E1m2W0J1m0o0$0)0B0F5B1W1?2}6z0$2;646Q6R5!6T2n5g040J6d366H5I3B156z1r6M1_5K0C776J6}7b015K0x6G6`1_0r150R0R7i6f015S154e6v725K6P36666^6R7j106|2U0W6+0u7p6I7f150C0x6F4L715O107s4c5Z7B7D016|0k0^6q7v7T7M047y4n7B7C7q0u152U190T0=0W7K727l047o7R7Z797h6@7/6_7;740?0T1=0t0W0r0=1=7|7*7~80707Z7V4l7z865#7Z6|0X3(8i3V150t8x3$0r6h5T817;0,7?2h0%7(387q6t7e7=6y6A7e798Q6K8U150x5X7X8r6S88040P0r0F5C5E5G7)5V157Q8m8)0=0@8h8G7L8k8B4a156n6p8Y5L8W8S768;3$6E904q8X8}7}150L9d3d898{0k8d8f3D8M588O150v8$8%877L8R8`8b9o8e8g9s3x7S3A7~0L8l3m9J4!9m9D9x9y7Z8R7@0F7_0V7{9a437~0(976o6p5;956u8N9A158+8-5D0$5F9H2!829v9T8s7q7F0;7I9k6x9X9Z9#9:7w8?a57c9C8c9F9r658(9;986B9g8j7mad7+7a9$9e040Dar9Lar8oar8u8wao8yaway8E7JaF9Q045u5waKaa7*7gay9iar8Vau2n7V7uaR8=04848qa0al8/9{5daSacaL916y8a8|8^8~aqa=av93a.9}96aY6x75ana$9ba;a`72a!959w859P43a27H6;ar8Ra-3-0.5b564@br0.4`1D0W4|bw2*2$24262(0V1;bt4`1Ja/3A2U0N0t0X0V0+9o0w0m151v1x1z1B0o7-3x1M3n0w0p0o0J0l105z6,1m0Y2O5A9!6-150q5A2N6$2O0)0$b^5z050V3A5v0V0:0$2:5g0o0w2U0X1003b/b}0ub=6:c22u0o120W1=100*5A1c2~0W0ocb150a0b1D0V2#b)3n1K0!1n1k0@0J0P6.0B0J0o0:0F0M0o0f2q1C1Q3n2^c61+1}1,2v7L2A2r2t152G0U0B0$13cz0*0D2b1m5955a/3758bqbK3$6|5i7e6h5$b33N6laO5S0u5yb|9^9`9.97dg8Fb76s9vb#3Jak726V5+5-7@5:5=0u5@cU1?5`5|2N5 61639x9V15bna}2n8 dS787N7Oa)7.a+726|0S1$a_9OdPaN5Rdq9t7L7x9 9z728R9?8.9_8:baap7 aW7NdZ4v7/8t158v0$bl8zaI6KaQd+8H8J0u8Ldndd7r0J4IaU049jdV7cdpeeb$7q9(972Lb6d:ab5L0vbed~a%du169U8)d`dld}eCd 9)elbm0f9,0lekdravdReZdT15eSe$6xeA9.eFd?bge!d|b0exe(9*eV2reXel8PeT9=8,d{dme}9~bfe6047Ga4es7304e#eQ9Ke^e 04e,f4eEbod5bs2#bI1O04cLb+0u2O0J3DcP1?5a50fde=1Dd50o0V5z0BcAc5c9fw0-2U0o0X0k0F9n5$d57OfGfD0o1zcT0G5~0ucz0HfMfS2}cU0F2d5=8LeS1TfsfC5cdRfHcQ2d0u0P2)fVcz4 1b1?0F2;cY2qdG0od`0Ya-0P0zf$fVgf1mcz0k0M2)0?0W0_2L6+fSbFc_bY0$0oga0o2 0F5z0Vf=gga-cY1j0_0%c15;0(0o0Of.2p1nf|56f~f#gb4 f+f*cz1z00gE0)0T0)2Df+b!cA00gM2rgl1B2Pf_3nbu6n0@0P04.
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