Sujet

Correction en OCaml

Exercice 1.

let rec fib n = if n < 2 then 1 else fib (n - 1) + fib (n - 2)
      

Exercice 2.

let fib' n =
  let rec aux fib_i_ fib_i i =
    if i >= n then fib_i else aux fib_i (add_big_int fib_i_ fib_i) (succ i)
  in aux unit_big_int unit_big_int 1

let ok = eq_big_int (big_int_of_int (fib 12)) (fib' 12)
      

Exercice 3.

module Int = struct
  type t = int
  let compare = (-)
end

module IntMap = Map.Make(Int)

let memo_fib n =
  let rec aux memo i =
    try memo,IntMap.find i memo
    with Not_found ->
      let memo_bis, reponse =
	if i < 2 then
	  memo, unit_big_int
	else
	  let memo',fib_i__ = aux memo (i - 2) in
	  let memo'',fib_i_ = aux memo' (i - 1) in
	  memo'', add_big_int fib_i__ fib_i_ in
      let memo_rempli = IntMap.add i reponse memo_bis in
      memo_rempli,reponse in
  snd (aux IntMap.empty n)
      

Exercice 4.

let exp mult unit x n =
  let () = assert (n >= 0) in
  let rec aux i =
    if i = 0 then unit
    else
      let moitie = aux (i/2) in
      mult
	(if i mod 2 = 0 then unit else x)
	(mult moitie moitie)
  in aux n

let demo = exp ( * ) 1 42 9
      

Exercice 5.

let addition ((a1,b1),(c1,d1)) ((a2,b2),(c2,d2)) =
  ((add_big_int a1 a2,add_big_int b1 b2),
   (add_big_int c1 c2,add_big_int d1 d2))

let multiplication ((a1,b1),(c1,d1)) ((a2,b2),(c2,d2)) =
  ((add_big_int (mult_big_int a1 a2) (mult_big_int b1 c2),
    add_big_int (mult_big_int a1 b2) (mult_big_int b1 d2)),
   (add_big_int (mult_big_int c1 a2) (mult_big_int d1 c2),
    add_big_int (mult_big_int c1 b2) (mult_big_int d1 d2)))

let identite = ((unit_big_int, zero_big_int),(zero_big_int,unit_big_int))
let puissance x n = exp multiplication identite x n

let imprime ((a,b),(c,d)) =
  let f = string_of_big_int in
  Printf.printf "|%s %s|\n|%s %s|\n" (f a) (f b) (f c) (f d)
      

Exercice 6.

let fib'' n =
  let mat = ((zero_big_int,unit_big_int),(unit_big_int,unit_big_int)) in
  snd (snd (puissance mat n))

let ok = eq_big_int (big_int_of_int (fib 12)) (fib'' 12)

let test f x =
  let t0 = Sys.time () in
  let res = f x in
  let t1 = Sys.time () in
  Printf.printf "En %fs, résultat :\n%s\n" (t1  -. t0) (string_of_big_int res)

let () = test fib' 100000
let () = test fib'' 100000