Diviser pour régner

On obtient facilement des définitions récursives à partir de la conception descendante d'un algorithme : pour résoudre un problème par un algorithme, on applique ce même algorithme à un ou plusieurs sous-problèmes. Cette stratégie, appelée diviser pour régner permet d'écrire assez facilement des algorithmes parmi les plus intéressants, voire les plus efficaces.

38#38

La dichotomie est un exemple simple de cette stratégie. On cherche à calculer un zéro d'une fonction réelle continue 39#39 sur un intervalle 40#40, prenant des valeurs de signes opposés aux extrémités. Le théorème des valeurs intermédiaires assure l'existence d'un zéro. L'idée de la dichotomie est de chercher un zéro sur 41#41 ou bien sur 42#42, selon le signe de 43#43.

package exemples;

class Dichotomie {
  static double f(double x) { ... }

  static final double EPS = 1e-5;

  static double zéro(double a, double b) {
    // on suppose que f(a)*f(b) < 0
    double m = (a+b)/2;
    double fm = f(m);
  
    if (Math.abs(fm)<EPS) {
      return m;
    } else {
      if (f(a)*fm<0) {
        return zéro(a, m);
      } else {
        return zéro(m, b);
      }
    }
  }
}

La condition d'arrêt est Math.abs(fm)<EPS, EPS étant une variable de la classe Dichotomie, et Math.abs étant la fonction qui calcule la valeur absolue d'un double.