Bonjour,
Est ce qu'on peut avoir une correction des fonctions arbre quasi parfait et génération d'un arbre quasi parfait s'il vous plaît.
Merci d'avance
Saleck BAYA
In riposta a Saleck Baya
Re: arbre quasi parfait et génération d'un arbre quasi parfais
di Idris Dulau -
Salut,
Je n'ai très certainement pas fait de la meilleure façon mais ça fonctionne,
Si quelqu'un a fait différemment je suis preneur.
DULAU Idris
(* Abres quasi-parfaits *)
type 'a btree = Empty | Node of 'a * 'a btree * 'a btree;;
let rec btree_is_quasi_perfect t =
let rec perfect t h =
match t with
|Empty -> (h = -1)
|Node(a,l,r) -> (perfect l (h-1)) && (perfect r (h-1))
in
let rec quasi_perfect t h =
match t with
|Empty -> false
|Node(a,l,r) -> ((perfect l (h-1)) && (quasi_perfect r (h-1))) ||
((perfect l (h-1)) && (perfect r (h-2))) ||
((quasi_perfect l (h-1)) && (perfect r (h-2)))
in
let rec btree_height t =
match t with
|Empty -> -1
|Node(a,l,r) -> 1 + max (btree_height l) (btree_height r)
in
(perfect t (btree_height t)) || (quasi_perfect t (btree_height t))
val btree_is_quasi_perfect : 'a btree -> bool = <fun>
---------------------------------------------------------------------
(* Génération d'arbres quasi-parfaits *)
(* Fonction qui à x associe 2 à la puissance x *)
let rec pow2 x =
if x = 0
then 1
else 2 * pow2 (x-1)
val pow2 : int -> int = <fun>
(* Fonction qui prend une hauteur et renvoie le nombre de noeuds
de l'arbre parfait de même hauteur *)
let rec h_to_n h =
if h < 0
then 0
else pow2 (h+1) -1
val h_to_n : int -> int = <fun>
(* Fonction qui a x associe la partie entière du logarithme
en base 2 de x *)
let log2 x =
let rec aux x c =
if x < 1
then c - 1
else aux (x/2) (c+1)
in
aux x 0
val log2 : int -> int = <fun>
(* Fonction qui prend un nombre de noeuds et renvoie la hauteur
du plus grand arbre parfait que l'on peut former avec *)
let rec n_to_h n =
if n < 1
then -1
else log2 (n+1) -1
val n_to_h : int -> int = <fun>
(* Nombres de noeuds ne permettant pas de générer un
arbre parfait supplémentaire avec la Fonction n_to_h *)
let exced_of_nodes nodes = nodes - (h_to_n ( n_to_h nodes))
val exced_of_nodes : int -> int = <fun>
(* Genere un arbre parfait de hauteur h *)
let rec btree_perfect h =
let rec aux h t =
if h >= 0
then aux (h-1) (Node(0,t,t))
else t
in
aux h Empty
val btree_perfect : int -> int btree = <fun>
(* Retourne la hauteur d'un arbre *)
let rec btree_height t =
match t with
|Empty -> -1
|Node(a,l,r) -> 1 + max (btree_height l) (btree_height r)
val btree_height : 'a btree -> int = <fun>
(* Teste si l'arbre est parfait *)
let rec btree_is_perfect t =
let rec aux t h =
match t with
|Empty -> (h = -1)
|Node(a,l,r) -> (aux l (h-1))&&(aux r (h-1))
in
aux t (btree_height t)
val btree_is_perfect : 'a btree -> bool = <fun>
(* Arité d'un arbre *)
let rec arity t =
match t with
|Empty -> 0
|Node(a,l,r) when l=Empty && r=Empty -> 0
|Node(a,l,r) when l!=Empty && r!=Empty -> 2
|_ -> 1
val arity : 'a btree -> int = <fun>
(* Ajout d'un zéro aux feuilles *)
let rec add t =
match t with
|Empty -> Node(0,Empty,Empty)
|Node(a,l,r) when arity t = 1 -> Node(a, l, add r)
|Node(a,l,r) when (arity l = 2) && (arity l > arity r) -> Node(a, l, add r)
|Node(a,l,r) when (btree_is_perfect l) && (not(btree_is_perfect t)) && (btree_height l > 1) -> Node(a, l, add r)
|Node(a,l,r) -> Node(a, add l, r)
(* Genere un arbre quasi parfait à n noeuds *)
let rec btree_quasi_perfect n =
let rec aux n t c =
if c < 1
then t
else aux (n-1) (add t) (c-1)
in
aux n (btree_perfect (n_to_h n)) (exced_of_nodes n)
In riposta a Idris Dulau
Re: arbre quasi parfait et génération d'un arbre quasi parfais
di Marc Zeitoun -
Comme je l'ai dit en cours, l'intérêt d'un tel forum est d'expliquer en français, et pas de poster du code sans aucun commentaire. Merci d'en tenir compte les fois prochaines.
--mz
In riposta a Marc Zeitoun
Re: arbre quasi parfait et génération d'un arbre quasi parfais
di Idris Dulau -
Bonsoir,
Autant pour moi,
Cependant,
Pourrions nous avoir à disposition la correction des exercices du moodle une fois la date de rendu dépassée ?
Cordialement,
DULAU Idris