(* Exercice 1 *)

let a = 42 ;;

let f x = 3*x+1 ;;

f 1 ;;

(*let f x = 3.*x + 1 ;;*)

(* Exercice 2 *)
let f1 x y = 2*x-3*y ;;
let f2 = fun x y z -> x ;;
let f3 x y = x y ;;
let f4 x = sin x +. x ;;
let f5 x y = if x -. 1. > y then x else y ;;
let f6 f g h = f (g h) ;;
let f7 = fun x y z -> (x, y, z) ;;
let f8 (x, y) = x * (x * y) ;;
let f9 x y = x  (x y) ;;

(* Exercice 3 *)
let implication p q = not p || q ;;

(* Exercice 4 *)
min 1 2 ;;

let min3 x y z = min (min x y) z ;;

min3 2 3 5 ;;

let max4 x y z t = max (max (max x y) z) t ;;

(* Exercice 5 *)
let x = sqrt 2. in (1. +. x +. x**3.)/.(1. +. exp x) ;;

let th x =
  let exp2x = exp (2. *. x) in
  (exp2x -. 1.) /. (exp2x +. 1.)
;;

(* Exercice 6 *)
let carre n = n*n ;;

(* Exercice 7 *)
let g1 f = (f(0.)+.f(1.))/.2. ;;

let g2 f = function x -> f(x)**2. ;;

let g3 f = function (x:float) -> f (f x) ;;

let g4 (f:float->float) = function x -> f(x+.1.) ;;

(* Exercice 8 *)
let c f g x=f(g x);;

(* Exercice 9 *)
let nombreChiffres x =
  1 + int_of_float(log(float_of_int x)/.log 10.)
;;

nombreChiffres 301 ;;

let nombreChiffresBase a b = 
  1 + int_of_float(log(float_of_int a)/.log (float_of_int b))
;;

nombreChiffresBase 64 2 ;;

(* Exercice 10 *)
let mult x y = x*y ;;

let mult2(x, y) = x*y ;;

let decurryfier f = function (x,y) -> f x y ;;

decurryfier mult ;;

(* Exercice 11 *)
let puiss x n =
  let r = ref 1 in
  for i=1 to n do
    r := !r * x
  done ;
  !r
;;

(* Exercice 12 *)
let sdc n =
  let s = ref 0 in
  let q = ref n in
  while !q != 0 do
    s := !s + (!q mod 10) ;
    q := !q/10
  done ;
  !s
;;

sdc 4948353 ;;

(* Exercice 13 *)
let miroir n =
  let puiss10 = ref (puiss 10 ((nombreChiffres n)-1)) in
  let q = ref n in
  let m = ref 0 in
  while !q != 0 do
    m := !m + !puiss10 * (!q mod 10) ;
    puiss10 := !puiss10/10 ;
    q := !q/10
  done ;
  !m
;;

miroir 123 ;;

(* Exercice 14 *)
let racine x epsilon =
  let u = ref 1. in
  while abs_float(!u -. x /. !u) >= epsilon do
    u := 0.5 *. (!u +. x /. !u)
  done ;
  !u
;;

(* Exercice 15 *)
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
;;

(* Exercice 16 *)
let inverse t =
  let n = Array.length t in
  let t' = Array.make n 0 in
  for i=n-1 downto 0 do
    t'.(i) <- t.(n-1-i)
  done ;
  t'
;;

(* Exercice 17 *)
let inverse_en_place t =
  let n = Array.length t in
  for i=0 to (n-1)/2 do
    let x = t.(i) in
    t.(i) <- t.(n-1-i) ;
    t.(n-1-i) <- x
  done
;;


(* Exercice 18 *)
let tri_bulle t =
  let swap i j =
    let x = t.(i) in
    t.(i) <- t.(j) ;
    t.(j) <- x
  in
  let n = Array.length t in
  for i=n-1 downto 0 do
    for j=0 to i-1 do
      if t.(j) > t.(j+1) then 
        swap j (j+1)
    done
  done
