Un exemple

Voici un algorithme pour calculer une approximation de $\pi$ :

<< Aller dans un pub, s'assurer qu'il contient bien un jeu de fléchettes et que la cible est un disque inscrit dans un carré, prier l'un des consommateurs de lancer des fléchettes n'importe où dans le carré, compter le nombre de fléchettes qui sont plantées dans le disque, et faire le quotient de ce nombre par le nombre total de fléchettes plantées dans le carré ; multiplier par 4 ce quotient ; retourner ce produit. >>

Si vous ne disposez pas des ressources naturelles nécessaires à l'implémentation de cet algorithme, vous pouvez recourir à un ordinateur et le programmer comme suit ; vous devrez simuler le lancer de fléchettes par un tirage de nombres aléatoires, et représenter le cadran supérieur droit du disque de la cible par une fonction $v=f(u) = \sqrt{1-u^2}$, avec $0\le u \le 1$ :

#include <cmath>                // déclare sqrt
#include <cstdlib>              // déclare drand48, srand48
#include <iostream>             // déclare cout, endl, <<

double f(double x) {
  // x doit être compris entre -1 et 1 
  return sqrt(1 - x*x);
}

bool lancer()
  // tirage d'un point dans le carré [0,1[ X [0,1[
{
    double u = drand48();
    double v = drand48();
    if (v <= f(u)) {
      return true;
    } else {
      return false;
    }
}

double calcul_aire(int n) {
  // évalue l'aire sous f par une méthode de Monte-Carlo
  int i, dedans;

  dedans = 0;
  for (i=0; i<n; i++) {
    if (lancer() == true) {
      dedans = dedans + 1;
    }
  }
  return double(dedans)/n;
}

int main() {
  // la fonction principale
  const int N = 1000000;
  double pi;

  srand48(0);
  pi = 4 * calcul_aire(N);
  cout << "Pi = " << pi << endl;
  
  return 0;
}

Ce programme consiste en la définition de quatre fonctions qui sont appelées f, lancer, calcul_aire et main. Ces fonctions en utilisent trois autres : f utilise sqrt, lancer utilise drand48, main utilise srand48. Ces trois autres fonctions, qui ne sont pas définies dans ce programme, sont déclarées dans les deux premières lignes : la fonction de génération de nombres pseudo-aléatoires, drand48, et celle de leur initialisation, srand48, sont déclarées au moyen de #include <cstdlib>, la fonction << racine carrée >> sqrt, est déclarée au moyen de #include <cmath> ; la troisième ligne, #include <iostream> permet de déclarer cout et l'opérateur d'écriture <<.

Chaque définition de fonction a pour rôle d'introduire un nom (f, lancer, etc), de déclarer la façon de l'utiliser (c'est son en-tête), et enfin de dire ce qu'elle fait (c'est son corps, placé entre << { >> et << } >>). Examinons la définition de f :

double f(double x) {
  return sqrt(1 - x*x);
}

L'en-tête de f est << double f(double x) >>. On y voit, outre f, deux autres noms, double et x : le premier est le nom d'un type de données, celui des nombres flottants en double précision, le second est celui d'un paramètre, qu'on retrouvera plus loin dans son corps. Cet en-tête déclare les conditions d'usage de la fonction : elle prend un argument de type double et donne un résultat de type double (on dit qu'elle retourne une valeur de type double). C'est bien ainsi qu'elle est utilisée dans le corps de lancer où l'on voit un appel << f(u) >>. Dans << double x >>, le type double précède le paramètre x, comme un adjectif précède le nom, selon l'usage de la langue anglaise.

Le corps de f contient une seule instruction, << return sqrt(1 - x*x); >>, qui contient l'expression << sqrt(1 - x*x) >>, exprimant $\sqrt{1-x^2}$, laquelle est un appel à la fonction sqrt ; l'argument de cet appel est l'expression << 1 - x*x >>. Cette dernière expression est formée à partir des opérateurs << - >> et << * >>, de la constante 1 et du nom x.

Le texte compris entre << // >> et la fin de la ligne est un commentaire, ou remarque : inutilisables par la machine, les commentaires facilitent la compréhension des programmes.

Examinons les en-têtes des deux autres fonctions:

• << bool lancer() >> déclare que lancer ne prend pas d'argument et retourne un bool, c'est-à-dire l'une des deux valeurs booléennes true ou false
• << double calcul_aire(int n) >> déclare que calcul_aire prend un argument de type int (un entier) et retourne un double (nombre flottant en double précision)
• << int main() >> déclare que main ne prend pas d'argument et retourne un int

Tout programme contient la définition d'une fonction principale qui doit s'appeler main ; l'exécution d'un programme commence par l'exécution de cette fonction main, qui appellera éventuellement d'autres fonctions. Son corps est ici assez simple :

int main() {
  const int N = 1000000;
  double pi;

  srand48(0);
  pi = 4 * calcul_aire(N);
  cout << "Pi = " << pi << endl;
  
  return 0;
}

Il commence par définir deux variables locales N et pi ; la première est une constante entière initialisée par la valeur 1000000, la seconde, de type double, n'est pas initialisée. Il appelle la fonction srand48, avec 0 pour argument, puis il affecte à pi la valeur de l'expression 4 * calcul_aire(N) ; celle-ci comprend l'appel de la fonction calcul_aire qui fait l'essentiel du travail. Ce programme affiche ensuite à l'écran une ligne comprenant la chaîne de caractères Pi = , suivie de la valeur de la variable pi, et d'un retour à la ligne (endl). Enfin, il retourne 0 (cette dernière valeur est entièrement conventionnelle et ne concerne pas l'algorithme proprement dit).

Le corps de calcul_aire est un peu plus élaboré :

double calcul_aire(int n) {
  int i, dedans;

  dedans = 0;
  for (i=0; i<n; i++) {
    if (lancer() == true) {
      dedans = dedans + 1;
    }
  }
  return double(dedans)/n;
}

Après avoir défini deux variables, i et dedans et affecté la seconde à 0, il y a une instruction d'itération, qui débute par for, qui fait le gros du travail, puis un return. La valeur retournée est le résultat de la division de dedans, une fois converti en flottant, par n.

Voici enfin le corps de lancer :

bool lancer()
{
    double u = drand48();
    double v = drand48();
    if (v <= f(u)) {
      return true;
    } else {
      return false;
    }
}

Après avoir défini deux variables, u et v et les avoir initialisées, chacune par un appel à drand48, il y a une instruction de branchement, qui débute par if. Chacune des deux branches du if retourne une valeur booléenne.

Ce programme, écrit dans un fichier pub.C, est compilé par g++ sous Linux, à l'aide de la commande

unix% g++ -o pub pub.C

Le programme exécutable, pub, est exécuté ; on obtient 3.14138 comme estimation de $\pi$, soit seulement trois décimales exactes, après un million de << lancers >> (c'est le int N = 1000000;) et en 0.98 seconde sur un Pentium 300 (la moitié de ce temps est consacré aux appels des fonctions externes sqrt et de drand48). Il y a heureusement des méthodes de calcul de $\pi$ qui sont bien meilleures¹.