Option info - TD 8 Piles, Files

(* Des fonctions pour transformer des files ou piles en liste, et inversément *)

let queue_into_list q =
let l = ref [] in
let condition = ref true in
while !condition do
    if (Queue.is_empty q) then condition:=false
    else l:= (Queue.take q)::(!l)
    done;
List.rev(!l);;

let list_into_queue l =
let rec aux l q = match l with
|[] -> q
|h::t -> begin (Queue.add h q);
            aux t q;
            end
in aux l ( Queue.create () );;

let stack_into_list s =
let l = ref [] in
let condition = ref true in
while !condition do
if Stack.is_empty s then condition:=false
else l:=(Stack.pop s)::!l
done;
(List.rev !l);;

let list_into_stack l =
let s = Stack.create () in
let rec aux l = match l with
|[] -> s
|h::t -> (Stack.push h s);
            aux t;
in
aux (List.rev l);;

(* Exercice 2 *)

type couleur = Bleue | Rouge and assiette = couleur * int ;;

let range_assiette pile =

let pile_rouge = Stack.create () in
let pile_bleue = Stack.create () in

while not (Stack.is_empty pile) do
let assiette = Stack.pop pile in
match assiette with
|(Bleue,a) -> Stack.push (Bleue,a) pile_bleue
|(Rouge,a) -> Stack.push (Rouge,a) pile_rouge
done;

while not (Stack.is_empty pile_bleue) do
let assiette = Stack.pop pile_bleue in
Stack.push assiette pile;
done;
while not (Stack.is_empty pile_rouge) do
let assiette = Stack.pop pile_rouge in
Stack.push assiette pile;
done;;

let s = list_into_stack [(Bleue,5);(Rouge,6);(Bleue,7);(Rouge,9)];;
range_assiette s;;
stack_into_list s;;

(* Exercice 4 *)

(* 1. Une complexité qui devient de plus en plus grande pour des grands nombres : une division euclidienne pour vérifier le reste semble prendre trop de temps pour des grandes valeurs de n
Réponse au "Comment ?" : théorème de décomposition unique en nombres premiers, puisque 2 3 et 5 sont premiers *)

let max n1 n2 n3 =
if (n1 >= n2) then  if n1>=n3 then n1
                            else n3
else if n2>=n3 then n2
else n3;;


let nombre_hamming n =

let f2 = Queue.create () in
let f3 = Queue.create () in
let f5 = Queue.create () in
Queue.push 1 f2;
Queue.push 1 f3;
Queue.push 1 f5;
let compteur = ref 0 in
let k2 = ref 0 in
let k3 = ref 0 in
let k5 = ref 0 in
let kmax = ref 0 in

while !compteur<n do
(* Queue.top renvoie le premier élément sans l'enlever *)
(* push synonyme de add *)
    k2 := Queue.top f2;
    k3 := Queue.top f3;
    k5 := Queue.top f5;
    kmax := max !k2 !k3 !k5;

    if !kmax= !k2 then k2:= Queue.pop f2;
    if !kmax= !k3 then k3:= Queue.pop f3;
    if !kmax= !k5 then k5:= Queue.pop f5;

    Queue.push (5* !kmax) f5;
    Queue.push (3* !kmax) f3;
    Queue.push (2* !kmax) f2;

    incr compteur
done;
(queue_into_list f2,queue_into_list f3,queue_into_list f5);;