(* étude des coîncidences *)

(*Problème 1: une liste de 1000 entiers à 4 chiffres est donnée, on veut 
savoir si il y en a un qui apparaït deux fois

Problème 2: deux  listes de 1000 entiers à 4 chiffres sont données, on veut 
savoir si il y en a un qui apparaït dans les deux 

Problème 3: trouvez seul un énoncé analogue
*)
		(* Résolution du problème 1 *)

let la=Array.make 1000 false;;

open Random;;
init (int_of_float(Sys.time()));;

let liste1= Array.init 1000 (fun k -> int 1000);;

	(* on se définit une exception *)
exception Trouvé;;

	(* on remet à zéro le tableau "la" *)
let la=Array.make 10000 false;;
let enregistre l=
	for k=0 to Array.length l do
		if (la.(l.(k))=false)
		then la.(l.(k))<-true
		else (print_int k; raise Trouvé)
	done;;

		(* Résolution du problème 2 *)
(* Possibilité 1: on enregistre liste1 dans la (sans déclencher Trouvé en 
cas de coincidence) puis on se met à enregistrer liste2. C'est "long" mais 
cela réutilise ce qui a été fait ci-dessus

Possibilité 2: on remplace la par lala=Array.make 10000 [|false;false|];; 
et on enregistre alternativement les termes de liste1 à gauche et ceux de 
liste2 à droite, on déclenche Trouvé quand on a lala.(k).(1)&lala.(k).(2)
Cette seconde méthode tiendra plus de place, mais prendra moins de temps

Possibilité 3: si on est parti de listes, on fait un tri fusion en éliminant 
les doublons de chacune, puis on fait un tri fusion final en déclenchant 
éventuellement "Trouvé" 
Cette méthode prendra beaucoup moins de place, mais prendra log(N) fois plus de temps 
*)

(* énoncés analogues: 
1 deux parties de l'écran sont données, on veut savoir si l'une des deux 
"cache" une partie de l'autre: Vert ayant été affiche avant Rouge, voit-on 
tout Vert? 
2 deux textes sont donnés ont-ils un mot commun?
3 deux répertoires sont donnés, y a-t-il un fichier commun ("en double")?
*)