Sujet

Correction en OCaml

Exercice 1.

let somme a =
  let resultat = ref 0 in
  for i = 0 to Array.length a - 1 do
    resultat := !resultat + a.(i)
  done;
  !resultat

let max a =
  if Array.length a = 0
  then failwith "aie aie aie"
  else
    let resultat = ref (a.(0)) in
    let () =
      for i = 1 to Array.length a - 1 do
	if a.(i) > !resultat then resultat := a.(i)
      done in
    !resultat

(* L'énoncé est faux mais pour ne pas perdre la face, je vais écrire
une fonction crédible ayant le bon type *)
let indice_max a =
  let resultat = ref 0 in
  for i = 0 to Array.length a - 1 do
    if a.(i) < a.(!resultat) then resultat := i
  done;
  !resultat

let begaie a =
  let taille = Array.length a in
  if taille = 0 then a
  else
    let resultat = Array.make (2 * taille) a.(0) in
    for i = 0 to taille - 1 do
      resultat.(2*i) <- a.(i);
      resultat.(2*i+1) <- a.(i);
    done;
    resultat
let begaie_triche a =
  Array.init (Array.length a * 2) (fun i -> a.(i/2))
      

Exercice 2.

let est_palindrome a =
  let taille = Array.length a in
  taille < 2 ||
    let i = ref 0 in
    let () =
      while a.(!i) = a.(taille-(!i)-1) && !i <= taille/2 do
	incr i
      done in
    !i > taille/2

let chiffres_de_nombre n =
  assert (n > 0);
  let taille = int_of_float (ceil (log10 (float n))) in
  let resultat = Array.make taille n in
  for i = taille - 1 downto 1 do
    resultat.(i-1) <- resultat.(i) / 10;
    resultat.(i) <- resultat.(i) mod 10;
  done;
  resultat

let est_palindrome2 n = est_palindrome (chiffres_de_nombre n)
      

Exercice 3.

(* L'énoncé *)
let ordre_N2 _ _ = true
(* La vraie question *)
let ordre_N2 (x,y) (x',y') =
  x < x' || (x = x' && y <= y')

let ordre_lex a b =
  let i = ref 0 in
  while !i < Array.length a && !i < Array.length b && a.(!i) = b.(!i) do
    incr i
  done;
  !i = Array.length a || (!i < Array.length b && a.(!i) < b.(!i))
      

Exercice 4.

let curry f x y = f (x,y)
let uncurry f (x,y) = f x y
      

Exercice 5.

let crible_simple n =
  let crible = Array.make (n+1) true in
  let () = crible.(0) <- false in
  let () = crible.(1) <- false in
  let () =
    for i = 2 to n do
      if crible.(i) then
	let j = ref (2 * i) in
	while !j <= n do
	  let () = crible.(!j) <- false in
	  j := !j + i
	done
    done in
  let taille =
    let va = ref 0 in
    for i = 0 to n do
      if crible.(i) then incr va
    done; !va in
  let sortie = Array.make taille 0 in
  let j = ref 0 in
  for i = 0 to n do
    if crible.(i) then
      let () = sortie.(!j) <- i in
      incr j
  done;
  sortie

let crible n =
  let crible = Array.make (n/2 + 1) true in
  let () = crible.(0) <- false in
  let () =
    for i = 1 to n/2 do
      if crible.(i) then
	let j = ref (4 * i * i + 4 * i + 1) in
	while !j <= n+1 do
	  let () = crible.(!j/2) <- false in
	  j := !j + 4 * i + 2
	done
    done in
  let taille =
    Array.fold_left (fun acc va -> if va then succ acc else acc) 0 crible in
  let sortie = Array.make (taille+1) 2 in
  let j = ref 1 in
  let () =
    Array.iteri
      (fun i va ->
       if va then let () = sortie.(!j) <- 2 * i + 1 in incr j)
      crible in
  sortie

let jeu = crible 200;;
      

Exercice 6.

#load "graphics.cma";;

let affiche a =
  let haut = Array.length a in
  if haut > 0 then
    let larg = Array.length a.(0) in
    let () =
      Graphics.open_graph
	(" "^string_of_int larg^"x"^string_of_int haut) in
    let () =
      for i = 0 to haut - 1 do
	for j = 0 to larg - 1 do
	  if a.(i).(j) then Graphics.plot j (haut - i)
	done
      done in
    let _ = Graphics.read_key () in
    Graphics.close_graph ()

let point regle = function
  | false, false, false -> 0 <> regle land (1 lsl 0)
  | false, false, true -> 0 <> regle land (1 lsl 1)
  | false, true, false -> 0 <> regle land (1 lsl 2)
  | false, true, true -> 0 <> regle land (1 lsl 3)
  | true, false, false -> 0 <> regle land (1 lsl 4)
  | true, false, true -> 0 <> regle land (1 lsl 5)
  | true, true, false -> 0 <> regle land (1 lsl 6)
  | true, true, true -> 0 <> regle land (1 lsl 7)

let automate l h regle =
  let res = Array.make_matrix h l false in
  let () = if l > 0 && h > 0 then res.(0).(l/2) <- true in
  let () =
    for i = 1 to h - 1 do
      for j = 1 to l - 2 do
	res.(i).(j) <-
	  point regle (res.(i-1).(j-1),res.(i-1).(j),res.(i-1).(j+1))
      done
    done in
  res

let sierpinski h l = automate h l 90

let affiche_sierpinski h l = affiche (sierpinski h l)

let test = affiche (automate 801 600 90)
let test = affiche (automate 801 600 30)
let test = affiche (automate 801 600 110)