Fonctions utiles de la bibliothèque standard

Guillaume Ryder pour www.france-ioi.org

L'objectif de ce cours est de présenter en détail l'utilisation de la bibliothèque standard pour résoudre des points algorithmiques ou techniques faciles en soit, mais délicats à coder si l'on s'y prend mal.

1. Entrées/sorties
   Comment lire des données à partir d'un fichier ou de l'entrée standard, et écrire le résultat
2. Opérations sur les entiers
   Comment coder rapidement certaines fonctions de calcul sur les entiers
3. Opérations sur les flottants
   Maîtriser les nombres à virgule, éviter les pièges dus aux erreurs de précision
4. Algorithme de tri
   Comment utiliser qsort() pour trier toutes sortes de données
5. Recherche dichotomique
   Comment utiliser bsearch() pour effectuer une recherche par dichotomie
6. Génération de nombres aléatoires
   La fonction rand() et son utilisation aux IOI

Entrées/sorties

Toutes les fonctions d'entrée/sortie sont définies par le #include <stdio.h>.

Lecture de l'entrée

Deux cas peuvent se présenter : vous devez soit lire sur l'entrée standard soit lire dans un fichier. Commençons par le premier cas, nous verrons le second un peu plus tard. La fonction scanf() permet de lire des données sur l'entrée standard. Cette fonction prend comme premier argument une chaîne de format, qui indique combien de variables vous souhaitez lire, et de quel type. Ensuite vous donnez comment arguments des pointeurs sur les variables qui recevront le résultat, dans l'ordre de la chaîne de format.

Prenons le cas le plus simple : vous voulez lire un entier et le placer dans la variable n :

#include <stdio.h>

int n;
scanf("%d", &n);

Les arguments sont bien la chaîne de format est "%d" (nous y reviendrons plus tard), et le pointeur sur la variable lue. Pour lire deux entiers :

int a, b;
scanf("%d %d", &a, &b);

Chaîne de format

La chaîne de format se compose de codes spéciaux indiquant le type des valeurs à lire. Chaque code est précédé du symbole %. Il en existe une multitude, nous nous contenterons ici de ceux dont vous aurez besoin :

Vous avez le droit d'écrire des espaces dans la chaîne de format pour l'aérer, ils sont ignorés si vous n'utilisez que les codes spéciaux indiqués.

La chaîne lue doit être le premier mot rencontré, en s'arrêtant aux espaces et aux fins de ligne. La variable qui contiendra le résultat doit être un tableau de caractères de taille au moins n+1 où n est la longueur maximale de la chaîne à lire, car les chaînes sont terminées par un caractère zéro ('\0').

Vérification d'erreur

Si vous vous trompez dans la chaîne de format (mauvais type, argument manquant, etc.) le comportement du programme est complètement indéfini. Vous lirez des valeurs étranges, ou bien le programme plantera. Pour éviter ces erreurs, pensez à compiler en activant les warnings (-Wall avec gcc) : le compilateur vous signalera les erreurs de type dans la chaîne de format.

Écriture du résultat

Dans la quasi-totalité des cas, les résultats doivent être écris sur la sortie standard. Cela se fait en général avec la fonction printf(). De même que scanf(), cette fonction prend en argument une chaîne de format qui spécifie les types de ses autres arguments.

La chaîne de format peut aussi spécifier du texte à écrire, en plus des codes spéciaux, par exemple :

#include <stdio.h>

printf("Hello World! %d\n", 42);

Cela écrira :

Hello World! 42

suivi d'un retour à la ligne (le "\n").

Chaîne de format

La chaîne de format de printf() est plus riche en possibilités, car elle indique non seulement le type des arguments mais aussi la manière de les écrire. Par exemple, vous pouvez choisir le nombre de chiffres après la virgule d'un nombre flottant.

Chaque code spécial de la chaîne de format est précédé d'un %. Si vous voulez écrire le symbole %, vous devez l'écrire deux fois :

printf("Taux de réussite : %d %%", 42);

Affiche :

Taux de réussite : 42 %

Chaque code spécial est découpé en plusieurs sections : %[largeur][.precision]type (les sections entre crochets sont facultatives)

1. Largeur : nombre minimum de caractères à écrire, printf() complètera si nécessaire par des espaces sur la gauche : la valeur est alignée à droite
2. Précision : nombre de chiffres après la virgule à écrire pour les nombres flottants, précédé d'un point. La valeur est automatiquement arrondie : le dernier chiffre est incrémenté s'il y a besoin.
3. Type : le type de la valeur à écrire

Par exemple

printf("%6.3f", 3.1415927);

écrira la valeur de PI sur 6 caractères (virgule et signe compris), avec 3 chiffres après la virgule, ce qui donnera : " 3.142". En enlevant la spécification de largeur

printf("%.3f", 3.1415927);

donne "3.142" (sans espace à gauche).

Voici les différents types utilisables :

Note : contrairement à scanf(), printf() ne fait pas de différence entre float et double : il n'est pas nécessaire d'écrire %lf pour écrire des double.

Exemples

Note : lorsque vous écrivez des flottants, il peut être nécessaire de leur ajouter epsilon auparavant. En effet, si x est un flottant négatif proche de zéro comme -1e-20, alors printf("%.3f", x) écrira -0.000 au lieu de 0.000. printf("%.3f", x + epsilon) permet d'écrire 0.000 et donc de résoudre le problème, sans effet secondaire si epsilon est suffisamment petit.

Entrées/sorties avec des fichiers

Lire à partir d'un fichier

Dans certains concours (USACO, certains IOI), ou tout simplement pour tester vos programmes plus facilement, vous aurez besoin de lire les données d'entrée à partir d'un fichier. La solution la plus simple consiste à rediriger le fichier sur l'entrée standard, avec la fonction freopen() :

#include <stdio.h>

int main()
{
    freopen("fichier_entrée.txt", "r", stdin);

    // ...
}

Dans ce code, freopen() redirige le fichier fichier_entrée.txt sur l'entrée standard. Quand vous ferez un scanf(), le programme lira le fichier fichier_entrée.txt et non la véritable entrée standard.

Écriture dans un fichier

Là encore la fonction freopen() fait le travail en redirigeant la sortie standard sur un fichier donné :

#include <stdio.h>

int main()
{
    freopen("fichier_sortie.txt", "w", stdout);

    // ...
}

Dans la suite du programme, printf() écrira dans le fichier choisi.

Opérations sur les entiers

Cette section donne des techniques efficaces pour utiliser les fonctions mathématiques courantes sur les entiers.

Valeur absolue

Une fonction valeur absolue est définie en standard, pas besoin de la redéfinir vous-même :

#include <stdlib.h>

int x = ...;
printf("abs(x) = %d\n", abs(x));

Minimum, maximum

La bibliothèque standard n'offre aucune fonction min ou max, on est obligé de les coder soi-même :

inline int min(int a, int b)
{
    if (a < b)  
        return a;
    else        
        return b;
}

inline int max(int a, int b)
{
    if (a > b)  
        return a;
    else        
        return b;
}

Le inline sert à dire que la fonction doit être optimisée par le compilateur. Dans certains cas cela peut grandement améliorer la vitesse de calcul.

Ce que l'on peut raccourcir grâce à l'opérateur « condition ? si_vrai : si_faux » :

inline int min(int a, int b)
{
    return (a < b) ? a : b;
}

inline int max(int a, int b)
{
    return (a > b) ? a : b;
}

