(*********************************************)
(*                                           *)
(*      Corrige du TP3 - fevrier 2005        *)
(*                                           *)
(*********************************************)

(**********************)
(***** Question 1 *****)
(**********************)

[| 1; 2; 3; 4 |];;

let v1000 = make_vect 1000 0.0;;

let random_vect n =
 let v = make_vect n 0.0 in
  for i=0 to (n-1) do v.(i) <- random__float 1.0; done;
  v;;

(***** Question 2 *****)

(**********************)
(***** Question 3 *****)
(**********************)

let sub v a b =
 let w = make_vect (b-a+1) v.(0) in
  for i=a to b do w.(i-a) <- v.(i); done;
  w;;

let cat v w =
 let nv = vect_length v
 and nw = vect_length w in
  let t = make_vect (nv+nw) v.(0) in
   for i=0 to (nv-1) do t.(i) <- v.(i); done;
   for i=0 to (nw-1) do t.(nv+i) <- w.(i); done;
   t;;

sub [|1;2;3;4;5|] 2 3;;
sub_vect [|1;2;3;4;5|] 2 3;;

cat [|1;2;3|] [|4;5|];;
concat_vect [|1;2;3|] [|4;5|];;

let rand_vect n x = map_vect random__int (make_vect n x);;

(**********************)
(***** Question 4 *****)
(**********************)

let vect_min v =
 let m = ref v.(0) in
  for i=2 to (vect_length v)-1 do
   if v.(i) < !m then m:=v.(i);
  done;
  !m;;

let vect_max v =
 let m = ref v.(0) in
  for i=2 to (vect_length v)-1 do
   if v.(i) > !m then m:=v.(i);
  done;
  !m;;

(**********************)
(***** Question 5 *****)
(**********************)

let addition p1 p2 = let s = max p1 p2 in
 for i=0 to (min (vect_length p1) (vect_length p2)) - 1do
  s.(i)<-p1.(i)+.p2.(i)
 done;
s;;

addition [|1.;2.;3.|] [|0.;1.|];;

let mult p1 p2 =
 let d1 = vect_length p1
 and d2 = vect_length p2 in
  let v = make_vect (d1+d2-1) 0.0 in
   for i=0 to d1-1 do
    for j=0 to d2-1 do
     v.(i+j) <- v.(i+j) +. p1.(i) *. p2.(j);
    done;
   done;
   v;;

mult [|1.;1.;1.;1.;1.|] [|1.;1.;1.;1.;1.|];;

let deriv p = let n = vect_length p in
 let d = make_vect (n-1) 0.0 in
  for i=0 to n-2 do d.(i)<-p.(i+1)*.float_of_int(i+1); done;
  d;;

deriv [|1.;1.;1.;1.;1.|];;

(***Bonus***)

let print_num x =
 if x=float_of_int(int_of_float x) then
  print_int(int_of_float x)
 else
  print_string(string_of_float x);;

let print_poly p = let n = vect_length p in
 if n>0 then print_num p.(0);
 for i=1 to n-1 do if p.(i)<>0.0 then (
  if p.(i)<0.0 then print_string " - "
  else print_string " + ";
  let t = abs_float(p.(i)) in
  if t<>1.0 then (
   print_num t;
   print_string "*";
  );
  print_string "x";
  if i>1 then (
   print_string "^";
   print_int i;
  );
 ); done;
print_newline();;

print_poly [|2.; 1.; 0.; -1.; 0.; 4.0|];;

(**********************)
(***** Question 6 *****)
(**********************)

let poly_val p x =
 let n = vect_length p
 and r = ref 0.0 in
  for i=n-1 downto 0 do r:= x *. !r +. p.(i); done;
  !r;;

poly_val [|1.;1.;1.;1.|] 1.;;
poly_val [|1.;1.;1.;1.|] 0.;;
poly_val [|1.;1.;1.;1.|] (-1.);;

