(* -1 / 1 *)

(* Ça ne fait pas une "deep copy": les k lignes de la matrices
 * sont stockées au même endroit, changer un élément d'une certaine ligne
 * le changera également dans toutes les autres lignes
 *)

(* -1 / 2 *)

let rec binom_rec n k = match (n, k) with
| (_, 0) -> 0
| (0, _) -> 1
| _      -> binom_rec (n-1) k + binom_rec (n-1) (k-1)

let binom_iter n k = 
        if n = 0 && k = 0 then 1 else
        let values = Array.make_matrix (n+1) (k+1) 0 in
        let result = ref 0 in
        for i = 0 to n do
                values.(i).(0) <- 1;
                for j = 1 to min i k do
                        values.(i).(k) <- values.(i-1).(k) + values.(i-1).(k-1)
                done;
        done;
        values.(n).(k);;

(* -1 / 3 *)

let start_time = ref Sys.time ();;
binom_iter 12 234;;
let duration_iter = !start_time - Sys.time ();;
start_time := Sys.time ();;
binom_rec 12 234;;
let duration_rec = !start_time - Sys.time ();;

(* 0 / 1 *)

(* Elle permet de calculer  x^n  *)

(* 0 / 2 *)

(* Notons  a  la suite des valeurs prises.
 * Procédons par récurrence.
 * Initialisation(n=0)
 * a_0 = 1 = x^0
 * Hérédité. Soit  n in NN  . Supposons  a_n = x^n  .
 * Traitons deux cas.
 * __1er cas__ (  n+1 in 2NN  )
 * On a  a_(n+1) = (a_n/2)^2 = x^n/4
 * __2e cas__
 * On a  a_(n+1) = x (a_n/2)^2 = x x^n/4 = x^(n+1)/4
 *
 *)

(* Montrons que pour tout  n in NN_+, f x n  calcule bien  x^n.
 * 1) Le seul cas de base est  n = 0.  La fonction retourne  1 = x^0  . Donc la fonction est correcte.
 * 2) Si  n  est pair: l'appel récursif se fait sur  x (n/2)  .
 * Supposons qu'il est correct, ie  f x (n/2) = x^(n/2)
 * La fonction retourne  (f x (n/2))^2 = (x^(n/2))^2 = x^n  par hypothèse et par parité de  n
 * Dans ce cas, la fonction est correcte
 * Si  n  est impair: l'appel récursif se fait sur  x |_ n/2 _| = x ((n-1)/2)
 * Supposons qu'il est correct, ie  f x ((n-1)/2) = x^((n-1)/2)
 * On a  x (f x ((n-1)/2))^2 = x (x^((n-1)/2))^2 = x x^(n-1) = x^n
 * D'après le théorème de correction, la fonction est correcte.
 *)

(* 0 / 3 *)

(* Montrons que 0 est un cas de base: ok!
 * Si  n in 2NN^ast
 * L'appel récursif se fait sur  n/2 < n
 * Si  n in 2NN+1
 * L'appel récursif se fait sur  (n-1)/2 < n
 * Donc d'après le théorème de terminaison, la fonction termine.
 *)

(* 0 / 4 *)

(* On fait beaucoup moins de multiplication pour  n  grand:
 * pour 512:
 * on fait 1 produit
 * ...
 * on fait 10 produits au lieu de 1024
 *)

(* 1 / 1 *)

(* Explication aux de fact:
 *      acc
 * n    1       n!/n!
 * n-2  n       n!(n-1)!
 * n-3  n(n-1)  n!/(n-2)!
 * ...
 * 0    n(n-1)...1 n!/0! = n!
 *)

let rec fibo_e n = match n with
| 0 -> 0
| 1 -> 1
| _ -> fibo_e (n-1) + fibo_e (n-2)

let fibo n = let rec aux n acc1 acc2 = match n with
| 0 -> acc1
| 1 -> acc2
| _ -> aux (n-1) acc2 (acc1 + acc2)
in aux n 0 1;;

fibo 1234;;

(* aux de fibo
 *      acc1            acc2
 * n    0 = F_0         1 = F_1
 * n-1  1 = F_1         1 = F_2 = F_1 + F_0
 * n-2  1 = F_2         2 = F_3 = F_2 + F_1
 * ...
 * 0    F_(n-1)         F_n
 *)

(* 1 / 2 *)

let compare_exec_time better worse test_data = 
        let start_better = Sys.time  () in
        better test_data;
        let duration_better = Sys.time () -. start_better in
        let start_worse = Sys.time () in
        worse test_data;
        let duration_worse = Sys.time () -. start_worse in
        duration_worse -. duration_better;;

(* 1 / 3 *)

(* Appels récurisivs dupliqués dans la première *)

(* 2 / 1 *)

let numero x y = match (x, y) with
| (0, 0) -> 0
| (_, 0) -> 1 + numero 0 (x-1)
| (x, y) -> 1 + numero (x+1) (y-1)

(* 2 / 2 *)

(*