Next: Chapitre 3 Up: Programmes en Caml Previous: Chapitre 1

## 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;;


1/11/1998