DS 3 (MP2I 2021-2022) — Programmation impérative en OCaml

Devoir surveillé · MP2I · 2021-2022 · OCaml · partie pratique sur machine du DS 3

Cours : Programmation impérative

Autres parties : Partie écrite : exponentiation rapide et tri du crêpier · Pratique, récursif

Partie pratique sur machine (exercices Learn OCaml « DS3 - Récursif » et « DS3 - Impératif »).

Attention dans toute cette partie, vous n'avez pas le droit d'utiliser de fonctions du module Array autres que length, make, make_matrix, init.

Les fonctions avec en indication vous garantissent, si vous les faites toutes, une note de 15.

Question 1

Écrire une fonction somme qui prend en entrée un tableau d'entiers et renvoie la somme de ses éléments.

Corrigé

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

Question 2

Écrire une fonction compte qui prend en entrée un tableau d'éléments de type 'a et une valeur x de type 'a et renvoie le nombre de fois que cette valeur est présente dans le tableau.

Corrigé

let compte a x =
  let c = ref 0 in
  for i = 0 to Array.length a - 1 do
    if a.(i) = x
    then incr c
  done;
  !c

Question 3

Écrire une fonction indice_minimum qui prend en entrée un tableau d'éléments de type 'a et renvoie le plus petit indice du minimum du tableau.

Cette fonction ne sera jamais appelée sur un tableau vide.

Corrigé

let indice_minimum a =
  let i = ref 0 in
  for j = 0 to Array.length a - 1 do
    if a.(j) < a.(!i)
    then i := j
  done;
  !i

Question 4

Écrire une fonction array_concat qui prend en entrée deux tableaux t1, t2 et renvoie le tableau correspondant à mettre les éléments de t1 suivis des éléments de t2.

Corrigé

Attention aux cas de base et à la valeur par défaut de Array.make.

let array_concat a1 a2 =
  if a1 = [||] then a2 else
  let n1 = Array.length a1 in
  let n2 = Array.length a2 in
  let a = Array.make (n1+n2) a1.(0) in
  for i = 0 to n1-1 do
    a.(i) <- a1.(i)
  done;
  for i = 0 to n2-1 do
    a.(n1+i) <- a2.(i)
  done;
  a

Question 5

Écrire une fonction compte_inversions qui prend en entrée un tableau t et compte le nombre de paires d'indices i, j tels que i < j et t.(i) > t.(j).

Corrigé

let compte_inversions a =
  let c = ref 0 in
  let n = Array.length a in
  for i = 0 to n-1 do
    for j = i+1 to n-1 do
      if a.(i) > a.(j)
      then incr c
    done
  done;
  !c

Question 6

Écrire une fonction cherche_motif qui étant donnés deux tableaux t et m renvoie un booléen indiquant si m est un sous-tableau de t.

C'est la même notion que l'inclusion de motif dans une chaîne vue en TP.

Corrigé

let cherche_motif a am =
  let n = Array.length a in
  let m = Array.length am in
  let v = ref false in
  for i = 0 to n-m do
    let trouve = ref true in
    for k = 0 to m-1 do
      trouve := !trouve && a.(i+k) = am.(k)
    done;
    v := !trouve || !v
  done;
  !v

Question 7

(Chronophage) Écrire une fonction dessine_sapin qui étant donné un entier p > 0 dessine un sapin ainsi :

    p        p      le motif fait 2*p+1
<------> <------>
        *
       * *
      *   *
     *     *<- dernier caractère
    *       *   on ne met pas les espaces
   *         *
  *           *
 *             *
*****************
       |||         <- comme p>0 on a 2*p+1>=3 et
       |||               il y a toujours un tronc

Pour 5 on aura donc le sapin

     *
    * *
   *   *
  *     *
 *       *
***********
    |||
    |||

On utilisera les fonctions print_char : char -> unit et print_newline (). On fera un saut de ligne après la dernière ligne.

Corrigé

let dessine_sapin p =
  for i = 0 to p-1 do
    for j = 1 to p-i do
      print_char ' '
    done;
    print_char '*';
    for j = 1 to 2*i-1 do
      print_char ' '
    done;
    if i > 0 then print_char '*';
    print_newline ()
  done;
  for i = 0 to 2*p do
    print_char '*'
  done;
  print_newline ();
  for i = 1 to 2 do
    for j = 0 to p-2 do
      print_char ' '
    done;
    for _ = 1 to 3 do print_char '|' done;
    print_newline ()
  done

Question 8

Écrire une fonction tri qui trie un tableau en place par la méthode de votre choix. Cette fonction ne renvoie rien vu qu'elle modifie le tableau passé en argument.

Corrigé

Tri par sélection :

let tri a =
  let echange a i j =
    let temp = a.(i) in
    a.(i) <- a.(j);
    a.(j) <- temp
  in
  for i = 0 to Array.length a - 2 do
    let j = ref i in
    for k = i+1 to Array.length a - 1 do
      if a.(k) < a.(!j)
      then j := k
    done;
    echange a i !j
  done

Question 9

(Difficile) Écrire une fonction carre : bool array array -> int -> int -> int telle que carre m x y renvoie la dimension du plus grand carré de true dans la matrice carrée de booléens m où le coin supérieur gauche du carré a pour coordonnées (x, y).

Si on voit cette matrice comme une image en noir et blanc, il s'agit de trouver la taille du carré noir commençant au pixel (x, y).

Cette fonction est toujours appelée avec des coordonnées pour lesquelles la valeur est true.

Corrigé

On agrandit le carré d'une couronne (colonne \(y+r\) et ligne \(x+r\)) tant que celle-ci ne contient que des true et ne sort pas de la matrice.

let carre m x y =
  if m.(x).(y)
  then begin
    let r = ref 1 in
    let valid = ref true in
    let n = Array.length m in
    while x + !r < n && y + !r < n && !valid do
      for xi = x to x + !r do
        valid := !valid && m.(xi).(y + !r)
      done;
      for yi = y to y + !r do
        valid := !valid && m.(x + !r).(yi)
      done;
      if !valid then incr r
    done;
    !r
  end else 0

Question 10

(Nécessite la précédente) Écrire une fonction plus_grand_carre qui renvoie la dimension du plus grand carré dans la matrice donnée en entrée selon la définition précédente.

Corrigé

let plus_grand_carre m =
  let n = Array.length m in
  let c = ref 0 in
  for x = 0 to n-1 do
    for y = 0 to n-1 do
      let cxy = carre m x y in
      if cxy > !c
      then c := cxy
    done
  done;
  !c