Next: Chapitre 2 Up: Programmes en Caml Previous: Programmes en Caml

## Chapitre 1

0em

#open "printf";;

let nmax = 10;;

let a = make_vect nmax 0;;

let initialisation () =
for i = 0 to nmax - 1 do
a.(i) <- random__int 100
done;;

let impression () =
for i = 0 to nmax - 1 do
printf "%3d " a.(i)
done;
printf "\n";;

let tri_sélection* () =
let min = ref 0 in
for i = 0 to nmax - 2 do
min := i;
for j = i + 1 to nmax - 1 do
if a.(j) < a.(!min) then min := j
done;
let t = a.(!min) in
a.(!min) <- a.(i); a.(i) <- t
done;;

let main () =
(* On lit le tableau *)
initialisation ();
(* On trie *)
tri_sélection* ();
(* On imprime le résultat *)
impression ();
exit 0;;

(* Style plus Caml *)
let initialisation a =
for i = 0 to vect_length a - 1 do
a.(i) <- random__int 100
done;;

let impression a =
for i = 0 to vect_length a - 1 do
print_int a.(i); print_string " ";
done;
print_newline();;

let tri_sélection* a =
let min = ref 0 in
for i = 0 to vect_length a - 2 do
min := i;
for j = i + 1 to vect_length a - 1 do
if a.(j) < a.(!min) then min := j
done;
let t = a.(!min) in
a.(!min) <- a.(i); a.(i) <- t
done;;

let a = make_vect 10 0 in
initialisation a;
tri_selection* a;
impression a;;

(* {\em Tri par insertion, voir page \pageref{prog:tri-insertion}} *)
let tri_insertion a =
let j = ref 0 in
let v = ref 0 in
for i = 1 to vect_length a - 1 do
v := a.(i); j := i;
while !j > 0 && a.(!j - 1) > !v do
a.(!j) <- a.(!j - 1);
j := !j - 1
done;
a.(!j) <- !v;
done;;

(* {\em Tri shell, voir page \pageref{prog:tri-shell}} *)
let tri_shell a =
let h = ref 1 in
while !h <= vect_length a - 1 do
h := 3 * !h + 1
done;
while !h > 1 do
h := !h / 3;
for i = !h to vect_length a - 1 do
if a.(i) < a.(i - !h) then begin
let v = a.(i) in
let j = ref i in
while !j >= !h && a.(!j - !h) > v do
a.(!j) <- a.(!j - !h);
j := !j - !h
done;
a.(!j) <- v
end
done
done;;

(* Avec une exception pour sortir de
la boucle dès qu'on a trouvé *)
let bottin =
[| "paul",   2811;
"roger",  4501;
"laure",  2701;
"anne",   2702;
"pierre", 2805;
"yves",   2806 |];;

exception Found of int;;

let recherche s bottin =
try
for i = 0 to vect_length bottin - 1 do
let nom, tel = bottin.(i) in
if nom = s then raise (Found tel)
done;
raise Not_found
with Found tel -> tel;;

(* Recherche 3 *)
let bottin =
[| "paul",   2811;
"roger",  4501;
"laure",  2701;
"anne",   2702;
"pierre", 2805;
"yves",   2806;
"",       0    |];;

let recherche s bottin =
nom.(vect_length nom - 1) <- (s, 0);
let i = ref 0 in
while fst (bottin.(!i)) <> s do
incr i
done;
if !i = vect_length bottin
then raise Not_found
else
let _, tel = bottin.(!i) in tel;;

(* Lecture des données *)
while true do
printf "%d\n"
(recherche (input_line stdin) bottin)
done;;

(* {\em Recherche dichotomique, voir page \pageref{prog:recherche-dichotomique}} *)
let nom =
[| "anne"; "laure"; "paul";
"pierre"; "roger"; "yves" |];;
let tel =
[| 2702;   2701;    2811;
2805;     4501;    2806 |];;

let recherche_dichotomique x =
let g = ref 0
and d = ref (vect_length nom - 1)
and i = ref 0 in
while x <> nom.(!i) && !g <= !d do
i := (!g + !d) / 2;
if x < nom.(!i) then d := !i - 1
else g := !i + 1;
done;
if x = nom.(!i) then tel.(!i) else (-1);;

(* {\em Insertion 1, voir page \pageref{prog:insertion1}} *)
let n = ref 0;;

let insertion x val =
if !n >= vect_length nom
then failwith "Débordement de la table";
nom.(n) <- x;
tel.(n) <- val;
incr n;;

(* Fonction de hachage *)
let n = vect_length nom - 1
and b = 128;;

let h s =
let result = ref 0 in
for i = 0 to string_length s - 1 do
result :=
(!result * b + (int_of_char (s.[i]))) mod n
done;
!result;;

(* Recherche avec hachage *)
let col = make_vect (vect_length nom)  (-1);;

let recherche x =
let i = ref (h x) in
while nom.(!i) <> x &&
col.(!i) <> -1
do i := col.(!i) done;
if x = nom.(!i) then tel.(!i) else -1;;

(* {\em Insertion avec hachage, voir page \pageref{prog:insertion1}} *)
let nom = make_vect nmax "";;
let tel = make_vect nmax 0;;
let col = make_vect nmax (-1);;

let nNoms = ref n;;

let insertion x val =
let i = h x in
if nom.(i) = "" then begin
nom.(i) <- x;
tel.(i) <- val
end else begin
if !nNoms >= nmax
then failwith "Débordement de la table"
else begin
nom.(!nNoms) <- x;
(* On met la nouvelle entrée en tête *)
(* de la liste des collisions *)
(* de sa classe d'équivalence *)
tel.(!nNoms) <- val;
col.(!nNoms) <- col.(i);
col.(i) <- !nNoms
end;
end;
incr nNoms;;

{\em voir page \pageref{prog:recherche-hachage-ouvert}} *)
let recherche x =
let i = ref (h x) in
while nom.(!i) <> x && nom.(!i) <> "" do
i := (!i + 1) mod nmax
done;
if nom.(!i) = x then tel.(!i) else -1;;

let insertion x val =
if !nNoms > nmax
then failwith "Débordement de la table";
incr nNoms;
let i = ref (h x) in
while nom.(!i) <> x && nom.(!i) <> "" do
i := (!i + 1) mod nmax
done;
nom.(!i) <- x;
tel.(!i) <- val;;


1/11/1998