Profondeurs

🧓 Cet exercice utilise une modélisation d'arbre non ordonné, avec la liste des parents.

Profondeur d'un nœud

La profondeur d'un nœud, est la longueur, en nombre d'arêtes, pour aller du nœud jusqu'à la racine.

La profondeur de la racine d'un arbre enraciné vaut donc 0, c'est le minimum.

Exemple d'arbre non ordonné

graph TB
    R("5") --> R1("2")
    R1 --> R2("1")
    R2 --> R3("3")
    R2 --> R4("0")
    R2 --> R5("4")

🐍 Script Python

# indices  0  1  2  3  4  5
parents = [1, 2, 5, 1, 1, None]
profond = [3, 2, 1, 3, 3, 0]

La profondeur de chaque nœud est donné par la liste profond

Exercice

Coder une fonction profondeurs qui prend en paramètre la liste des parents (modélisant un arbre non ordonné) et qui renvoie la liste des profondeurs de chaque nœud.

On devra écrire un algorithme efficace qui utilise les profondeurs déjà calculées !

Indice

1. On pourra initialiser une liste remplie de None pour les profondeurs inconnues.
2. Pour chaque nœud (un indice 0 <= i < taille) on construit un chemin du nœud jusqu'à un autre de profondeur connue.
3. Si le parent indiqué est None, c'est que le nœud précédent était la racine. On connait sa profondeur...
4. Une fois connue la profondeur d'un nœud sur le chemin, on calcule la profondeur de chaque nœud sur ce chemin en le rebroussant.

Guide

🐍 Script Python

def profondeurs(parents):
    "Renvoie la liste des profondeurs d'un arbre non ordonné modélisé par sa liste de parents"
    taille = ...
    profond = [None for _ in range(taille)]
    for i in range(taille):
        noeud = i
        chemin = []  # une pile vide
        while profond[noeud] is ...:
            # la profondeur du nœud est inconnue
            chemin.append(...)
            noeud = parents[noeud]
            if noeud is ...:
                # c'était la racine
                noeud = ...
                profond[noeud] = 0
        # la profondeur du nœud est **connue**
        p = profond[noeud]
        while chemin != ...:
            noeud = ...
            p += 1
            profond[noeud] = ...
    return profond

###(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

Exécuter le code
(Ctrl+S)Valider
Ctrl+Enter
(Clic droit pour l'historique)TéléchargerTéléverserRéinitialiser l'éditeurSauvegarder dans le navigateur

Évaluations restantes : ∞/∞

.339.128013]59/f.!78rnb N_o=ylaepcwgu)*vd4613kRméhtsP(S0+2[i:050F0w0P0v0Y0u0Q0o0y0u0v0Q0Q0s010P0Y0x010406050Q0B0M0M0v0l0t040T0r0u0B0@0r0m050f0~1012140|0x04051k1d1n0f1k0|0F0Y0E0,0.0:0=0O0Y0A0O0u1B0O0P0`050%0n0u0w1w0/0;011A1C1E1C0P1K1M1I0P0l1l0P0O1O1y010g0)0w0m0v0M0w010,170Q0x0v0m0=0W1I1_1{1)1Q1,1M1/1;0`0b0o0R0l0r0x0r0Q0Y1a0m0o0#1@0l0l0w0y2i1d200m1l0f1%2v1!1$1#1J0F220=1E0m1.2f1I1t1v0-1P2F0Y2H0m0r2L1I0x2o1l2t2v2Z0}1`2j2N1*2S0l110u0`0o0I2s2%0{2$212)1Q2+2-2/0W2=1{2@2t2E012|0v2.040o0J302u0|332`0=36380o0G3c322%343i2/0d3m3e3o3g350r2,372/0H3t2^2(1x2{3y2}390j3D3f3G3h3I3A390k3M3v3O3x3z3j0e3U2_3W3q040I0U3#3F2O3X3J0I2;1e2?3u3$3.3(0I2 3?313^3-2*3Q380I3b3~3d3E3p430`0I3l473n3_423Y4c3s4f404a4j3)3C4m493w3{3L4s3N3`4b3)3T4x3V4z4p0I3!4D4h3H4p0W3+4J414L3J0W3=2Z4n4u4A0W3}2#1q2X1d2L2y0F1$2D3w0y2T1=1l4)1m4%4#2#4/0#2Y4E1*0K0`0#0g3m4t3W0z2/544y2*0g0`2W0r0g1b0#0B0l0Q594~1Q0_040S5m4K3h5d121.0P5l4f553.5p0C0Z3t0o5H0o5B1*0Q1~04010L1.0E0r0Y1N0.0o1E0Q0P1N0#0+5e5g0m5i5k2k000B2j120n2o0o2S2j3y0F1b0m0N0o0M2T0N5Y5~1`0l0o0Q0v5X0Y5Z5#1N655x0Q015G5I5K2{0`0%0)1M3m5J5a1Q0r0`0s6r6l3h0n0`255s4Q0=5p5r5A6t5u046f0m5y6E345D6j5H6z355d2c5)0F6y6K016v046x4f6s5n6G0`0X6Q3w0K0y0`0p1b0w6#6-0150045g0l6|5t6W040q736F6%57042Q783p6B040l1{0A6{6J6}6H6;3%6n0(0u6q7m745D0c6T6,746 717e4u0`0Y7E3W0r7b7d6+6V0m7g7i0m7k7p5C0`6I2#6$0m7r6p7l7Y7n0`5E7z5I7A797!042S0w0B6!7N6$6(6*2Z7.3p7G7,6k7Z0`0y0O0w0M7M7}6V7{7I7V040X7y6+7~4.0I0`030o5/6e1-816U6$6 0z1A7u8a836M6Y5h7U1*5p6:7v7/0`7=7@8E5o0`8h8z6}7K7G5z8R7B6@046_2H8N6.045F4m7-8+826}0y8l048n5W5(5h7?660F0B5@0a7@0o0w5Z0o2Q4/0m0m0B7%3@8,8,6V6 0Y537_6}7:6N6P8I6R6/8$758L7^7(7w8P8d1*8T7c8V2?8j3W6?6^6`9p5p8)4V9b9L9C3.8/8m8}8 910P5X697i0y2Q993 9M9b7O6X5f8D9m3w8G9p7:9r9H9v9h748c9@79880`4O9K9$9N4 0`0w0*9!2u6V9I8s9M9(048587892?8b0`0h9/0`0v0x0x1.9sah6$7o9,7q7;0r7?ar31a87*aa9Lac9;9`349_8W8J6M5w6O9AaBat9oav3`8Kay8MaU8F9?9 9c6$9P8;9V0o8@5*8_2k8|0m8~2D9T0o0D0D95970wa`aaac0x9w6u6wb36La-aAa7aS8falaxaz9=048Q9a9%8u0`8w8raI7Fad86881cbp7J0`0i7|9BaC8f0c9Jbj9$aGaXb939ai6)b675aebt9p6(akaZ6m6M2dbg0S0CaE8-749jbN6(0Vbz31a11Q9|3)b#8t9i9)6Zbg8H9taMaHb|9nbhb)b5bvaV6M7z9d0`2o0P5jbuaL7 8B9*5*3D0f4{0w2v2Wcm4(1u4*2y2B2w0v1Lcp0f4)0|cz0$7s0Q04.