Chapitre 2

(* {\em Fibonaci, voir page \pageref{prog:fib}} *)
let rec fib n =
 if n <= 1 then 1
 else fib (n - 1) + fib ( n - 2);;

(* {\em Factorielle, voir page \pageref{prog:fact}} *)
let rec fact n =
  if n <= 1 then 1
  else n * fact (n - 1);;

(* {\em Triangle de Pascal, voir page \pageref{prog:fact}} *)
let rec c n p =
 if n = 0 || p = n then 1
 else c (n - 1) (p - 1) + c (n - 1) p;;

(* {\em Fibonaci itératif, voir page \pageref{prog:fib-iteratif}} *)
let fib n =
 let u = ref 1 and v = ref 1 in
 for i = 2 to n do
  let u0 = !u and v0 = !v in
  u := u0 + v0;
  v := u0
 done;
 !u;;

(* Le même en style fonctionnel *)
let fib n =
 let rec fib_aux k u v =
  if k > n then u
  else fib_aux (k + 1) (u + v) u in
 fib_aux 2 1 1;;

(* {\em La fonction d'Ackermann, voir page \pageref{prog:ackermann}} *)
let rec ack m n =
 if m = 0 then n + 1 else
 if n = 0 then ack (m - 1) 1 else
 ack (m - 1) (ack m (n - 1));;

(* {\em La fonction 91, voir page \pageref{prog:fn-91}} *)
let rec f91 n =
 if n > 100 then n - 10
 else f91 (f91 (n + 11));;

(* {\em La fonction de Morris, voir page \pageref{prog:fn-morris}} *)
let rec g m n =
 if m = 0 then 1
 else g (m - 1) (g m n);;

(* {\em Les tours de Hanoi, voir page \pageref{prog:hanoi}} *)
let rec hanoi n i j =
 if n > 0 then begin
  hanoi (n - 1) i (6 - (i + j));
  printf "%d -> %d\n" i j;
  hanoi (n - 1) (6 - (i + j)) j;
 end;;

(* {\em La courbe du dragon, voir page \pageref{prog:dragon}} *)
#open "graphics";;
open_graph "";;

let rec dragon n x y z t =
 if n = 1 then begin
  moveto x y;
  lineto z t
 end else begin
  let u = (x + z + t - y) / 2
  and v = (y + t - z + x) / 2 in
  dragon (n - 1) x y u v;
  dragon (n - 1) z t u v
 end;;

dragon 15 120 120 50 50;;

(* {\em La courbe du dragon, voir page \pageref{prog:dragon-2}} *)
let rec dragon n x y z t =
 if n = 1 then begin
  moveto x y;
  lineto z t
 end else begin
  let u = (x + z + t - y) / 2
  and v = (y + t - z + x) / 2 in
  dragon (n - 1) x y u v;
  dragon_bis (n - 1) u v z t
 end

and dragon_bis n x y z t =
 if n = 1 then begin
  moveto x y;
  lineto z t
 end else begin
  let u = (x + z - t + y) / 2
  and v = (y + t + z - x) / 2 in
  dragon (n - 1) x y u v;
  dragon_bis (n - 1) u v z t
 end;;

clear_graph();;
dragon 15 120 120 50 50;;

(* {\em Quicksort, voir page \pageref{prog:qsort}} *)
let a = [| 1; 7; 3; 8; 0 |];;

let rec qsort g d =
 if g < d then begin
  let v = a.(g)
  and m = ref g in
  for i = g + 1 to d do
   if a.(i) < v then begin
    m := !m + 1;
    let x = a.(!m) in
    a.(!m) <- a.(i); a.(i) <- x
   end
  done;
  let x = a.(!m) in
  a.(!m) <- a.(g); a.(g) <- x;
  qsort g (!m - 1);
  qsort (!m + 1) d
 end;;

(* {\em Quicksort, voir page \pageref{prog:quicksort}} *)
let rec quicksort g d =
 if g < d then begin
  let v = a.(d)
  and t = ref 0
  and i = ref (g - 1)
  and j = ref d in
  while j > i do
   incr i;
   while a.(!i) < v do incr i done;
   decr j;
   while a.(!j) > v do decr j done;
   t := a.(!i);
   a.(!i) <- a.(!j);
   a.(!j) <- !t
  done;
  a.(!j) <- a.(!i);
  a.(!i) <- a.(d);
  a.(d) <- !t;
  quicksort g (!i - 1);
  quicksort (!i + 1) d
 end;;

(* {\em Tri fusion, voir page \pageref{prog:tri-fusion}} *)
let b = make_vect n 0;;

let rec tri_fusion g d =
 if g < d then begin
  let m = (g + d) / 2 in
  tri_fusion g m;
  tri_fusion (m + 1) d;
  for i = m downto g do
   b.(i) <- a.(i) done;
  for i = m + 1 to d do
   b.(d + m + 1 - i) <- a.(i) done;
  let i = ref g and j = ref d in
  for k = g to d do
   if b.(!i) < b.(!j) then begin
    a.(k) <- b.(!i); i := !i + 1
   end else begin
    a.(k) <- b.(!j); j := !j - 1
   end
  done
 end;;