Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Preuve algo recursif

Posté par
soo123
04-12-16 à 01:08

Bonjour,
je bloque  pour la preuve de cet algo en utilisant le theoreme de correction:
Entasser-max(A,i)


g<-- Gauche(i)
d<-- Droite(i)
Si g<=taille[A] et A[g]>A[i]
    alors max<--  g
   sinon  max <--  i
Si d<=taille[A] et A[d]>A[max]
   alors max <--  d
Si max <> i
 alors echanger(A[i] et A[max])
    Entasser-Max(A,max)


Merci d'avance!

Posté par
carpediem
re : Preuve algo recursif 04-12-16 à 12:28

salut

peut-être au moins nous dire ce qu'il est censé faire ...

Posté par
soo123
re : Preuve algo recursif 04-12-16 à 14:26

L'algorithme permet de rétablir la propriété d'un tas max.(un arbre binaire tel que la valeur du noeud pere est superieur ou egal a celles des noeuds fils).
A c'est un tableau representant le tas ,i c'est l'indice du noeud qui a une valeur plus petite que celles de ses fils .Le role de l'algo c'est de faire descendre la valeur de A[i] dans le tas max, de sorte que le sous arbre enraciné en i devienne un tas max.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !