Fonctions de base sur les tableaux

Max / Min

Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l

let rec max l = match l with
  | [] -> failwith "Pas de maximum"
  | [p] -> p
  | p::q -> let max_reste = max q in if p > max_reste then p else max_reste

let rec min l = match l with
  | [] -> failwith "Pas de minimum"
  | [p] -> p
  | p::q -> let min_reste = min q in if p < min_reste then p else min_reste

HR : Récurrence sur \( n \), la taille de l : "Pour toute liste l de taille \( n \) : max l (resp. min l) termine et renvoie le maximum (resp. le minimum) de l"

// On suppose le tableau non-vide
int max(int tab[], int taille_tab) {
  int max_actuel = tab[0];
  for (int i = 0; i < taille_tab; i += 1) {
    if (tab[i] > max_actuel) {
      max_actuel = tab[i];
    }
  }
  return max_actuel;
}

int min(int tab[], int taille_tab) {
  int min_actuel = tab[0];
  for (int i = 0; i < taille_tab; i += 1) {
    if (tab[i] < min_actuel) {
      min_actuel = tab[i];
    }
  }
  return min_actuel;
}

Variant : \( taille\_tab - i \)

Invariant : \( max\_actuel \) (resp. \( min\_actuel \) ) contient le maximum (resp. le minimum) des valeurs de tab d'indice inférieur à \( i \)

Indice max/Indice min

Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l

let rec max_avec_indice l = match l with
  | [] -> failwith "Pas de maximum"
  | [p] -> (p, 0) (* valeur, indice *)
  | p::q -> let (max_reste, indice_max_reste) = max_avec_indice q in
     if p > max_reste then (p, 0) else (max_reste, 1 + indice_max_reste)

let rec indice_max l = snd (max_avec_indice l)

let rec min_avec_indice l = match l with
  | [] -> failwith "Pas de minimum"
  | [p] -> (p, 0) (* valeur, indice *)
  | p::q -> let (min_reste, indice_min_reste) = min_avec_indice q in
     if p < min_reste then (p, 0) else (min_reste, 1 + indice_min_reste)

let rec indice_min l = snd (min_avec_indice l)

HR (pour max_avec_indice et min_avec_indice) : Sur la taille \( n \) de l : "max_avec_indice (resp. min_avec_indice) termine et renvoie un tuple contenant la valeur du max (resp. min) et son indice"

// On suppose le tableau non-vide
int indice_max(int tab[], int taille_tab) {
  int indice_max_actuel = 0;
  for (int i = 0; i < taille_tab; i += 1) {
    if (tab[i] > tab[indice_max_actuel]) {
      indice_max_actuel = i;
    }
  }
  return indice_max_actuel;
}

int indice_min(int tab[], int taille_tab) {
  int indice_min_actuel = 0;
  for (int i = 0; i < taille_tab; i += 1) {
    if (tab[i] < tab[indice_min_actuel]) {
      indice_min_actuel = i;
    }
  }
  return indice_min_actuel;
}

Variant : \( taille\_tab - i \)

Invariant : \( indice\_max\_actuel \) (resp. \( indice\_min\_actuel \) contient l'indice du maximum (resp. du minimum) des valeurs de tab d'indice inférieur à \( i \)

Nombre d'occurences

Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l

let rec nombre_occurences l v = match l with
  | [] -> 0
  | p::q -> if p = v then 1 + (nombre_occurences q v) else (nombre_occurences q v)

HR : Sur la taille \( n \) de l : "Pour toute liste l de taille \( n \), nombre_occurences l v termine et renvoie le nombre d'occurences de v dans l"

int nombre_occurences(int tab[], int taille_tab, int val) {
  int nb_occ = 0;
  for (int i = 0; i < taille_tab; i += 1) {
    if (tab[i] == val) {
      nb_occ += 1;
    }
  }
  return nb_occ;
}

Variant : \( taille\_tab - i \)

Invariant : \( nb\_occ \) contient le nombre d'occurences de val dans tab d'indice inférieur à \( i \)

Indice première/dernière occurence

Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l

(* Pas obligatoire mais TRES PRATIQUE DANS BEAUCOUP DE CAS *)
let fmap_option f o = match o with
  | None -> None
  | Some v -> Some (f v)

let rec indice_premiere_occurence l v = match l with
  | [] -> None
  | p::q -> if p = v then Some 0 else fmap_option (fun i -> i + 1) (indice_premiere_occurence q v)

let rec indice_derniere_occurence l v = match l with
  | [] -> None
  | p::q -> match indice_derniere_occurence q v with
    | None -> if p = v then Some 0 else None
    | Some i -> Some (i + 1)

HR : Sur \( n \) la taille de l : "Pour toute liste l de taille \( n \), indice_premiere_occurence l v (resp. indice_derniere_occurence l v) renvoie None si la valeur n'est pas dans la liste et Some i avec \( i \) l'indice de la première (resp. dernière) occurence de v dans l sinon"

int indice_premiere_occurence(int tab[], int taille_tab, int val) {
  for (int i = 0; i < taille_tab; i += 1) {
    if (tab[i] == val) {
      return i;
    }
  }
  return -1;
}

int indice_derniere_occurence(int tab[], int taille_tab, int val) {
  for (int i = taille_tab - 1; i >= 0; i -= 1) {
    if (tab[i] == val) {
      return i;
    }
  }
  return -1;
}

Variant : \( taille\_tab - i \) et \( i + 1 \) respectivement.

Invariant : tab ne contient pas la valeur val pour des indices inférieurs (resp. supérieurs) à \( i \)

Est-trié dans l'ordre croissant

Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l

let rec est_croissant l = match l with
  | [] | [_] -> true
  | p1::p2::q -> (p1 <= p2) && (est_croissant (p2::q))

HR : Sur la taille \( n \) de l : "Pour toute liste l de taille \( n \), est_croissant l renvoie vrai si et seulement si l est trié dans l'ordre croissant"

bool est_croissant(int tab[], int taille_tab) {
  for (int i = 0; i < taille_tab - 1; i += 1) {
    if (tab[i+1] < tab[i]) {
      return false;
    }
  }
  return true;
}

Variant : \( taille\_tab - i \)

Invariant : Les valeurs de tab d'indices inférieurs à \( i \) sont triées dans l'ordre croissant.

Somme des valeurs

Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l

let rec somme l = match l with
  | [] -> 0
  | p::q -> p + (somme q)

HR : Sur \( n \) la taille de l : "Pour toute liste l de taille \( n \), somme l termine et renvoie la somme des éléments de l"

int somme(int tab[], int taille_tab) {
  int s = 0;
  for (int i = 0; i < taille_tab; i += 1) {
    s += tab[i];
  }
  return s;
}

Variant : \( taille\_tab - i \)

Invariant : \( s = \sum_{k = 0}^{i} tab_i \) où \( tab_i \) désigne l'élément d'indice \( i \) dans tab