Questions / réponses

is_perfect

is_perfect

Arthur Cargnelli –
Vastuste arv 2

Bonjour ,


Voici mon code pour la fonction is_perfect :

let is_perfect t =
  if is_full t = false then false else
    let rec aux t_list d  =
      match t_list with
      |[]-> true
      |(Empty,h)::q -> aux q d
      |(Bin(x,l,r),h)::q -> aux ((l,h+1):kurvastabr,h+1)::q) d
      |(Bin(x,Empty,Empty),h)::q -> if d = -1 then d = h else if h = d then aux q d else false
    in
    aux [(t,0)] (-1)

mais je ne vois pas ou est mon erreur car sur mon ordinateur la fonction passe bien alors que sur moodle non .

Merci de votre aidre.

Cordialement ,

Arthur

Vastuses Arthur Cargnelli

Re: is_perfect

Marc Zeitoun –

Bonjour,

Le code n'est pas correct et ne doit pas donner le bon résultat sur une autre machine. Le test fournit un exemple dont il faut se servir pour corriger. Il donne un arbre qui n'est pas parfait mais sur lequel la fonction écrite renvoie true. Il faut rejouer le code sur ce test pour comprendre l'erreur. On peut le simplifier (ou relancer l'évaluation en espérant un exemple plus petit). Par exemple, le code renvoie true sur l'arbre suivant, qui n'est pas parfait (il n'y a pas d'arbre parfait à 5 noeuds) :


let leaf v = Bin(v, Empty, Empty)
let _ = is_perfect (Bin (1, leaf 2, Bin (3, leaf 4, leaf 5)))
Au passage, l'interpréteur OCaml indique qu'un cas n'est jamais appliqué, ce qui est suspect. 

--mz

Vastuses Marc Zeitoun

Re: is_perfect

Marc Zeitoun –

Au passage, on ne demandera pas de fonctions récursives terminales sur les arbres.

Par contre, il est souhaitable d'avoir un algorithme faisant un nombre linéaire d'appels récursifs par rapport à la taille de l'arbre.