3.9 Un exemple

Voici un algorithme qui permet de 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 ; 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. »

Figure: Calculer $\pi$ avec des fléchettes.

Si vous ne disposez pas des ressources naturelles nécessaires à la réalisation 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 quadrant supérieur droit du disque de la cible par une fonction $v=f(u) = \sqrt{1-u^2}$, avec $0\le u \le 1$ :

package monte_carlo;

class Cible {
  private int dedans;

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

  Cible() {
    dedans = 0;
  }

  int getDedans() {
    return dedans;
  }

  void lancer() {
    // tirage d'un point dans le carré [0,1[ X [0,1[
    double u = Math.random();
    double v = Math.random();
    if (v <= f(u)) dedans++;
  }
}

class Simulation {
  private static double calculAire(int n) {
    // évalue l'aire de la cible par une méthode de Monte-Carlo
    Cible cible = new Cible();
    for (int i=0; i<n; i++) cible.lancer();
    return (double)cible.getDedans()/n;
  }
  
  public static void main(String[] args) {
    int tirages = Integer.parseInt(args[0]);
    double pi = 4 * calculAire(tirages);
    System.out.println("Pi = " + pi);
  }
}

Il s'agit de la définition de deux classes, Cible et Simulation, membres du paquet monte_carlo. La première classe définit un modèle d'objets, la seconde un modèle de calcul. La classe Cible est destinée à être instanciée, c'est-à-dire à produire des objets de type Cible. Une fois ces objets créés, les deux opérations que l'on peut faire sur ceux-ci sont : lancer et getDedans. Ces deux opérations utilisent dedans, un champ de la classe Cible qui indique le nombre de fléchettes dans la cible et une fonction f qui détermine le contour d'une cible ; ce champ et cette fonction sont des membres de la classe Cible. La classe Simulation n'est pas destinée à être instanciée. Elle rassemble deux fonctions, calculAire et main. C'est cette dernière, dite fonction principale, par laquelle l'exécution du programme commence. Plaçons ces deux définitions de classe dans un fichier de nom Simulation.java. Puis compilons ce fichier par la commande suivante sous Linux :

linux% javac -d . Simulation.java

L'exécution de cette commande crée le répertoire monte_carlo et produit deux autres fichiers, Cible.class et Simulation.class, qui contiennent des instructions exécutables par la Machine Virtuelle Java. La classe Cible n'est pas exécutable, parce qu'elle ne contient pas de fonction principale. La classe Simulation peut être exécutée, parce qu'elle en contient une :

linux% java monte_carlo.Simulation 1000000

La commande java démarre une Machine Virtuelle Java, lui fournit la classe principale Simulation et l'argument 1000000. La Machine Virtuelle Java charge la classe Simulation et les classes que celle-ci utilise, notamment la classe Cible ; elle exécute ensuite les instructions définies par la fonction principale de Simulation.

Chaque cible est dotée d'un champ dedans, dont la valeur sera le nombre de fléchettes dans la cible (la cible ignore celles qui frappent le mur). Ce champ, de type int, est déclaré private, ce qui signifie qu'il n'est pas accessible de l'extérieur de la classe. On veut cependant pouvoir lire la valeur de ce champ, c'est ce que permet la méthode getDedans. Rappelons que la différence entre une fonction et une méthode est visible dans leurs en-têtes : une fonction est déclarée static, une méthode ne l'est pas. Une méthode est destinée à être appliquée à une instance de la classe, tandis qu'une fonction, qui ne dépend d'aucune instance, doit être invoquée via la classe où elle est définie. C'est pourquoi les fonctions sqrt (racine carrée), random (génératrice de nombres pseudo-aléatoires) et parseInt (conversion d'une chaîne de caractères en entier) sont invoquées sous la forme Math.sqrt(x), Math.random(), et Integer.parseInt(s). Ainsi, la méthode lancer n'a de sens que relativement à une cible particulière, et est invoquée sous la forme cible.lancer(), mais toutes les cibles partagent une même fonction f qui définit un même contour. La fonction f est également déclarée private, car on ne souhaite pas qu'une cible soit utilisée simplement pour obtenir les valeurs de cette fonction : on interdit ainsi à une autre classe de faire appel à elle.