(* fonction de test *)
let test label b =
print_string label;
if b then print_string ": ok !\n" else print_string ": failed !\n";
flush stdout
;;
(* Premiere partie *)
let mAX_VAL = 9;;
let compte_occ t =
let occ = Array.make (mAX_VAL+1) 0 in
for i = 1 to t.(0) do
occ.(t.(i)) <- occ.(t.(i)) + 1
done;
occ
;;
let tri_simple t =
let occ = compte_occ t
and j = ref 1 in
for i = 0 to mAX_VAL do
for k = 1 to occ.(i) do
t.(!j) <- i;
incr j
done;
done;
t
;;
test "tri simple" ((tri_simple [|7;3;1;3;9;5;6;2|]) = [|7;1; 2; 3; 3; 5; 6; 9|]);;
(************************************************)
(* question 3 *)
let vider t =
t.(0) <- 0
;;
(* question 4 *)
let ajouter t p =
t.(0) <- t.(0) + 1;
t.(t.(0)) <- p
;;
(* question 5 *)
let concatener t1 t2 =
for i = 1 to t2.(0) do
ajouter t1 t2.(i)
done
;;
(* question 6
La complexitÈ de concatener est |t2|
*)
(* question 7 *)
let max_valeur t =
let m = ref 0 in
for i = 1 to t.(0) do
m := max t.(i) !m
done;
!m
;;
test "max_valeur" ((max_valeur [|4;3;1;3;8;0;0;0|]) = 8);;
(* question 8 *)
let rec nombre_chiffres i =
let i' = i / 10 in
if i' = 0 then 1 else 1 + (nombre_chiffres i')
;;
test "nombre_chiffres" ((nombre_chiffres 5973) = 4);;
(* question 9 *)
let max_chiffres t =
nombre_chiffres (max_valeur t)
;;
test "max_chiffres" ((max_chiffres [|4;33;13445;32;8|]) = 5);;
(* question 10
complexitÈ = n * maxc
*)
(* question 11 *)
let rec chiffre_de_rang_r n r =
if r = 1 then
n mod 10
else
chiffre_de_rang_r (n/10) (r-1)
;;
test "chiffre_de_rang_r" ((chiffre_de_rang_r 12345 4) = 2);;
test "chiffre_de_rang_r" ((chiffre_de_rang_r 12345 8) = 0);;
(* (distribuer : int array -> int -> int array array -> unit)*)
let distribuer t r baquets =
for i = 1 to t.(0) do
ajouter baquets.(chiffre_de_rang_r t.(i) r) t.(i)
done
;;
let print_vect t =
for i = 1 to t.(0) do
print_int t.(i);
print_string " ";
done;
print_string "\n";
flush stdout;
;;
let tri_baquets t =
let maxc = max_chiffres t
and baquets = Array.make_matrix 10 t.(0) 0
in
for r = 1 to maxc do
for i = 0 to 9 do vider (baquets.(i)) done;
distribuer t r baquets;
vider t;
for i = 0 to 9 do concatener t baquets.(i) done;
done;
t
;;
test "tri baquets" ((tri_baquets [|7;3;1;3;9;5;6;2|]) = [|7;1;2;3;3;5;6;9|]);;
(* question 17 *)
(*
Il faut se debrouiller pour ne pas reparcourir les elements de t deja
traitÈ, i.e., quand on est au rang n, il faut avoir enlevÈ de t tous
les nombres de moins de (n-1) chiffres.
*)
let distribuer2 t tt r baquets =
for i = 1 to t.(0) do
let p = t.(i) in
let k = chiffre_de_rang_r p r in
if k = 0 && nombre_chiffres p = r - 1 then
ajouter tt p
else
ajouter baquets.(k) p
done
;;
let tri_baquets2 t =
let r = ref 1 in
let baquets = Array.make_matrix 10 t.(0) 0 in
let tt = Array.make (t.(0) + 1) 0 in
while t.(0) <> 0 do
for i = 0 to 9 do vider baquets.(i) done;
distribuer2 t tt !r baquets;
vider t;
for i = 0 to 9 do concatener t baquets.(i) done;
incr r
done;
vider t;
concatener t tt;
t
;;
test "tri baquets2" ((tri_baquets2 [|7;3;1;3;9;5;6;222|]) = [|7;1;3;3;5;6;9;222|]);;