Correction de Thomas

• Sujet

• Retour à la page des TP

(* Question 1 *)

let make_matrix n m e =
  let mat = make_vect n [||] in
  for i = 0 to n-1 do
    mat.(i) <- make_vect m e
  done;
  mat
;;

(* Question 2 *)

let rec tri_selection = function
  | [] -> []
  | h :: t ->
    let rec extract_max m acc = function
      | [] -> m, acc
      | h :: t when h > m -> extract_max h (m::acc) t
      | h :: t -> extract_max m (h::acc) t
    in
    let h, t = extract_max h [] t in
    h :: tri_selection t
;;

(* un meilleur tri : le tri fusion *)

let rec split l1 l2 = function
  | [] -> l1, l2
  | [x] -> x::l1, l2
  | a :: b :: t -> split (a::l1) (b::l2) t
;;

let rec merge = function
  | [], l | l, [] -> l
  | h1 :: t1, h2 :: t2 when h1 < h2 -> h2 :: (merge (h1::t1, t2))
  | h :: t, l -> h :: (merge (t, l))
;;

let rec tri_fusion = function
  | [] -> []
  | [x] -> [x]
  | l ->
    let l1, l2 = split [] [] l in
    merge (tri_fusion l1, tri_fusion l2)
;;

(* Question 3 *)

let rec rendu_glouton l m = match l with
  | [] -> if m = 0 then [] else failwith "Bad currency"
  | h :: t -> (m/h)::(rendu_glouton t (m mod h))
;;

(* Question 5 *)

let est_representable l m =
  let p = list_length l in
  let dyn = make_matrix (m+1) (p+1) None in
  let rec est_representable i j l =
    match dyn.(i).(j) with
      | Some b -> b
      | None ->
        let res =
          match l with
            | [] -> i = 0
            | h :: t -> i >= h && est_representable (i-h) j l || est_representable i (j-1) t
        in
        (dyn.(i).(j) <- Some res; res)
  in
  est_representable m p l
;;

(* Question 6 *)

let rendu_dynamique l m=
  let p = list_length l in
  let dyn = make_matrix (m+1) (p+1) None in
  let rec rendu_dynamique i j l =
    match dyn.(i).(j) with
      | Some v -> v
      | None ->
        let res =
          match l with
            | [] -> if i = 0 then Some (0, []) else None
            | h :: t ->
              if i >= h then
                match rendu_dynamique (i-h) j l, rendu_dynamique i (j-1) t with
                  | Some (a, la), Some (b, _) when a+1 < b -> Some (a+1, h::la)
                  | Some (a, la), None -> Some (a+1, h::la)
                  | _, v -> v
              else
                rendu_dynamique i (j-1) t 
        in
        (dyn.(i).(j) <- Some res; res)
  in
  match rendu_dynamique m p l with
    | Some (_, l) -> l
    | None -> failwith "Bad currency"
;;

(* Question 7 *)

let decompose_carre n =
  let rec carre_inf i =
    if i*i > n then []
    else i*i :: carre_inf (i+1)
  in
  rendu_dynamique (carre_inf 1) n
;;

(* Question 8 *)

let decompose_fibo n =
  let rec rendu_fibo n = function
    | [] -> []
    | h :: t when n >= h -> h :: (rendu_fibo (n-h) t)
    | _ :: t -> rendu_fibo n t
  in
  let rec fibo = function
    | [] | [_] -> fibo [2;1]
    | a :: b :: t when a+b <= n -> fibo (a+b::a::b::t)
    | l -> l
  in
  rendu_fibo n (fibo [])
;;

(* Question 9 *)

let planning_nb l =
  let l = tri_fusion l in
  let rec enleve_incompatible = function
    | [] -> []
    | [x] -> [x]
    | (d1, f1) :: (_, f2) :: t when d1 < f2 -> enleve_incompatible ((d1, f1) :: t)
    | h :: t -> h :: enleve_incompatible t
  in
  enleve_incompatible l
;;