Ne jamais utiliser de macro (#define) pour définir les fonctions min et max. En effet si l'on définit :
#define min(a,b) (((a) < (b)) ? (a) : (b))
et que l'on utilise : min(f(x), f(y))
ce code sera traduit en : (((f(x)) < (f(y))) ? (f(x)) : (f(y)))
donc la fonction f sera appelée trop souvent : 2 fois pour calculer f(x) et f(y) (normal), et une troisième fois (en trop) pour recalculer la valeur qui correspond au maximum. Cela fait non seulement perdre du temps si la fonction f est lente à s'exécuter, mais surtout ne marchera pas si f a des effets de bords (modification de variable globale par exemple). Bref, vous devez définir une vraie fonction.

Si vous avez besoin de définir une fonction min/max pour plusieurs types différents, par exemple les entiers et les flottants, utilisez les templates du C++ :

template<class T>
inline T min(T a, T b)
{
    return (a < b) ? a : b;
}

template<class T>
inline T max(T a, T b)
{
    return (a > b) ? a : b;
}

Opérations sur les flottants

Une des différences majeures entre le traitement des entiers et des flottants est la perte de précision. Avec les entiers, les calculs sont toujours exacts, du moment que l'on ne dépasse pas la capacité des entiers. Avec les flottants, chaque opération (addition, multiplication, etc.) induit une perte de précision.

Il existe deux types de flottants en C : float et double. Les nombres flottants sont représentés sous la forme A = x * 10^y, que l'on note x e y, x ayant un seul chiffre à gauche de la virgule (par exemple 1.2345e3 = 1234.5). La précision de x est de 6 chiffres pour les float, 15 pour les double. Il donc est conseillé de toujours utiliser des double afin de garder la meilleure précision possible, le seul intérêt des float est qu'ils prennent deux fois moins de place en mémoire.

Fonctions mathématiques

La bibliothèque C standard contient une série de fonctions de calcul sur les flottants (racine carrée, logarithme, sinus, etc.), que l'on peut utiliser en incluant le fichier <math.h>.

• fabs(x) : retourne la valeur absolue de x
fabs(3.5) = 3.5, fabs(-3.5) = 3.5
  
  
• floor(x) : arrondit x à la valeur entière inférieure
  floor(3.5) = 3., floor(-3.5) = -4.
  
  
• fmod(x, y) : modulo flottant
  fmod(-10.5, 3.) = -1.5
  
  
• sqrt(x) : calcule la racine carrée de x
  
  
• pow(x, y) : élève x à la puissance y ; y peut être un nombre négatif et/ou à virgule. À ne surtout pas utiliser pour élever un nombre au carré, la multiplication est beaucoup plus rapide.
  pow(x, 1./3.) retourne la racine cubique de x
  
  
• sin(x), cos(x), tan(x) : fonctions trigonométriques usuelles (en radians, pas en degrés)
  
  
• asin(x), acos(x), atan(x) : fonctions trigonométriques inverses
  
  
• atan2(y, x) : calcule l'angle formé entre le vecteur de coordonnées (x,y) et celui de coordonnées (1,0), en radians. Il s'agit de l'angle du vecteur dans le cercle trigonométrique compris entre −PI (exclu) et +PI (inclus). Notez que le vecteur nul n'a pas de direction, donc normalement vous ne devez pas appeller atan2(0,0).
  
  atan2(1., 0.) = 1.570796 = PI/2
  
  
• exp(x) : exponentielle
  
  
• log(x), log10(x) : logarithme népérien et logarithme en base 10
  log10(100.) = 2.

Dans cette liste notez le grand intérêt de la fonction atan2() qui gère les angles obtus ainsi que les cas particuliers (vecteur horizontal, vertical).

Valeur de PI

Il n'existe aucune constante standard pour PI. Si vous en avez besoin, vous devez la définir vous-même. Ne vous contentez pas de recopier les quelques décimales de PI que vous savez, car à moins de connaître au moins les 16 premières vous perdrez bêtement de la précision. Le plus sûr est de retenir que cos(PI) = -1, donc que PI = acos(-1). N'utilisez surtout pas de #define mais définissez une constante C++ :

#include <math.h>

const double PI = acos(-1.);

Perte de précision

Si vous calculez 1e10 + 1e-10 = 1.00000000000000000001e10, l'ordinateur arrondira à 1.00000000000000e10 = 1e10 (15 chiffres pour un double). On a donc des cas où A + B = A même si B != 0.

Il faut également faire attention à l'ordre des calculs. Par exemple A + (B - C) peut être différent de (A + B) - C. Si A = 1e-10, B = 1e10, C = 1e10, on a A + (B - C) = A + 0 = 1e-10 mais (A + B) - C = B - C = 0.

En résumé on se heurte à trois types de problèmes :

• Dépassement de capacité lors des multiplications/divisions. C'est assez difficile avec les double, puisque l'on peut aller jusqu'à environ 10^300.
• Perte de précision lors des additions/soustractions. Règle d'or : placer les parenthèses et déplacer les opérandes de manière à additionner/soustraire d'abord les quantités du même ordre de grandeur.
• Perte de précision lors des opérations successives. Il faut absolument éviter d'effectuer des calculs inutiles : ne pas multiplier par 2 puis diviser par 2, ni effectuer plusieurs opérations successives par des constantes. Règle d'or : simplifiez toujours vos formules sur papier avant de les coder, comme si vous deviez vous-même les calculer à la main. En général, ce qui est difficile à calculer pour vous (racine carrée, cosinus, etc.) est également difficile pour l'ordinateur (lent, perte de précision).

Comparaison

À cause des pertes de précision, les flottants sont rarement exactement égaux à leur valeur approchée, surtout si l'on utilise des fonctions comme la racine carrée, le sinus, etc. Prenons par exemple le code suivant :

x = 2.;
x = sqrt(x);   // Racine carrée de x
x = x * x;     // x^2
if (x == 2.)
    printf("OK\n");

On s'attend à voir ce programme écrire OK. Il n'en est rien ! À cause des pertes de précision, x n'est pas égal à 2 à la fin du programme, mais à un nombre presque égal à 2 et différent de 2, comme 2.0000000000000004.

Pour déterminer si deux nombres sont égaux, il faut donc ruser. On commence par calculer la différence des deux nombres. Si la différence est très proche de zéro, c'est-à-dire si la valeur absolue de la différence est très petite, alors on considère que les nombres sont égaux.

Concrètement, pour comparer x et y, on commence par définir une constante très petite que l'on nomme traditionnellement epsilon, et on teste si |x - y| < epsilon. La fonction qui calcule la valeur absolue s'appelle fabs et est définie dans <math.h>.

#include <math.h>

const double epsilon = 1e-10;

x = 2.;
x = sqrt(x);   // Racine carrée de x
x = x * x;     // x^2
if (fabs(x - 2.) < epsilon)
    printf("OK\n");

Ce code affiche bien OK.

À retenir : pour tester si x est égal à zéro, il faut faire if (fabs(x) < epsilon).

Algorithme de tri

La bibliothèque C standard offre une fonction de tri : qsort(). Elle sert à trier un tableau d'éléments à l'aide d'une fonction de comparaison à fournir. Pour l'utiliser, vous devez inclure le fichier <stdlib.h>.

La fonction de comparaison

qsort() trie les éléments dans l'ordre que vous lui demandez. Plus précisément, vous donnez à qsort() une fonction de comparaison. Cette fonction prend deux éléments A et B, et indique si A doit être avant ou après B dans le tableau trié.

La fonction de comparaison est donc vitale, c'est elle qui indique dans quel ordre et selon quels critères il faut trier le tableau.

Arguments de qsort()

1. Pointeur sur le premier élément à trier ; en pratique, il suffit de donner le nom du tableau
2. Nombre d'éléments à trier à partir du début du tableau
3. Taille de chaque élément, en octets ; sizeof(valeurs[0]) (où valeurs est le tableau à trier) calcule cette taille pour nous
4. Fonction de comparaison

En pratique, pour trier un tableau valeurs contenant nbValeurs éléments, on donnera :

1. Le nom du tableau, valeurs
2. Le nombre d'éléments du tableau, nbValeurs
3. sizeof(valeurs[0])
4. Le nom de la fonction de comparaison

Voici un squelette d'utilisation classique :

#include <stdlib.h>

int valeurs[nbValeurs];

int compareValeurs(const void* val1, const void* val2)
{
    // Ce qu'il faut mettre ici est décrit plus tard
    // ...
}

// ...

qsort(valeurs, nbValeurs, sizeof(valeurs[0]), compareValeurs);

// ...

Notez que qsort() a besoin du nombre d'éléments de votre tableau, pas de sa taille totale. Par exemple, si le tableau a une taille de nbValeurs mais qu'en réalité vous n'utilisez que les n premiers éléments (n étant par exemple lu dans un fichier d'entrée), vous devez impérativement donner n et non nbValeurs à qsort(). Sinon la fonction triera aussi les éléments de n+1 à 99, qui sont invalides.