;;

(* Exercice 19 *)
let sinc x = match x with
  |0. -> 1.
  |_ -> sin(x) /. x
;;

(* Exercice 20 *)
(*
let f x = 1 - sin x ;;

let g x = match x with
  | x when x<0. -> 0.
  | x -> x**2.
;;
*)

(* Exercice 21 *)
type entiersGauss = {re : int ; im : int} ;;

let nombreI = {re = 0 ; im = 1} ;;

let addition x y = {re = x.re + y.re ; im = x.im + y.im} ;;

let multiplication x y =
  {re = x.re * y.re - x.im * y.im ; im = x.im * y.re +  x.re * y.im}
;;

let conjugaison x = {re = x.re ; im = -x.im} ;;

(* Exercice 22 *)
type reelsEtendus =
    Reel of float 
  | Inf
  | MoinsInf
  | NaN
;;

let addition x y = match x,y with
  | Reel(a), Reel(b) -> Reel(a+.b)
  | Inf, Inf -> Inf
  | MoinsInf, MoinsInf -> MoinsInf
  | Reel(a), z -> z
  | z, Reel(a) -> z
  | _, _ -> NaN
;;

let multiplication x y = match x,y with
  | Reel(a), Reel(b) -> Reel(a*.b)
  | Inf, Inf -> Inf
  | MoinsInf, MoinsInf -> Inf
  | NaN, _ -> NaN
  | _, NaN -> NaN
  | Reel(a), z when a>0. -> z
  | Reel(a), Inf when a<0. -> MoinsInf
  | Reel(a), MoinsInf when a<0. -> Inf
  | z, Reel(a) when a>0. -> z
  | Inf, Reel(a) when a<0. -> MoinsInf
  | MoinsInf, Reel(a) when a<0. -> Inf
  | _, _ -> NaN
;;

(* Exercice 23 *)
let sous_tableau_max v =
  let n = Array.length v in
  let sm = ref 0 in
  for i=0 to n-1 do
    let si = ref 0 in
    for j=i to n-1 do
      si := !si + v.(j) ;
      if !si > !sm then
          sm := !si
    done
  done ;
  !sm
;;

let sous_tableau_max_lineaire v =
  let n = Array.length v in
  let s0j = ref 0 in
  let s0jm = ref 0 in
  let jm = ref 0 in
  for j=0 to n-1 do
    s0j := !s0j + v.(j) ;
    if !s0j > !s0jm then
      begin
        s0jm := !s0j ;
        jm := j
      end
  done ;
  let sm = ref !s0jm in
  let sijm = ref !s0jm in
  for i=0 to !jm do
    sijm := !sijm - v.(i) ;
    if !sijm > !sm then
      sm := !sijm
  done ;
  !sm
;;

(* Exercice 24 *)
let decomposition t s =
  let p = Array.length t in
  let dec = Array.make_matrix (s+1) (p+1) 0 in
  (* il y a une façon de décomposer k=0, peut importe les pièces
   * donc on remplit la première ligne de 1 *)
  for i=0 to p do
    dec.(0).(i) <- 1
  done ;
  (* il y a aucun moins de décomposer k s'il n'y a pas de pièces,
   * donc on laisse la colonne i=0 remplie de 0 *)
  (* on démarre la programmation dynamique *)
  for k=1 to s do
    for i=1 to p do
      (* pour décomposer k avec les i premières pièces :
       *   - soit on ne se sert jamais de la i-ème pièce ;
       *   - soit on s'en sert au moins une fois (donc k >= t.(i-1)),
       *     et on compte les manières de décomposer le reste *)
      dec.(k).(i) <- dec.(k).(i-1) +
                     if k >= t.(i-1)
                     then dec.(k-t.(i-1)).(i)
                     else 0
    done
  done ;
  dec.(s).(p)
;;

decomposition [|1; 2; 3|] 4 ;; (* doit renvoyer 4 *)