(*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*) (* Nicolas Pécheux *) (* Monday, 23 April 2018 *) (* http://cpge.info *) (*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*) (** Question 1 **) let produit ((re1, im1) : complexe) ((re2, im2) : complexe) = ((re1 *. re2 -. im1 *. im2, re1 *. im2 +. im1 *. re2) : complexe) ;; produit (0., 1.) (0., 1.);; (** Question 3 **) type complexe = {re : float; im : float};; let somme {re = re1; im = im1} {re = re2; im = im2} = {re = re1 +. re2; im = im1 +. im2} ;; somme {re = 0.; im = 1.} {re = 0.; im = 1.};; let produit z1 z2 = {re = z1.re *. z2.re -. z1.im *. z2.im; im = z1.re *. z2.im +. z1.im *. z2.re} ;; produit {re = 0.; im = 1.} {re = 0.; im = 1.};; (** Question 4 **) let rec indice element liste = match liste with | [] -> None | tete :: queue when tete = element -> Some 0 | _ :: queue -> match indice element queue with | None -> None | Some i -> Some (i + 1) ;; indice 5 [2; 1; 5; 2; 5] indice 3 [2; 1; 5; 2; 5] type 'a arbre = Vide | Noeud of 'a * 'a foret and 'a foret = 'a arbre list;; let exemple = Noeud (5, [Noeud (9, []); Noeud (1, [Noeud (3, []); Noeud (8, [])]); Noeud (7, [Noeud (6, [])]) ]);; (** Question 5 **) let rec hauteur arbre = match arbre with | Vide -> -1 | (Noeud (_, fils)) -> 1 + hauteur_foret fils and hauteur_foret foret = match foret with | [] -> -1 | arbre :: autres -> max (hauteur arbre) (hauteur_foret autres) ;; hauteur exemple;; (** Question 6 **) let rec parcours_suffixe arbre = match arbre with | Vide -> () | Noeud (etiquette, fils) -> parcours_foret fils; print_int etiquette and parcours_foret foret = match foret with | [] -> () | arbre :: autres -> parcours_suffixe arbre; parcours_foret autres ;; parcours_suffixe exemple;; (** Question 7 **) let rec parcours_prefixe arbre = match arbre with | Vide -> [] | Noeud (etiquette, fils) -> etiquette :: (parcours_foret fils) and parcours_foret foret = match foret with | [] -> [] | arbre :: autres -> (parcours_prefixe arbre) @ (parcours_foret autres) ;; parcours_prefixe exemple;; let rec parcours_suffixe arbre = match arbre with | Vide -> [] | Noeud (etiquette, fils) -> parcours_foret fils @ [etiquette] and parcours_foret foret = match foret with | [] -> [] | arbre :: autres -> (parcours_suffixe arbre) @ (parcours_foret autres) ;; parcours_suffixe exemple;; (** Question 8 **) let rec degre arbre = match arbre with | Vide -> 0 | (Noeud (_, fils)) -> degre_foret fils 0 0 (* Trouve le degré d'une forêt de fils sachant que l'on a déjà vu n fils dont le degré est d *) and degre_foret foret n d = match foret with | [] -> max n d (* n est ici le degré du père *) | arbre :: autres -> degre_foret autres (n + 1) (max d (degre arbre)) ;; degre exemple;; (** Question 9 **) type 'a arbre = {etiquette : 'a; fils : 'a arbre list};; let exemple = {etiquette = 5; fils = [ {etiquette = 9; fils = []}; {etiquette = 1; fils = [ {etiquette = 3; fils = []}; {etiquette = 8; fils = []} ] }; {etiquette = 7; fils = [{etiquette = 6; fils = []}]} ] };; let rec taille arbre = 1 + taille_foret arbre.fils and taille_foret foret = match foret with | [] -> 0 | arbre :: autres -> (taille arbre) + (taille_foret autres) ;; taille exemple;; let rec hauteur arbre = 1 + hauteur_foret arbre.fils and hauteur_foret foret = match foret with | [] -> -1 | arbre :: autres -> max (hauteur arbre) (hauteur_foret autres) ;; taille exemple;; (** Question 10 **) (* On ne peut pas écrire cette fonction car le type arbre est immuable. Comme pour les listes on ne peut pas modifier un arbre une fois celui-ci créé *) (** Question 11 **) let est_feuille arbre = arbre.fils = [] ;; let rec nb_feuilles arbre = (if est_feuille arbre then 1 else 0) + nb_feuilles_foret arbre.fils and nb_feuilles_foret foret = match foret with | [] -> 0 | arbre :: autres -> (nb_feuilles arbre) + (nb_feuilles_foret autres) ;; nb_feuilles exemple;; (** Question 12 *) let rec max_etiquettes arbre = max_etiquettes_foret arbre.etiquette arbre.fils and max_etiquettes_foret maxi fils = match fils with | [] -> maxi | arbre :: autres -> max_etiquettes_foret (max maxi (max_etiquettes arbre)) autres ;; max_etiquettes exemple;; (** Question 13 **) let rec max_somme_branche arbre = arbre.etiquette + (max_somme_branche_foret arbre.fils) and max_somme_branche_foret fils = match fils with | [] -> 0 | arbre :: autres -> max (max_somme_branche arbre) (max_somme_branche_foret autres) ;; max_somme_branche exemple;;