Pour trier le tableau valeurs à partir du deuxième élément (il reste alors n-1 éléments à trier), vous pouvez écrire : qsort(&valeurs[1], n-1, sizeof(valeurs[0]), compareValeurs);.

En pratique

La fonction de comparaison que vous donnez à qsort() est utilisée pour ordonner deux éléments, comme le ferait l'opérateur <= ou >=. Si la fonction de comparaison est <=, alors à la fin du tri du tableau a[0..n-1] les éléments sont réordonnés de telle manière que a[0] <= a[1] <= ... <= a[n-1]. Si on utilise la fonction >=, cela donnera a[0] >= a[1] >= ... >= a[n-1].

La fonction de comparaison a le prototype suivant : int compareValeurs(const void* val1, const void* val2). Autrement dit elle prend deux pointeurs val1 et val2, et renvoie un entier. val1 et val2 sont des pointeurs sur les éléments à comparer. Le const est là pour dire que les pointeurs sont constants : la fonction de comparaison n'a pas le droit de modifier le contenu du tableau pendant le tri.

Valeur de retour

Seul le signe de la valeur retournée par la fonction de comparaison compte. Si on veut que A soit avant B, compareValeurs(A, B) doit renvoyer une valeur strictement négative. Même chose dans l'autre sens : si on veut que A soit après B, compareValeurs(A, B) doit renvoyer une valeur strictement positive. Si A peut-être avant ou après B, par exemple si A = B, on peut renvoyer n'importe quelle valeur.

Par exemple on peut retourner -1 pour A avant B, +1 pour A après B, et zéro si l'ordre ne compte pas.

Utilisation des arguments

Comme val1 et val2 sont des const void*, vous ne pouvez pas les déréférencer avec * ou ->. Il faut d'abord les convertir en des pointeurs sur le type des éléments du tableau, puis les déréférencer. Nous prendrons ici l'exemple du tri d'un tableau d'entiers :

int compareEntiers(const void* val1, const void* val2)
{
    int i1 = *(const int*)val1;
    int i2 = *(const int*)val2;
    // ...
}

Si on trie des entiers par ordre croissant, la fonction de comparaison peut se contenter de renvoyer la différence entre i1 et i2. En effet la valeur i1 - i2 est bien négative si i1 doit être avant i2 (i.e. si i1 < i2) et positive si i1 doit être après i2 (i.e. si i1 > i2).

Bref pour comparer i1 et i2 on retourne leur différence :

int compareEntiers(const void* val1, const void* val2)
{
    int i1 = *(const int*)val1;
    int i2 = *(const int*)val2;
    return i1 - i2;
}

Notez qu'on peut faire plus court en écrivant comme suit. Les const sont superflus dans le code de la fonction (mais pas dans le prototype !), et on n'a pas besoin de variable intermédiaire :

int compareEntiers(const void* p1, const void* p2)
{
    return *(int*)p1 - *(int*)p2;
}

Attention ! Le code précédent ne fonctionne pas dans les cas extrêmes où les entiers à comparer sont très grands. Imaginons que i1 = MAX_INT et i2 = -MAX_INT. Dans ce cas i1 - i2 = 2*MAX_INT, ce qui dépasse la capacité des entiers ! i1 - i2 risque alors d'être négatif, ce qui fausse le tri. Si l'on travaille avec de très grands entiers, il faut donc les comparer à la main :

