Algorithmes de base

Factorielle

Complexité : \( C_n = \mathcal{O}(n) \)

let rec factorielle n = if n = 0 then 1 else n * (factorielle (n - 1))

HR : "Si \( n \) désigne l'entrée, factorielle n termine et renvoie \( n! \)"

int factorielle(int n) {
  int res = 1;
  for (int i = 1; i <= n; i += 1) {
    res *= i;
  }
  return res;
}

Variant : \( n + 1 - i \)

Invariant : \( res = i! \)

Expo rapide

Complexité : \( C_n = \mathcal{O}(log(n)) \)

let rec expo_rapide x n = if n = 0 then 1
  else if n mod 2 = 0 then expo_rapide (x*x) (n/2)
  else x * (expo_rapide (x*x) ((n - 1) / 2))

HR : Par récurence sur \( n \) : "expo_rapide x n termine et renvoie \( x^n \)"

int expo_rapide(int x, int n) {
  int resultat = 1;
  while (n > 0) {
    if (n % 2 == 0) {
      n = n/2;
    } else {
      resultat *= x;
      n = (n - 1)/2;
    }
    x = x*x;
  }
  return resultat;
}

Variant : \( n \)

Invariant : En notant \( N \) la valeur initiale de \( n \) et \( X \) la valeur initiale de \( x \), on prend \( X^N = resultat \cdot (x^n) \)

Euclide

Complexité : Pas au programme, nous n'avons pas les outils pour la calculer

let rec euclide a b = if b = 0 then a else euclide b (a mod b)

HR : Récurrence sur \( b \). "euclide a b termine et renvoie \( pgcd(a,b) \)"

int euclide(int a, int b) {
  while (b > 0) {
    int tmp = a;
    a = b;
    b = tmp % b;
  }
  return a;
}

Variant : \( b \)

Invariant : En notant \( A \) et \( B \) les valeurs originales de \( a \) et \( b \) on prend \( pgcd(a,b) = pgcd(A,B) \)

PS : Pour la récurrence/l'invariant voir le cours de maths pour la relation entre pgcd de deux nombres et division euclidienne.

Recherche dichotomique

Complexité : \( C_n = \mathcal{O}(log(n)) \)

let rec recherche_dicho_interne tab value imin imax = if imin > imax then false
  else let imoy = (imin + imax) / 2 in let vmoy = t.(imoy) in
  if vmoy = value then true
  else if vmoy < value then recherche_dicho_interne tab value (imoy + 1) imax
  else recherche_dicho_interne tab value imin (imoy - 1)

let recherche_dicho tab value = recherche_dicho_interne tab value 0 (Array.length tab - 1)

HR (pour recherche_dicho_interne) : Sur \( imax - imin \), "recherche_dicho_interne et renvoie vrai si et seulement si la valeur \( val \) est dans le tableau entre les indices \( imin \) et \( imax \)"

bool recherche_dichotomique(int tab[], int taille_tab, int val) {
  int imin = 0;
  int imax = taille_tab - 1;
  while (imin <= imax) {
    int imoy = (imin + imax) / 2;
    int vmoy = tab[imoy];
    if (vmoy == val) {
      return true;
    } else if (vmoy < val) {
      imin = imoy + 1;
    } else {
      imax = imoy - 1;
    }
  }
  return false;
}

Variant : \( imax - imin \)

Invariant : "Si tab contient val c'est entre les indices imin et imax"

Nombre de chiffre d'un entier naturel

Complexité : \( C_n = \mathcal{O}(k) \) où \( k \) désigne le nombre de chiffres de \( n \)

let rec nb_chiffres n = if n < 10 then 1 else
  1 + (nb_chiffres (n / 10))

HR : "nb_chiffres(n) termine et renvoie le nombre de chiffre de n"

int nb_chiffres(int n) {
  int nb = 1;
  while (n > 9) {
    nb += 1;
    n = n / 10;
  }
  return nb;
}