(* exercice 1 *)

let somme t =
  let n = Array.length t in
  let s = ref 0 in
  for i = 0 to n-1 do
    s := !s + t.(i)
  done ;
  !s

let _ = somme [|1;2;3;4;5;6|]

let moyenne t =
  float_of_int (somme t) /. float_of_int (Array.length t)

let _ = moyenne [|1;2;3;4;5;6|]

let min_tab t =
  let n = Array.length t in
  if n = 0 then failwith "Le tableau est vide" ;
  let m = ref t.(0) in
  for i = 1 to n-1 do
    m := min !m t.(i)
  done ;
  !m

let _ = min_tab [|1;2;3;4;0;5;1;6|]

let max_tab t =
  let n = Array.length t in
  if n = 0 then failwith "Le tableau est vide" ;
  let m = ref t.(0) in
  for i = 1 to n-1 do
    m := max !m t.(i)
  done ;
  !m

let _ = max_tab [|1;2;3;4;0;5;1;6|]

let appartient x t =
  let n = Array.length t in
  let trouve = ref false in
  for i = 0 to n-1 do
    if t.(i) = x then trouve := true
  done ;
  !trouve

let _ = appartient 0 [|1;2;3;4;0;5;1;6|]

let _ = appartient 9 [|1;2;3;4;0;5;1;6|]

let dernier_indice x t =
  let n = Array.length t in
  let indice = ref None in
  for i = 0 to n-1 do
    if t.(i) = x then indice := Some i
  done ;
  !indice

let _ = dernier_indice 1 [|2;3;1;4;0;5;1;6|]

let _ = dernier_indice 9 [|2;3;1;4;0;5;1;6|]

let premier_indice x t =
  let n = Array.length t in
  let indice = ref None in
  for i = 0 to n-1 do
    if t.(i) = x && !indice = None then indice := Some i
  done ;
  !indice

let _ = premier_indice 1 [|2;3;1;4;0;5;1;6|]

let _ = premier_indice 9 [|2;3;1;4;0;5;1;6|]

let forall f t =
  let n = Array.length t in
  let res = ref true in
  for i = 0 to n-1 do
    res := !res && f t.(i)
  done ;
  !res

let _ = forall (fun x -> x mod 2 = 0) [|2;3;1;4;0;5;1;6|]

let _ = forall (fun x -> x < 9) [|2;3;1;4;0;5;1;6|]

let exists f t =
  let n = Array.length t in
  let res = ref false in
  for i = 0 to n-1 do
    res := !res || f t.(i)
  done ;
  !res

let _ = exists (fun x -> x mod 2 = 0) [|2;3;1;4;0;5;1;6|]

let _ = exists (fun x -> x > 9) [|2;3;1;4;0;5;1;6|]

(* exercice 2 *)

exception Break

exception Trouve of int

let appartient x t =
  let n = Array.length t in
  try
    for i = 0 to n-1 do
      if t.(i) = x then raise Break
    done ;
    false
  with Break -> true

let _ = appartient 0 [|1;2;3;4;0;5;1;6|]

let _ = appartient 9 [|1;2;3;4;0;5;1;6|]

let premier_indice x t =
  let n = Array.length t in
  try
    for i = 0 to n-1 do
      if t.(i) = x then raise (Trouve i)
    done ;
    None
  with Trouve y -> Some y

let _ = premier_indice 1 [|2;3;1;4;0;5;1;6|]

let _ = premier_indice 9 [|2;3;1;4;0;5;1;6|]

let forall f t =
  let n = Array.length t in
  try
    for i = 0 to n-1 do
      if not (f t.(i)) then raise Break
    done ;
    true
  with Break -> false

let _ = forall (fun x -> x mod 2 = 0) [|2;3;1;4;0;5;1;6|]

let _ = forall (fun x -> x < 9) [|2;3;1;4;0;5;1;6|]

let exists f t =
  let n = Array.length t in
  try
    for i = 0 to n-1 do
      if f t.(i) then raise Break
    done ;
    false
  with Break -> true

let _ = exists (fun x -> x mod 2 = 0) [|2;3;1;4;0;5;1;6|]

let _ = exists (fun x -> x > 9) [|2;3;1;4;0;5;1;6|]

(* exercice 3 *)

let carres n =
  let t = Array.make n 0 in
  for i = 0 to n-1 do
    t.(i) <- i * i
  done ;
  t

let _ = carres 6

let copie_miroir t =
  let n = Array.length t in
  if n = 0 then [||]
  else
    begin
      let t' = Array.make n t.(0) in
      for i = 0 to n-1 do
        t'.(i) <- t.(n-1-i)
      done ;
      t'
    end

let _ = copie_miroir [|"a";"b";"c";"d"|]

let _ = copie_miroir [||]

let matrice n =
  let m = Array.make_matrix n n 0 in
  for i = 0 to n-1 do
    for j = 0 to n-1 do
      m.(i).(j) <- n * i + j
    done
  done ;
  m

let _ = matrice 6

(* Exercice 4 *)

let swap t i j =
  let tmp = t.(i) in
  t.(i) <- t.(j) ;
  t.(j) <- tmp

let _ =
  let t = carres 6 in
  swap t 1 4 ;
  t

let etape_bulles t =
  let n = Array.length t in
  let echange = ref false in
  for i = 0 to n-2 do
    if t.(i) > t.(i+1) then
      begin
        swap t i (i+1) ;
        echange := true
      end
  done ;
  !echange

let _ =
  let t = copie_miroir (carres 6) in
  let _ = etape_bulles t in
  t

let tri_bulles t =
  while etape_bulles t do
    ()
  done

let _ =
  let t = copie_miroir (carres 6) in
  tri_bulles t ;
  t

(* Exercice 5 *)

let indice_min t i =
  let n = Array.length t in
  let i_min = ref i in
  for j = i+1 to n-1 do
    if t.(!i_min) > t.(j) then i_min := j
  done ;
  !i_min

let _ =
  let t = [|0;1;5;3;2;6;3;4|] in
  indice_min t 2

let tri_selection t =
  let n = Array.length t in
  for i = 0 to n-1 do
    let i_min = indice_min t i in
    swap t i i_min
  done

let _ =
  let t = copie_miroir (carres 6) in
  tri_selection t ;
  t

(* Exercice 6 *)

let tri_insertion t =
  let n = Array.length t in
  for i = 1 to n-1 do
    let x = t.(i) in
    let j = ref i in
    while !j > 0 && t.(!j-1) > x do
      t.(!j) <- t.(!j-1) ;
      decr j
    done ;
    t.(!j) <- x
  done

let _ =
  let t = copie_miroir (carres 6) in
  tri_insertion t ;
  t

(* Exercice 7 *)

(* Q1 *)

let monnaie_glouton p x =
  let n = Array.length p in
  let rec monnaie x i acc = (* on essaye de rendre x avec la i-ème pièce *)
    match x with 
    | 0 -> acc
    | _ when x >= p.(i) -> monnaie (x - p.(i)) i (p.(i)::acc)
    | _ -> monnaie x (i-1) acc
  in monnaie x (n-1) []

let _ = monnaie_glouton [|1;2;5;10;20;50|] 139

let _ = monnaie_glouton [|1;3;6;12;24;30|] 48

(* Q2 *)

(* Soit on utilise la i-ème pièce, soit on ne le fait pas *)

(* Q3/4 *)

let monnaie_dyna p x =
  let n = Array.length p in
  let s = Array.make_matrix n (x+1) 0 in 
  for k = 1 to x do
    if k - p.(0) >= 0 then
      s.(0).(k) <- 1 + s.(0).(k - p.(0))
    else
      s.(0).(k) <- max_int (* c'est le plus grand entier représentable en OCaml *)
  done ;
  for i = 1 to n-1 do
    for k = 1 to x do
      if k - p.(i) < 0 then 
        s.(i).(k) <- s.(i-1).(k)
      else
      s.(i).(k) <- min (1 + s.(i).(k - p.(i))) s.(i-1).(k)
    done ;
  done ;
  (* pour Q3, renvoyer s.(n-1).(x) *)
  let rec remonte i k acc = (* reconstitue la liste des pièces *)
    let k' =  k - p.(i) in
    if k = 0 then acc
    else if k' < 0 then remonte (i-1) k acc
    else if i = 0 then remonte i k' (p.(i)::acc)
    else if s.(i-1).(k) < 1 + s.(i).(k') then remonte (i-1) k acc
    else remonte i k' (p.(i)::acc)
  in remonte (n-1) x []

let _ = monnaie_dyna [|1;3;6;12;24;30|] 48