(*  Exercice 1*)


(* Question 1 *)

let rec puis_naive element n fois id =
	if n = 0 then id 
		else fois ( puis_naive element (n-1) fois id ) element ;;
	
	
	
	
	
puis_naive 5 7 (fun a b -> a*b ) 1;;


let rec puis element n fois id =
	if n = 0 then id 
	else
	if n = 1 then element
	else
	if (n mod 2) = 0 then 
			let e_prim = puis element (n/2) fois id in fois e_prim e_prim
	else
			let e_prim = puis element (n/2) fois id in 
					fois element (fois e_prim e_prim );;

puis 3 38 (fun a b -> a*b ) 1;;


(* Exercice 2 *)


let recherche () =
	let nb_a_trouve = Random.int 101 in
	let rec aux compteur a b =
		if a = b then (compteur , a )
		else
			begin
				let milieu = (a+b)/2 in
					if milieu > nb_a_trouve
						then aux (compteur+1) a (milieu-1)
					else 
						if milieu = nb_a_trouve then (compteur , milieu )
					else aux (compteur+1) (milieu +1 ) b
			
			end
			in
		aux 0 0 100;;

recherche ();;


(*  Exercice 4  *)
let rec fusion liste_1 liste_2 =  
		match (liste_1 , liste_2 ) with
		| ( [] , [] ) -> []
		| ( [] , _ ) -> liste_2
		| ( _  , [] ) -> liste_1
		| (a::reste_1 , b::reste_2 ) -> 
				if a<b then a::( fusion reste_1 liste_2 )
				else b::( fusion liste_1 reste_2 );;


fusion [ 1;4;9;12 ] [ 5;6;7;15];;


let rec fendre liste = match liste with
	| [] -> [],[]
	| [a] -> [a] , []
	| a::b::reste -> let l_a,l_b = fendre reste in ( a::l_a , b::l_b);;


fendre [8;4;96;1;4;8;7;47;9;4;15;1];;

let rec tri_fusion l =
	match l with
		| [] -> []
		| [a] -> [a]
		| _ -> let (l1,l2) = fendre l in fusion (tri_fusion(l1))  (tri_fusion(l2));;

tri_fusion [5;4;1;9;7;6;1;5;7;9;2];;