int compareEntiers(const void* p1, const void* p2)
{
    int i1 = *(const int*)p1;
    int i2 = *(const int*)p2;
    if (i1 < i2)  return -1;
    if (i1 > i2)  return +1;
    return 0;
}

En fait qsort() n'a pas besoin du cas d'égalité : il veut juste savoir si i1 est avant ou après i2.

int compareEntiers(const void* p1, const void* p2)
{
    int i1 = *(const int*)p1;
    int i2 = *(const int*)p2;
    if (i1 < i2)  
        return -1;
    else
        return +1;
}

Ce que l'on peut abréger en :

int compareEntiers(const void* p1, const void* p2)
{
    return (*(int*)p1 < *(int*)p2) ? -1 : +1;
}

En pratique le cas se présente rarement en algorithmique et aux IOI, retourner la différence suffira dans la plupart des cas. Du moment que tous les entiers manipulés sont compris entre -1 milliard et +1 milliard, tout va bien. Par contre vous devez faire attention si les nombres à comparer sont issus de multiplication, par exemple si vous comparez i1 * A1 et i2 * A2 avec A1 et A2 grands.

Trier par ordre décroissant

Pour cela il suffit de changer la signification de la fonction de comparaison : on ne veut pas savoir si A est avant B, mais si A est après B (donc si B est avant A). Il suffit donc d'échanger A et B dans le corps de la fonction. Par exemple pour trier des entiers dans l'ordre décroissant on pourra faire :

int compareEntiers(const void* p1, const void* p2)
{
    return *(int*)p2 - *(int*)p1;
}

Comparer des structures

Imaginons que vous vouliez trier un tableau de points du plan selon leur abscisse :

struct point
{
    int x;
    int y;
};

int comparePointsSelonXpuisY(const void* p1, const void* p2)
{
    const point *point1 = (const point*)p1;
    const point *point2 = (const point*)p2;
    int diff = point1->x - point2->x;
    if (diff != 0)  
        return diff;
    else
        return point1->y - point2->y;
}

Notez que l'on garde les pointeurs en ne déréférençant pas tout de suite. C'est intéressant surtout si la structure est grosse, car cela évite au compilateur de recopier le contenu de la structure dans les variables temporaires : on ne garde que les pointeurs.

On peut abréger le code précédent en :

int comparePointsSelonXpuisY(const void* p1, const void* p2)
{
    point *point1 = (point*)p1;
    point *point2 = (point*)p2;
    int diff = point1->x - point2->x;
    return (diff) ? diff : point1->y - point2->y;
}

Remarquez également que tout ce qui a été dit sur la comparaison d'entiers reste valable : si les points peuvent prendre des coordonnées plus grandes que 1 milliard ou plus petites que -1 milliard, il faudra utiliser la méthode expliquée plus haut :

int comparePointsSelonXpuisY(const void* p1, const void* p2)
{
    point *point1 = (point*)p1;
    point *point2 = (point*)p2;
    return (point1->x != point2->x)
       ? ((point1->x < point2->x) ? -1 : +1)
       : ((point1->y < point2->y) ? -1 : +1);
}

Comparer des nombres flottants

Utiliser la distance algébrique ne fonctionne plus, car cette distance doit être convertie en un entier. Or si la distance est plus petite que 1 en valeur absolue, une fois convertie elle deviendra nulle ! De plus il se pose certains problèmes de précision si l'on compare des flottants très grands.

Bref, il faut comparer les deux éléments à la main :

int compareFlottants(const void* p1, const void* p2)
{
    return (*(double*)p1 < *(double*)p2) ? -1 : +1;
}

Récapitulatif

• Appeler qsort() pour trier le tableau valeurs contenant nbValeurs éléments :

  #include <stdlib.h>
  
  // ...
  
  qsort(valeurs, nbValeurs, sizeof(valeurs[0]), compareValeurs);
  

• Comparer des entiers compris entre -1 milliard et +1 milliard, dans l'ordre croissant

  int compareEntiers(const void* p1, const void* p2)
  {
      return *(int*)p1 - *(int*)p2;
  }
  

• Comparer des entiers compris entre -1 milliard et +1 milliard, dans l'ordre décroissant

  int compareEntiers(const void* p1, const void* p2)
  {
      return *(int*)p2 - *(int*)p1;
  }
  

• Comparer des entiers quelconques, dans l'ordre croissant

  int compareEntiersQuelconques(const void* p1, const void* p2)
  {
      return (*(int*)p1 < *(int*)p2) ? -1 : +1;
  }
  

• Comparer des entiers quelconques, dans l'ordre décroissant

  int compareEntiersQuelconques(const void* p1, const void* p2)
  {
      return (*(int*)p2 < *(int*)p1) ? -1 : +1;
  }
  

• Comparer des structures

  int comparePointsSelonXpuisY(const void* p1, const void* p2)
  {
      point *point1 = (point*)p1;
      point *point2 = (point*)p2;
      int diff = point1->x - point2->x;
      return (diff) ? diff : point1->y - point2->y;
  }
  

