melissa240
Messages postés1Date d'inscriptionlundi 10 décembre 2018StatutMembreDernière intervention10 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.
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."""
#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
#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)
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. """
#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