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 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 <stdio.h>
#include <math.h>

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

double calcul_pi(int n) {
  /* évalue PI par une méthode de Monte-Carlo */
  int k = 0;
  int i;

  for (i=0; i<n; i++) {
    double u = drand48();
    double v = drand48();
    if (v <= f(u)) {
      k = k+1;
    }
  }
  return 4 * (double)k/n;
}

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

  printf("%6.5f\n", pi);
  return 0;
}

Ce programme consiste en la définition de trois fonctions qui sont appelées f, calcul_pi et main. Ces fonctions en utilisent trois autres : f utilise sqrt, calcul_pi utilise drand48 et main utilise printf.

   

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, ainsi que la fonction << racine carrée >> sqrt, sont déclarées au moyen de #include <math.h>, et la fonction d'impression printf, au moyen de #include <stdio.h>.

Chaque définition de fonction a pour rôle d'introduire un nom (calcul_pi, f, 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 un double). C'est bien ainsi qu'elle est utilisée dans le corps de calcul_pi où l'on voit un appel << f(v) >>. 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 << */ >> est un commentaire (ou remarque) : inutilisables par la machine, les commentaires facilitent la compréhension des programmes.

Examinons les deux autres en-têtes :

• << double calcul_pi(int n) >> déclare que calcul_pi 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 assez simple :

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

  printf("%6.5f\n", pi);
  return 0;
}

Il commence par définir deux variables locales N et pi ; la première est initialisée par la constante 1000000, la seconde par le résultat de l'appel << calcul_pi(N) >>. Puis il appelle la fonction printf pour afficher à l'écran la valeur calculée de $\pi$. Enfin, il retourne 0 (cette dernière valeur est entièrement conventionnelle et ne concerne pas l'algorithme proprement dit).

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

double calcul_pi(int n) {
  int k = 0;
  int i;
  for (i=0; i<n; i++) {
    double u = drand48();
    double v = drand48();

    if (v <= f(u)) {
      k = k+1;
    }
  }
  return 4 * (double)k/n;
}

Après avoir défini deux variables, k et i, la première étant initialisée à zéro, il y a ensuite une instruction d'itération , qui débute par for, qui fait le gros du travail, puis un return. La valeur retournée est celle du produit de 4 par le résultat de la division de k, converti en flottant, par n.

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

   

unix% gcc -o pub pub.c -lm

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 11.41 secondes (la moitié de ce temps est consacré aux appels des fonctions externes sqrt et de rand48). Il y a heureusement des méthodes de calcul de $\pi$qui sont bien meilleures.