• Comparer des flottants

  int compareFlottants(const void* p1, const void* p2)
  {
      return (*(double*)p1 < *(double*)p2) ? -1 : +1;
  }
  

Remarques

• Il est important de bien définir sur le papier votre fonction de comparaison avant de commencer à coder. La plupart du temps il s'agira de comparer des entiers, mais dans certains cas ce peut être plus compliqué : comparaison de points du plan, de chaînes de caractères, etc. Il faut être sûr d'avoir un ordre valide : si on se donne trois éléments a, b, c tels que la fonction de comparaison dit que a AVANT b et b AVANT c, alors on doit avoir a AVANT c. Ceci est notamment vrai pour la relation ≤ ou ≥ des entiers et des flottants, ainsi que pour l'ordre lexicographique (l'ordre des mots du dictionnaire) utilisé pour comparer des chaînes de caractère.
• Si plusieurs éléments sont équivalents du point de vue de la relation de comparaison, rien ne garantit qu'ils resteront dans le même ordre dans le tableau final qu'au départ : on dit que qsort() est non-stable. C'est sans importance si vous triez des entiers ou des flottants, ça l'est par exemple si vous triez des points selon leur abscisse uniquement : si deux points ont la même abscisse, ils peuvent changer d'ordre après le tri.
• Le tableau est trié en place, c'est-à-dire que qsort() prend le tableau que vous lui donnez, le trie, et écrase le tableau original avec le tableau trié. Après le tri, le tableau non-trié est perdu. Si vous voulez le conserver, vous devez d'abord copier le tableau non-trié dans un autre tableau, puis trier cet autre tableau.

Recherche dichotomique

Avant de commencer, si vous ne savez pas ce qu'est une recherche par dichotomie, ignorez cette section. Une correction de sujet vous dira lorsque vous pourrez la lire.

Plutôt que de coder vos dichotomies à la main, vous pouvez utiliser la fonction bsearch() de la bibliothèque C standard, définie dans le fichier #include <stdlib.h>. Cette fonction ressemble beaucoup à qsort() décrite à la section précédente, dont nous supposerons que vous l'avez déjà lue.

La fonction de comparaison

bsearch() recherche une valeur dans un tableau initialement trié. Elle prend en argument l'objet cherché (la clé), le tableau, et fonction de comparaison qui permet de savoir si un élément donné est situé avant ou après la clé, ou bien est égal à la clé.

Arguments de bsearch()

1. Pointeur sur la clé
2. Pointeur sur le premier élément du tableau de recherche ; en pratique, il suffit de donner le nom du tableau
3. Nombre d'éléments du tableau
4. Taille de chaque élément, en octets ; sizeof(valeurs[0]) (où valeurs est le tableau de recherche) calcule cette taille pour nous
5. Fonction de comparaison

En pratique, pour rechercher la valeur clef dans un tableau valeurs contenant nbValeurs éléments, on donnera :

1. Un pointeur sur la clé, &clef
2. Le nom du tableau, valeurs
3. Le nombre d'éléments du tableau, nbValeurs
4. sizeof(valeurs[0])
5. Le nom de la fonction de comparaison

Note : même si la clé est un entier, vous ne pouvez pas la donner directement. Vous devez déclarer une variable, lui donner la valeur de la clé, et donner un pointeur sur cette variable à bsearch().

Valeur de retour

• bsearch() renvoie un pointeur sur l'élément trouvé, c'est-à-dire un pointeur sur un élément valeurs[i] pour lequel la fonction de comparaison indique qu'il est égal à la clé.
• Si aucun élément n'a été trouvé, bsearch() renvoie NULL.

Squelette d'utilisation

#include <stdlib.h>

int valeurs[nbValeurs];

int compareValeurs(const void* val1, const void* val2)
{
    // Ce qu'il faut mettre ici est décrit plus tard
    // ...
}

// ...

int clef = ...;
int *resultat = (int*)bsearch(&clef, valeurs, nbValeurs,
    sizeof(valeurs[0]), compareValeurs);

En pratique

Fonction de comparaison

La fonction de comparaison que vous donnez à bsearch() a (presque) la même signification que celle de qsort(). Si vous voulez d'abord trier le tableau avec qsort() puis rechercher des valeurs dedans avec bsearch(), vous pouvez utiliser la même fonction de comparaison.

Contrairement à la fonction de comparaison de qsort(), celle de bsearch() exige que si A et B sont des pointeurs sur des éléments identiques, alors compareValeurs(A, B) doit retourner zéro.

La valeur de retour de la fonction de comparaison doit donc être calculée comme suit. Si A est avant B dans le tableau, compareValeurs(A, B) doit renvoyer une valeur strictement négative. Même chose dans l'autre sens : A est après B dans le tableau, compareValeurs(A, B) doit renvoyer une valeur strictement positive. Si A est au même endroit que B, c'est-à-dire si A et B sont considérés comme identiques, on doit renvoyer zéro.

Attention !

