Questions / réponses

parameters

parameters

BrandelClement -
回帖数：3

Bonjour,  

apparemment j'aurais un problème sur ma fonction btree_size mais je ne comprend pas pourquoi. Pouriez_vous m'expliquer ?  


let rec btree_size t = match t with 

    Empty -> 0

    | bin(x,t1,t2) -> 1 + btree_size t1 + btree_size t2 ;;


let rec nb_de_feuilles t = match t with 

    Empty -> 1

    | bin(x,t1,t2) -> btree_size t1 + btree_size t2 ;;

    

let arity t = match t with 

    Empty -> -1 

    | bin(x,t1,t2) -> if (t1 = Empty && t2 = Empty) then 0 else if (t1 = Empty && t2 != Empty) || (t1 != Empty && t2 = Empty) then 1 else

    2 ;;

let rec nb_noeud_2 t = match t with 

    Empty -> 0

    | Bin(x,t1,t2) -> if arity t1 = 2 && arity t2 = 2 then 2 + nb_noeud_2 t1 + nb_noeud_2 t2 else 

        if (arity t1 != 2 && arity t2 = 2) || (arity t1 = 2 && arity t2 != 2) then 1 + nb_noeud_2 t1 + nb_noeud_2 t2 else 0 + nb_noeud_2 t1 + nb_noeud_2 t2;;

    

let rec nb_noeud_1 t = match t with 

    Empty -> 0

    | Bin(x,t1,t2) -> if arity t1 = 2 && arity t2 = 1 then 2 + nb_noeud_2 t1 + nb_noeud_2 t2 else 

        if (arity t1 != 1 && arity t2 = 1) || (arity t1 = 1 && arity t2 != 1) then 1 + nb_noeud_2 t1 + nb_noeud_2 t2 else 0 + nb_noeud_2 t1 + nb_noeud_2 t2;;

        

let rec btree_height t = match t with 

    Empty -> -1

    | Bin (x,t1,t2) -> 1 + max (btree_height t1)(btree_height t2) ;;

    

let rec parameters t = (btree_size t, nb_de_feuilles t, nb_noeud_1 t, nb_noeud_2 t, btree_height t) ;;


Merci d'avance.


回复BrandelClement

Re: parameters

ZeitounMarc -

Bonjour,

Le constructeur de nœud est Bin et non bin. Les constructeurs de type commencent par une majuscule en OCaml (et au contraire, les identificateurs ne doivent pas commencer par une majuscule).

--mz

回复ZeitounMarc

Re: parameters

BrandelClement -

Effectivement, j'avais pas fait attention. Mais en rectifiant le correcteur automatique me dit qu'il y a un problème au niveau de Empty  :

Fonction parameters 


Échec sur les arguments suivants:
Empty


Pourriez-vous me dire si ces 3 fonctions sont bonnes ? 

let rec nb_noeud_2 t = match t with 

    Empty -> 0

    | Bin(x,t1,t2) -> if arity t1 = 2 && arity t2 = 2 then 2 + nb_noeud_2 t1 + nb_noeud_2 t2 else 

        if (arity t1 != 2 && arity t2 = 2) || (arity t1 = 2 && arity t2 != 2) then 1 + nb_noeud_2 t1 + nb_noeud_2 t2 else 0 + nb_noeud_2 t1 + nb_noeud_2 t2;;

    

let rec nb_noeud_1 t = match t with 

    Empty -> 0

    | Bin(x,t1,t2) -> if arity t1 = 2 && arity t2 = 1 then 2 + nb_noeud_2 t1 + nb_noeud_2 t2 else 

        if (arity t1 != 1 && arity t2 = 1) || (arity t1 = 1 && arity t2 != 1) then 1 + nb_noeud_2 t1 + nb_noeud_2 t2 else 0 + nb_noeud_2 t1 + nb_noeud_2 t2;;


let rec nb_de_feuilles t = match t with 

    Empty -> 1

    | Bin(x,t1,t2) -> btree_size t1 + btree_size t2 ;;


Merci

Cordialement. 

回复BrandelClement

Re: parameters

ZeitounMarc -

Je ne sais pas ce que sont les fonctions nb_noeud_1 ni nb_noeud_2, mais si elles doivent renvoyer le nombre de nœuds d'arité 1 et 2, elles ne sont pas correctes. Il me semble que cela vient d'une incompréhension sur ce qu'est l'arité (il faut relire le poly et le diaporama 1). L'arité d'un noeud qui se trouve dans un arbre est son nombre de fils dans l'arbre.

Si on codait les arbres en C, un nœud serait une structure avec un champ pour la clé, un champ pointant sur le sous-arbre gauche, et un champ pointant sur son sous-arbre droit. Si le sous-arbre gauche est l'arbre vide, le pointeur serait NULL. Sinon, il pointerait sur  une structure représentant le fils gauche, et ainsi de suite récursivement. Idem pour le pointeur droit.

L'arité d'un nœud est donc le nombre de ces pointeurs ne valant pas NULL (0, 1 ou 2).

C'est donc une notion locale (toute l'information se trouve déjà dans le nœud). 

Pour la fonction nb_noeud1, il faut donc se demander comment calculer le nombre de nœuds d'arité 1 si on connaît ce paramètre pour chacun des sous-arbres gauche et droit, connaissant aussi l'arité de la racine.

La fonction nb_feuilles est aussi incorrecte, l'arbre vide n'est pas un noeud.

--mz