Prog Caml : Ecrire la fonction tableau_contient

Écrire une fonction tableau_contient qui prend en paramètre un tableau d'entiers tab d'une part, une valeur entière clef d'autre part, et qui renvoie un booléen pour savoir si au moins une des cases du tableau tab contient la valeur clef. Pouvez-vous donner le type de cette fonction ?

Attention : ne cherchez pas à interrompre la boucle for si vous rencontrez la valeur clef. Il n'est pas possible de quitter une boucle for avant d'arriver à la valeur finale du compteur. On verra plus tard une autre structure de boucle qui permet d'avoir un contrôle plus précis. Pour l'instant, on doit se contenter d'une boucle du type for i = 0 to pred taille do ... .

Limites de temps et de mémoire (Python)

  • Temps : 4 s sur une machine à 1 GHz.
  • Mémoire : 1 000 ko.

Exemples

Exemple 1

entrée :

3
1 2 3
2

sortie :

true

Exemple 2

entrée :

3
1 2 3
4

sortie :

false

Commentaires

Code à compléter Caml

let read_int() = Scanf.scanf " %d" (fun x -> x);;

let read_int_array () =
  let taille = read_int() in
  let tab = Array.make taille 0 in
  for i = 0 to pred taille do
     let valeur = read_int() in
     tab.(i) <- valeur;
  done;
  tab 
;;


let tableau_contient tab clef =
(*à compléter*)
;;

let t = read_int_array () in
let c = read_int() in
print_string( string_of_bool ( tableau_contient t c ))


Source : http://www.france-ioi.org/ Créé par : Arthur Charguéraud.