Si vous voulez réutiliser la même fonction de comparaison pour qsort() et bsearch(), vous devez vérifier que la fonction de comparaison renvoie bien zéro quand ses arguments sont considérés comme identiques. Pour cette raison, certaines des fonctions de comparaison données dans la section précédente ne fonctionnent pas avec bsearch.

Le plus simple pour rendre une fonction de comparaison compatible avec bsearch() consiste à traiter le cas d'égalité tout au début de la fonction, c'est-à-dire à retourner zéro si les deux valeurs à comparer sont égales. Le reste de la fonction n'a pas besoin de changer.

Résultat

La valeur retournée par bsearch() doit être convertie en un pointeur du même type que les éléments de votre tableau. Par exemple, si vous avez un tableau de int, le résultat est un int*. Si c'est une chaîne char*, le résultat sera un char**.

Pour tester la nullité du pointeur résultat, pas besoin de comparer avec NULL : un simple if (resulat) suffit.

int clef = ...;
int *resultat = (int*)bsearch(&clef, valeurs, nbValeurs, 
                              sizeof(valeurs[0]), compareValeurs);

if (resultat)   // Pas besoin de != NULL
    printf("Trouvé : %d\n", *resultat);
else
    printf("Non trouvé\n");

Récapitulatif

• Appeler bsearch() pour chercher la valeur clef dans le tableau valeurs contenant nbValeurs éléments :

  #include <stdlib.h>
  
  int valeurs[nbValeurs];
  
  int compareValeurs(const void* val1, const void* val2)
  {
      // ...
  }
  
  // ...
  
  int clef = ...;
  int *resultat = (int*)bsearch(&clef, valeurs, nbValeurs, 
                                sizeof(valeurs[0]), compareValeurs);
  

• Comparer des entiers compris entre -1 milliard et +1 milliard, triés par ordre croissant dans le tableau

  int compareEntiers(const void* p1, const void* p2)
  {
      return *(int*)p1 - *(int*)p2;
  }
  

• Comparer des entiers compris entre -1 milliard et +1 milliard, triés par ordre décroissant dans le tableau

  int compareEntiers(const void* p1, const void* p2)
  {
      return *(int*)p2 - *(int*)p1;
  }
  

• Comparer des entiers quelconques, triés par ordre croissant dans le tableau

  int compareEntiersQuelconques(const void* p1, const void* p2)
  {
      int i1 = *(int*)p1;
      int i2 = *(int*)p2;
      if (i1 == i2)
          return 0;
      return (i1 < i2) ? -1 : +1;
  }
  

• Comparer des entiers quelconques, triés par ordre décroissant dans le tableau

  int compareEntiersQuelconques(const void* p1, const void* p2)
  {
      int i1 = *(int*)p1;
      int i2 = *(int*)p2;
      if (i1 == i2)
          return 0;
      return (i2 < i1) ? -1 : +1;
  }
  

• Comparer des structures

  int comparePointsSelonXpuisY(const void* p1, const void* p2)
  {
      point *point1 = (point*)p1;
      point *point2 = (point*)p2;
      int diff = point1->x - point2->x;
      return (diff) ? diff : point1->y - point2->y;
  }
  

• Comparer des flottants

  #include <math.h>
  
  const double epsilon = 1e-10;
  
  int compareFlottants(const void* p1, const void* p2)
  {
      double diff = *(double*)p1 - *(double*)p2;
      if (fabs(diff) < epsilon)
          return 0;
      return (diff < 0.) ? -1 : +1;
  }
  

  Pour des explications sur ce code, voir la section réservée à la comparaison des nombres flottants.

Génération de nombres aléatoires

Dans certains problèmes vous pourrez avoir besoin d'un générateur de nombres aléatoires. La bibliothèque C standard en comporte un, dans le fichier <stdlib.h>. Il se compose de deux fonctions, rand() et srand().

rand() tire un nombre aléatoire compris entre 0 et RAND_MAX (qui est une constante définie dans <stdlib.h>). Jusque-là c'est simple.

Malheureusement l'aléatoire n'existe pas en informatique, on parle de nombres pseudo-aléatoires parce qu'ils sont en fait générés par un algorithme qui essaye d'imiter le véritable aléatoire du mieux qu'il peut.

Initialiser le générateur

L'algorithme qui génère les nombres pseudo-aléatoires a besoin d'une valeur de départ, une graine (seed en anglais). À partir de cette valeur initiale, l'algorithme donnera autant de nombres pseudo-aléatoires que l'on voudra. On initialise le générateur de nombre pseudo-aléatoires avec la fonction srand() en lui donnant la valeur initiale en argument.

Dans la vraie vie, on initialise les générateurs de nombre pseudo-aléatoires avec une valeur imprévisible, en général l'heure courante : cela permet d'avoir une chaîne de nombres pseudo-aléatoires qui soit imprévisible elle aussi.

