Implementation arbre

Fermé
melissa240 Messages postés 1 Date d'inscription lundi 10 décembre 2018 Statut Membre Dernière intervention 10 décembre 2018 - 10 déc. 2018 à 10:46
Bonjour, alors voila j'ai besoin d'aide sur 2 question sur mon sujet d'algo. Il est un peu long mais j'ai tout fait a part les 2 questions en particuliers (cela porte sur les induction structurelle). Je serez infiniment reconnaissante si quelqu'un pourriez m'aider a les boucler.
Je vous pose mes reponse et le sujet.




#Arbre : List[int]
Arbre = [0,0,3,0,1,1,3,3]
#tA : List[int]
tA = [2,3,3,4,10,3,20,5]

#tB : List[int]
tB = [3,10,1,2,2,15,5,1]

#cAB : List[int]
cAB = [0,1,2,4,2,3,3,3]

#cBA : List[int]
cBA = [0,4,3,3,4,2,3,4]

#Sigma : List[int]
Sigma = [1, 1, 0, 0, 0, 1, 0, 0]




def duree(u, Sigmau, tA, tB):
""" list[]**2 * int**2 -> int
renvoie tA[u] si Sigmau = 1, tB[u] sinon. """

#les comparaisons ont ete faites pour verifier que u est bien un noeud de l'arbre,
#et que sigma est un booleen 0 ou 1 sinon on demande de rentrer de valeurs valides

if (Sigmau == 1 and (u<len(tA))):
return tA[u]
elif (Sigmau == 0 and (u<len(tB))):
return tB[u]
else:
print("Entrez des valeurs valides, svp.")




def valCom(u, v, Sigmau, Sigmav, cAB, cBA):
""" liste[]**2 * int**4 -> int
renvoie 0 si Sigmau et Sigmav égaux, 1 si Sigmau = 1,
cBA((u,v)) sinon."""

# -||- les comparaisons ont ete faites pour verifier que u est bien un noeudde l'arbre,
#et que sigma est un booleen 0 ou 1 sinon on demande de rentrer de valeurs valides

if (Sigmau == Sigmav):
return 0
elif (Sigmau == 1 and (v<len(cAB))):
return cAB[v]
elif (Sigmau == 0 and (v<len(cBA))):
return cBA[v]
else:
print("Entrez des valeurs valides, svp")



def succ(u, Arbre):
""" Arbre*int -> list[]
renvoie la liste des successeurs de u dans l'arbre ABT Arbre."""

#j : int
j = 1

#list_succ: list
list_succ = []

while (j < len(Arbre)):
#a partir de Arbre[1] car la racine Arbre[0] n'a pas de successeurs et on risque de boucler a l'infini
if Arbre[j] == u:
list_succ.append(j)
j = j+1

return list_succ



def CalculDelta(Arbre,tA,tB,cAB,cBA,Sigma,u):
"""list[]**5 * int -> int
renvoie delta(u) pour une allocation sigma."""

#tab_u, succ_u, succ_u,bis : list[]

tab_u = duree(u,Sigma[u],tA,tB)
succ_u =succ(u,Arbre)
succ_u_bis = []

#i, j, val, val_finale : int
i, j, val, val_finale = 0, 0, 0, 0


if (succ_u == []):
return tab_u



else:
while( i<len(succ_u) ):

val = valCom(u, succ_u[i], Sigma[u],Sigma[succ_u[i]], cAB, cBA)
j = CalculDelta(Arbre, tA, tB, cAB, cBA, Sigma, succ_u[i]) + val
succ_u_bis.append(j)

i = i + 1


val_finale = max(succ_u_bis)
val_finale += tab_u


return val_finale




#la fonction decompose_base_2 decompose tout entier j en base 2 et envoie le resulat
#sous la forme d'un tableau, elle est faite pour etre utilitee dans CalculSigmaOptimum

def decompose_base_2(Arbre,j):
""" int*list[] -> list[]
renvoie un tableau des chiffres de la decomp de j en base 2. """

#i : int
i=0

#tab : list[]
tab = []

#n : int
n = len(Arbre)

while(n):
i = j%2
j = j//2
tab.append(i)
n = n -1

#je fais le mirroir de mon tableau de valeurs vu qu'elles ont ete stockee dans
#l'ordre inverse, cette etape n'est pas necessaire mais nous sert a voir la bonne
#representation binaise de j

i=0
j=0
temp = 0
while(i<len(tab)):
j = len(tab) - 1
temp = tab[i]
tab[i] = tab[j-i]
tab[j-i] = temp
i = i + 1

return tab