let racine p a b =
 let aa=ref a and bb=ref b in
  while abs_float(!aa -. !bb) > abs_float(1e-8 *.(!aa +. !bb)) do
   let c = 0.5 *.(!aa +. !bb) in
   if (poly_val p !aa) *. (poly_val p c) < 0.0 then bb:=c
   else aa:=c;
  done;
  0.5 *.(!aa +. !bb);;

racine [|3.0; 0.0; -1.0|] 0.0 2.0;;
sqrt(3.0);;

(***Bonus***)

let iter_newton p p' x =
 x -. (poly_val p x) /. (poly_val p' x);;

let newton p x0 =
 let p' = deriv p and x = ref x0 and pas_fini = ref true in
 while !pas_fini do
  let x2 = iter_newton p p' !x in
   pas_fini := abs_float(!x-.x2) > abs_float(1e-8*.(!x+.x2));
   x := x2;
 done;
 !x;;

let gros = make_vect 10002 0.0;;
gros.(0) <- -1e100;;
gros.(10001) <- 1.0;;

newton gros 1.023;;
racine gros 1.022 1.024;;

(**********************)
(***** Question 7 *****)
(**********************)

let min_sub_vect v i j = let p = ref i in
 for k=i+1 to j do if v.(k)<v.(!p) then p:=k; done;
 !p;;

let swap_vect v i j = let c = v.(i) in
 v.(i)<-v.(j);
 v.(j)<-c;;

let select_sort v = let n = vect_length v in
 for i=0 to n-2 do swap_vect v i (min_sub_vect v i (n-1)); done;;

let txt = [|"caml";"c";"'";"est";"super";"cool"|];;
select_sort txt;;
txt;;

(**********************)
(***** Question 8 *****)
(**********************)

let mult_mat m1 m2 =
 let p=vect_length m1 and q=vect_length m1.(0)
 and r=vect_length m2 and s=vect_length m2.(0) in
if q<>r then failwith "Les matrices ont mauvaise dimension";
let m = make_matrix p s 0.0 in
 for i=0 to p-1 do for j=0 to s-1 do for k=0 to q-1 do
  m.(i).(j) <- m.(i).(j) +. m1.(i).(k) *. m2.(k).(j);
 done; done; done;
 m;;

let ii = [|[|0.; 1.|];[|-1.; 0.|]|];;
mult_mat ii ii;;

(***Bonus***)

let copy_matrix m = let lignes = vect_length m in
 let m2 = make_vect lignes [||] in
 for i=0 to lignes-1 do m2.(i)<-copy_vect m.(i); done;
 m2;;

let jj = copy_matrix ii;;
jj.(0).(0)<-25. ;;
jj;;
ii;;

(**********************)
(***** Question 9 *****)
(**********************)

let swap_vect v i j = let c = v.(i) in
 v.(i)<-v.(j);
 v.(j)<-c;;

let permute v = let n = vect_length v in
 for i=n downto 2 do swap_vect v (random__int i) (i-1); done;;

(***********************)
(***** Question 10 *****)
(***********************)

(** quadratique **)

let smax v =
let n=vect_length v and max=ref 0 in
 for debut=0 to n-1 do
  let somme = ref 0 in
   for fin=debut to n-1 do
    somme:= !somme+v.(fin);
    if !somme > !max then max := !somme;
   done;
 done;
!max;;

let essai = map_vect (fun x->(random__int 20)-10) (make_vect 20 0);;

smax essai;;

(** lineaire **)

let smax2 v =
let n = vect_length v and max=ref 0 and somme = ref 0 in
for i=0 to n-1 do
 somme := !somme + v.(i);
 if !somme > !max then max:= !somme;
 if !somme < 0 then somme:=0;
done;
!max;;

let essai = map_vect (fun x->(random__int 20)-10) (make_vect 20 0);;

smax essai;;
smax2 essai;;