En algorithmique on préfère avoir des programmes déterministes, c'est-à-dire qui font toujours la même chose quand on leur donne les mêmes entrées. Or si on initialise le générateur avec une valeur qui dépend de l'heure, le programme ne fera pas la même chose selon l'heure à laquelle on l'exécute. Aux IOI cela veut dire que votre algorithme risquera d'obtenir un score différent si vous l'exécutez plusieurs fois de suite, et qu'il sera donc indéterministe ! Les juges des IOI interdisent formellement les programmes indéterministes, on préfère donc initialiser le générateur avec une valeur constante. Le choix de cette constante ne dépend que de vous, on note cependant une forte propension à utiliser 42...

En pratique

• Au tout début du programme, première ligne de main(), il faut appeler srand(constante) pour initialiser le générateur.
• À chaque fois que vous avez besoin d'un nombre aléatoire, exécutez rand().

Exemple :

#include <stdlib.h>
#include <stdio.h>

int main()
{
    srand(42);

    for (int i = 1; i <= 10; i++)
        printf("Valeur aléatoire n°%d: %d\n", i, rand());

    return 0;
}

Vous pouvez vérifier qu'en lançant le programme plusieurs fois de suite, vous obtenez toujours les 10 mêmes valeurs. Si vous changez le 42 en autre chose, vous obtiendrez une autre série de valeurs.

Tirer au hasard un nombre compris entre 0 et N-1 inclus

La fonction rand() tire un nombre compris entre 0 et RAND_MAX inclus. Pour tirer un nombre entre 0 et N-1, il suffit de prendre le modulo sur N, avec l'opérateur %. N'hésitez pas à mettre des parenthèses autour du modulo, la priorité des opérateurs joue parfois des tours.

Dans l'exemple suivant on tire aux dés. Le modulo donne un nombre compris entre 0 et 5, auquel on ajoute 1 pour obtenir un nombre compris entre 1 et 6 :

#include <stdlib.h>
#include <stdio.h>

int main()
{
    srand(42);

    for (int i = 1; i <= 10; i++)
        printf("Jet de dé n°%d: %d\n", i, (rand() % 6) + 1);

    return 0;
}

Pour la culture générale : les numériciens disent que prendre le modulo pour tirer un nombre aléatoire est très mal parce qu'on n'utilise que les bits de poids faible, c'est-à-dire que les chiffres correspondant aux petites puissances de 10 : unités, dizaines, rarement plus. Pour mieux faire il faudrait écrire (int)((double)N * rand() / (RAND_MAX + 1.)) pour tirer un nombre compris entre 0 et N-1 inclus.

Pour l'algorithmique de base et les IOI c'est rarement important, sauf avec certaines implémentations de la fonction rand(), qui ont un comportement pas du tout aléatoire quand on écrit rand() % 2 (alternance de 0 et de 1). Pour résoudre ce problème, vous pouvez soit utiliser la formule du paragraphe précédent (rappelée si vous tapez man 3 rand dans un shell) : (int)(2. * rand() / (RAND_MAX + 1.)), ou bien tout simplement écrire (rand() / 17) % 2.

Culture générale : coder son propre générateur de nombres pseudo-aléatoires

L'implémentation de rand() varie beaucoup d'un compilateur à l'autre, voire d'une version de compilateur à l'autre, et certaines sont beaucoup plus lentes que d'autres. Si vous voulez absolument une version rapide, vous devez coder votre propre fonction rand(). Notez que cela ne sert pas aux IOI.

La théorie des générateurs de nombres pseudo-aléatoires est extrêmement ardue, nous ne ferons que donner une méthode qui fonctionne assez bien pour les problèmes algorithmique classiques.

Le principe général est le suivant. Une variable globale x sert de paramètre pour générer le prochain nombre pseudo-aléatoire. Initialement, sa valeur est celle que l'on donne à srand(). Pour générer un nombre pseudo-aléatoire, on calcule x' = f(x), on remplace x par x', et on renvoie g(x). Dans l'histoire, f et g sont des fonctions « qui vont bien ». Concrètement :

int x = 42;

int my_rand()
{
    x = f(x);
    return g(x);
}

Que l'on peut simplifier en :

int my_rand()
{
    static int x = 42;
    return g(x = f(x));
}

Toute la difficulté est maintenant de trouver de bonnes fonctions f et g. Une technique pas trop mauvaise consiste à poser f(x) = x * A + B et g(x) = (x / C) mod (D + 1), où A, B et C sont très grands et « presque premiers », et où D = RAND_MAX. En pratique, on utilise un décalage de bits au lieu de la division ainsi qu'un ET logique au lieu d'un modulo pour gagner en rapidité d'exécution. Cela donne quelque chose comme :

int my_rand()
{
    static int x = 42;
    return ((x = x * A + B) >> C) & D;
}

On peut par exemple prendre les valeurs suivantes pour les constantes, afin de tirer un nombre pseudo-aléatoire compris entre 0 et 32767 (0x7FFF en hexadécimal, le 0x) :

int my_rand()
{
    static int x = 42;
    return ((x = x * 214013 + 2531011) >> 16) & 0x7FFF;
}