def CalculSigmaOptimum(Arbre, tA, tB, cAB, cBA):
""" list[]**5 -> int
renvoie l'allocation de duree minimale. """

#n : int
n = len(Arbre)

#alpha : int
alpha = 2**n

#j, j_minimum : int
j, j_minimum = 0, 0


#tab_Sigma, resultats, allocations : list[]
tab_Sigma, resultats, allocations = [], [], []


#je cherche la representation de tout le nombre < alpha en binaire
#pour ensuite les stocker dans un tableau d'allocations
while( j<alpha ):
tab_base_2 = decompose_base_2(Arbre,j)
tab_Sigma.append(tab_base_2)
j = j + 1


#je cherchce la valeur minimale en stockant d'abord toutes les valeurs
#pour les allocations possibles, la fonction renvoie ensuite SIgma pour
#laquelle resultat est minimal.
for Sigma in tab_Sigma:
resultat = CalculDelta(Arbre, tA, tB, cAB, cBA, Sigma, 0)
resultats.append(resultat)
allocations.append(Sigma)

minimum = min(resultats)
j_minimum = resultats.index(minimum)

return allocations[j_minimum]





dA = tA[:]
dB = tB[:]


def CalculBorneInf(Arbre, tA, tB, cAB, cBA, dA, dB, u):
"""List[int]**7 * int ->
calcule dA et dB de u. """

#liste_succ, tab1, tab2: List[int]
liste_succ, tab1, tab2 = [], [], []
liste_succ = succ(u, Arbre)


#succsseur : int
successeur = 0


if ( len(liste_succ)>0 ):
for successeur in liste_succ:
CalculBorneInf(Arbre, tA, tB, cAB, cBA, dA, dB,successeur)


for successeur in liste_succ:
tab1.append(min(dA[successeur],dB[successeur] + cAB[successeur]))
tab2.append(min(dB[successeur], cBA[successeur] + dA[successeur]))

dA[u] += max(tab1)
dB[u] += max(tab2)

#return print("dA(",u,")=",dA[u],", dB(",u,")=",dB[u])
return [dA, dB]




def CalculSigmaOptimum2(Arbre, tA, tB, cAB, cBA, DeltaA, DeltaB, Sigma, u):
"""List[int] ** 5 * int ** 4 ->
calcule et renvoie une allocation sigma pour laquelle la duree est minimale. """

#liste_succ: List[]
liste_succ = []
liste_succ = succ(u, Arbre)

#successeur : int
successeur = 0


if (u == 0 and dA[0] <= dB[0]):
Sigma[0] = 1

elif (u == 0):
Sigma[0] = 0

else:

if (Sigma[Arbre[u]] == 1):
if ( dA[u] < (dB[u] + cAB[u]) ):
Sigma[u] = 1
else:
Sigma[u] = 0

elif (Sigma[Arbre[u]] == 0):
if (dB[u] < (dA[u] + cAB[u]) ):
Sigma[u] = 0
else:
Sigma[u] = 1

for successeur in liste_succ:
CalculSigmaOptimum2(Arbre, tA, tB, cAB, cBA, DeltaA, DeltaB, Sigma, successeur)

return Sigma


def CalculArbreComplet(hauteur):
""" int -> Arbre
renvoie une arbre binaire complet. """

#Complet : list[]
Complet = []

#nb_noeuds : int
nb_noeuds = 0
nb_noeuds = 2^(hauteur - 1) + 1

#Complet[0] : taille de l'arbre
Complet.append(nb_noeuds)

#i : int
i = 0

seed(10)

while(i < nb_noeuds):

noeud = randint(0,1000)

if noeud not in Complet:
Complet.append(noeud)
i = i+1


return Complet


def InstanceAleatoire(n, M):
"""int**2 -> list[]*
renvoie toutes les valeurs numerique d'une instance de n taches."""

# i : int
i = 0

# val : int
val = 0

# M = 50 pour les experimentations

#tA, tB: list[int]
tA, tB = [], []

#cAB, cBA : list[int]
cAB, cBA = [], []

i=0
while (i < n):
val = randint( 1, M)
if val not in tA:
tA.append(val)
i = i+1

i=0
while (i < n):
val = randint( 1, M)
if val not in tB:
tB.append(val)
i = i+1

i=0
while (i < n):
val = randint( 1, M)
if val not in cAB:
cAB.append(val)
i = i+1
i=0
while (i < n):
val = randint( 1, M)
if val not in cBA:
cBA.append(val)
i = i+1

return print("tA =" ,tA, "\ntB =" ,tB, "\ncAB =" ,cAB, "\ncBA =" ,cBA, "\n")


Configuration: Windows / Firefox 63.0