ENPC - Programmation - Séance 1 - Correction


Mise en jambes

Le fichier de la classe BaseDeux doit être placé dans le fichier seance1/BaseDeux.java:

package seance1;
/**
 * Programme permettant de convertir un entier décimal en entier
 * binaire.
 */
public class BaseDeux {
  /**
   * Méthode principale appelée à l'exécution.
   * @param args le tableau qui contient les arguments placés sur la
   * ligne de commande lors de l'appel.
   */
  public static void main(String[] args) {
    // récupération de la valeur entière décimale
    // passée sur la ligne de commande 
    int argument = Integer.parseInt(args[0]);
    // Conversion de cette valeur entière décimale
    // en une chaîne de catractères représentant la même
    // valeur exprimée en binaire
    String resultat = Integer.toBinaryString(argument);
    // affichage de cette chaîne
    System.out.println(resultat);
  }
}


Exercice 1: factorielle

La définition récursive de la fonction factorielle est la suivante:
0! = 1
(n+1)! = (n+1) * n!

Voici la classe Exo1:

package seance1;
/**
 * Classe définissant une fonction calculant la factorielle.
 */
public class Exo1 {
  /**
   * Fonction récursive retournant la factorielle de son argument.
   * @param n l'entier, supposé positif ou nul, dont on veut calculer
   *          la factorielle.
   * @return la factorielle de l'entier n passé en argument.
   */
  public static int fact(int n) {
    // si n=0, n! = 1
    if (n==0)
      return 1;
    // sinon, n!= n * (n-1)!, on rappelle donc la fonction sur n-1
    return n * fact(n-1);
  }
  /**
   * Fonction de test. Affiche la factorielle de l'entier passé sur la
   * ligne de commande s'il est positif ou nul, ou bien affiche un
   * message d'erreur sinon.
   */
  public static void main(String[] args) {
    int n = Integer.parseInt(args[0]);
    if (n < 0) {
      System.out.println("Factorielle n'est pas définie sur " + n);
    } else {
      System.out.println(n + "! vaut " + fact(n));
    }
  }
}

Quand on écrit une fonction récursive, le(s) cas de base doi(ven)t toujours se trouver avant le cas général, et il faut toujours s'assurer que l'argument de la fonction évolue vers ce(s) cas de base.

On peut également écrire la fonction fact de manière itérative (en utilisant une boucle). Les appels récursifs vont alors disparaître :

public static int factIteratif(int n) {
  int r=1; // Va contenir les produits calculés au fur et à mesure par la boucle
  for (int i=2; i<=n; ++i)
    r = r + i;
  return r;
}

Comme il existe donc plusieurs manières différentes d'écrire une fonction réalisant le même calcul, il est naturel d'essayer de déterminer laquelle est la meilleure (si une est meilleure que l'autre). Il existe au moins deux critères fondamentaux pour comparer deux fonctions :

Ces mesures sont exprimées en fonctions des paramètres des fonctions. Il en existe d'autres, comme nous le verrons dans les exercices suivants.

Nous allons comparer les complexités en temps de nos deux fonctions calculant n!. Les opérations élémentaires (comparaisons de constantes et variables, changement de valeurs de variables, opérations arithmétiques, etc.) peuvent être considérées comme étant exécutées en temps constant, ne dépendant pas de l'argument n de la fonction.

Pour la version itérative du calcul, les instructions int r=1, int i=2 et return r sont toutes exécutées en un temps constant, que nous nommons c. Les expressions i>=n et ++i prisent seules sont également exécutées en temps constant, ainsi que l'instruction r=r+i. Notons d la somme du temps mis pour les réaliser une fois. Elles sont réalisées n-1, donc le temps mis au total par la fonction fact pour calculer son résultat est (n-1)c+d : le temps croît linéairement en fonction de la valeur de son argument n.

Pour la version récursive du calcul, notons a le temps (constant) mis pour réaliser une fois le test et un return. Notons b le temps (égelement constant) mis pour réaliser un produit une fois. Finalement, notons Un le temps mis par le calcul de fact(n). On a la relation récursive suivante :

En supprimant la récursivité de la relation on obtient : Comme pour le calcul itératif, le temps de calcul de fact(n) croît linéairement en fonction de la valeur de son argument n.

Intéressons nous maintenant à la complexité en espace.

Pour la version itérative, l'espace mémoire nécessaire au calcul est celui pris par le paramètre n et les deux variables r et i : l'espace mémoire ne dépend pas de n.

Pour la version récursive en revanche, si on note Sn l'espace mémoire pris par le calcul de fact(n), on a la relation suivante :

a est l'espace mémoire pris par n. Comme pour le calcul de la complexité en temps, la suppression de la récursivité dans cette fonction montre que l'espace mémoire pris par le calcul de fact(n) est une fonction linéaire croissante de n.

En conclusion, les calculs de complexité en temps ne permettent pas de différencier les deux manières de calculer mais la complexité en espace de la version itérative est bien meilleure que celle de la version récursive. On préférera donc utiliser la version itérative.


Exercice 2: Calcul de ab

On suppose dans la suite de cet exercice que a et b sont des entiers et que b ≥ 0.

  1. Première manière de calculer ab, en utilisant la définition récursive:
    package seance1;
    /**
     * Classe définissant deux manières de calculer l'exponentielle entre
     * deux entiers.
     */
    public class Exo2 {
      /**
       * Retourne la valeur de a exposant b. On suppose que b est positif
       * ou nul. Cette fonction récursive applique "bêtement" la
       * définition mathématique suivante:
       *     a^0 = 1
       *     a^(b+1) = a * a^b
       *
       * @param a l'entier dont on veut calculer la puissance b.
       * @param b la puissance, positive ou nulle, à laquelle on veut
       *          élever a.
       * @return la valeur de a puissance b.  */
      public static int expo1(int a, int b) {
        // cas de terminaison de la récursion
        if (b == 0)
          return 1;
        // cas de récursion qui fait décroître b
        return a * expo1(a, b-1);
      }
      /**
       * Fonction de test. Affiche le résultat de a puissance b où a et b
       * sont respectivement le premier et le second argument sur la ligne
       * de commande dans.
       */
      public static void main(String[] args) {
        int a = Integer.parseInt(args[0]);
        int b = Integer.parseInt(args[1]);
        if (b < 0) {
          System.out.println("L'exposant " + b + " n'est pas positif ou nul");
        } else {
          System.out.println(a + " à la puissance " + b + " vaut " + expo1(a,b));
        }
      }
    }
    
  2. Seconde manière de calculer ab, en utilisant la définition récursive:
    package seance1;
    public class Exo2 {
    
      ...
       
      /**
       * Retourne la valeur de a exposant b. On suppose que b est positif
       * ou nul. Cette seconde fonction récursive applique la
       * définition mathématique suivante:
       *     a^0      = 1
       *     a^(2k)   = (a * a)^k
       *     a^(2k+1) = a * (a * a)^k
       *
       * @param a l'entier dont on veut calculer la puissance b.
       * @param b la puissance, positive ou nulle, à laquelle on veut
       *          élever a.
       * @return la valeur de a puissance b.  */
      public static int expo2(int a, int b) {
        // cas de terminaison de la récursion
        if (b == 0)
          return 1;
        // 1er cas de récursion, où b est pair
        if (b%2 == 0)
          return expo2(a*a, b/2);
        // 2nd cas de récursion, où b est impair (c'est inutile de le tester)
        return a * expo2(a*a, b/2);
      }  
    
      ...
      
    }
    
  3. Étant donnés a et b, pour calculer ab avec expo1(), il semble clair que le nombre de multiplications et le nombre d'appels récursifs est le même: c'est b! On multiplie b fois a par lui-même.

    En revanche, avec expo2(), le nombre d'appels récursifs dépend directement du nombre de fois où il faut diviser b par 2 pour arriver jusqu'à 1 (en division euclidienne). Ce nombre est exprimé par le log2b. En ce qui concerne le nombre de multiplication, il dépend de ce même nombre, log2b, mais également du nombre de fois où, à l'occasion de ces divisions, on tombe sur un entier impair, ce qui coûte une multiplication de plus à chaque fois.

    Pour s'en convaincre, on peut ajouter dans la classe Exo2 deux variables statiques, multi et recurs, qui comptabilisent respectivement le nombre de multiplications et le nombre d'appels récursifs. Voici le programme complet comparant les deux techniques.
    package seance1;
    /**
     * Classe définissant deux manières de calculer l'exponentielle entre
     * deux entiers.
     */
    public class Exo2 {
      /**
       * Variable statique permettant de compter le nombre de multiplications.
       */
      static int multi;
      /**
       * Variable statique permettant de compter le nombre d'appels récursifs.
       */
      static int recurs;
      /**
       * Retourne la valeur de a exposant b. On suppose que b est positif
       * ou nul. Cette fonction récursive applique "bêtement" la
       * définition mathématique suivante:
       *     a^0 = 1
       *     a^(b+1) = a * a^b
       *
       * @param a l'entier dont on veut calculer la puissance b.
       * @param b la puissance, positive ou nulle, à laquelle on veut
       *          élever a.
       * @return la valeur de a puissance b.  */
      public static int expo1(int a, int b) {
        // cas de terminaison de la récursion
        if (b == 0)
          return 1;
        // cas de récursion qui fait décroître b
        // nécessite une multiplication et un appel récursif
        multi = multi + 1;
        recurs = recurs + 1;
        return a * expo1(a, b-1);
      }
      /**
       * Retourne la valeur de a exposant b. On suppose que b est positif
       * ou nul. Cette seconde fonction récursive applique la
       * définition mathématique suivante:
       *     a^0      = 1
       *     a^(2k)   = (a * a)^k
       *     a^(2k+1) = a * (a * a)^k
       *
       * @param a l'entier dont on veut calculer la puissance b.
       * @param b la puissance, positive ou nulle, à laquelle on veut
       *          élever a.
       * @return la valeur de a puissance b.  */
      public static int expo2(int a, int b) {
        // cas de terminaison de la récursion
        if (b == 0)
          return 1;
        // 1er cas de récursion, où b est pair
        // nécessite une multiplication et un appel récursif
        if (b%2 == 0) {
          multi = multi + 1;
          recurs = recurs + 1;
          return expo2(a*a, b/2);
        }
        // 2nd cas de récursion, où b est impair (c'est inutile de le tester)
        // nécessite deux multiplications et un appel récursif
        multi = multi + 2;
        recurs = recurs + 1;
        return a * expo2(a*a, b/2);
      }  
      /**
       * Fonction de test. Affiche le résultat de a puissance b où a et b
       * sont respectivement le premier et le second argument sur la ligne
       * de commande dans.
       */
      public static void main(String[] args) {
        int a = Integer.parseInt(args[0]);
        int b = Integer.parseInt(args[1]);
        if (b < 0) {
          System.out.println("L'exposant " + b + " n'est pas positif ou nul");
        } else {
          multi = 0;
          recurs = 0;
          System.out.println(a + " à la puissance " + b + " vaut " + expo1(a,b));
          System.out.println("Le calcul avec expo1() à requis " +
    			 multi + " multiplications et " +
    			 recurs + " appels récursifs");
          multi = 0;
          recurs = 0;
          System.out.println(a + " à la puissance " + b + " vaut " + expo2(a,b));
          System.out.println("Le calcul avec expo2() à requis " +
    			 multi + " multiplications et " +
    			 recurs + " appels récursifs");
        }
      }
    }
    
    

    Un exemple d'exécution donne alors, par exemple:
    % java seance1.Exo2 2 15
    2 à la puissance 15 vaut 32768
    Le calcul avec expo1() à requis 15 multiplications et 15 appels récursifs
    2 à la puissance 15 vaut 32768
    Le calcul avec expo2() à requis 8 multiplications et 4 appels récursifs
    


Exercice 3: Affichage d'un triangle

Voici la classe Triangle, avec ses méthodes afficheTriangle1() et afficheTriangle2():

package seance1;
/**
 * Classe d'affichage des triangles avec des symboles "*".
 */
public class Triangle {
  /**
   * Affiche à l'écran n lignes contenant une, puis deux, puis
   * trois... puis n étoiles.
   * @param n nombre de lignes à afficher.
   */
  public static void afficheTriangle1(int n) {
    for (int ligne=1; ligne<=n; ligne++) {
      for (int colonne=1; colonne<=ligne; colonne++) {
	System.out.print("*");
      }
      System.out.println();
    }
  }
  /**
   * Affiche à l'écran 2n-1 lignes contenant une, puis deux, puis
   * trois... puis n étoiles, avant de décroitre en n-1, puis n-2, etc
   * jusqu'à une seule étoile.
   * @param n nombre maximum d'étoiles à afficher sur une ligne.
   */
  public static void afficheTriangle2(int n) {
    for (int ligne=1; ligne<=n; ligne++) {
      for (int colonne=1; colonne<=ligne; colonne++) {
	System.out.print("*");
      }
      System.out.println();
    }
    for (int ligne=n-1; ligne>=1; ligne--) {
      for (int colonne=1; colonne<=ligne; colonne++) {
	System.out.print("*");
      }
      System.out.println();
    }
  }
  public static void main(String[] args) {
    int nbLigne = Integer.parseInt(args[0]);
    afficheTriangle1(nbLigne);
    afficheTriangle2(nbLigne);
  }
}

Pour changer arbitrairement de symbole, il suffit de déclarer que les fonctions le reçoivent en argument.

package seance1;
public class Triangle {
  ...
  public static void afficheTriangle1(int n) {
    ...
  }
  public static void afficheTriangle2(int n) {
    ...
  }
  /**
   * Affiche à l'écran n lignes contenant une, puis deux, puis
   * trois... puis n fois le symbole.
   * @param n nombre de lignes à afficher.
   * @param symbol symbole avec lequel dessiner le triangle.   
   */
  public static void afficheTriangle1(int n, String symbol) {
    for (int ligne=1; ligne<=n; ligne++) {
      for (int colonne=1; colonne<=ligne; colonne++) {
	System.out.print(symbol);
      }
      System.out.println();
    }
  }
  public static void main(String[] args) {
    int nbLigne = Integer.parseInt(args[0]);
    afficheTriangle1(nbLigne);
    afficheTriangle2(nbLigne);
    afficheTriangle1(nbLigne, args[1]);    
  }
}

En voici un exemple d'exécution:

java seance1.Triangle 4 "#"
*
**
***
****
*
**
***
****
***
**
*
#
##
###
####


Exercice 4: Calcul du triangle de Pascal

On rappelle que les coefficients binomiaux sont données par:

Voilà une fonction C1() récursive, déclarant deux paramètres entiers n et p, et retournant Cpn. Cette fonction fait partie de la classe Exo4 qui définit également la fonction affichePascal() et une méthode main() de test.

package seance1;
/**
 * Classe de calcul des coefficients binomiaux.
 */
public class Exo4 {
  /**
   * Première méthode de calcul pour C(n,p). Applique directement la
   * définition mathématique.
   * @param n le n de C(n,p)
   * @param p le p de C(n,p)
   * @return la valeur de C(n,p).  */
  public static int C1(int n, int p) {
    return Exo1.fact(n)/(Exo1.fact(n-p)*Exo1.fact(p));
  }
  /**
   * Affiche les nbLigne premières lignes du triangle de Pascal.
   * @param nbLigne nombre de lignes du triangle de Pascal souhaitées.
   */
  public static void affichePascal(int nbLigne) {
    // pour chaque ligne
    for (int n=0; n<=nbLigne; n++) {
      for (int p=0; p<=n; p++)
	System.out.print(C1(n,p)+" ");
      System.out.println();
    }
  }
  /**
   * Méthode de test.
   * @param args[0] le nombre de ligne du triangle de Pascal souhaitées
   *                spécifié sur la ligne de commande.
   */
  public static void main(String[] args) {
    affichePascal(Integer.parseInt(args[0]));
  }
}  

Le programme fonctionne correctement jusqu'à la valeur 12. Au delà, il y a dépassement de capacité. En effet, la fonction C1(n,p) requiert le calcul de n!. Or la valeur 13! est plus grande que la plus grande valeur représentable dans un entier de type int (cette valeur peut être obtenue par la constante Integer.MAX_VALUE). Lors des calculs, les valeurs "débordent" en quelque sorte des variables qui doivent les contenir, et les résultats du calcul sont erronés.

Pour remédier à ce problème, nous nous interdisons maintenant le calcul de la factorielle d'un nombre, et voulons réécrire notre programme.

Il est possible d'exprimer Cp+1n en fonction de Cpn.

De cette formule, on peut déduire une nouvelle fonction C2() récursive, déclarant deux paramètres entiers n et p, et retournant Cpn. La voici, avec la méthode affichePascal() modifiée dans la classe Exo4 complétée.

package seance1;
/**
 * Classe de calcul des coefficients binomiaux.
 */
public class Exo4 {
  /**
   * Première méthode de calcul pour C(n,p). Applique directement la
   * définition mathématique.
   * @param n le n de C(n,p)
   * @param p le p de C(n,p)
   * @return la valeur de C(n,p).  */
  public static int C1(int n, int p) {
    return Exo1.fact(n)/(Exo1.fact(n-p)*Exo1.fact(p));
  }
  /**
   * Seconde méthode de calcul pour C(n,p). Applique la formule
   * récursive suivante:
   *     C(n,0) = 1
   *     C(n,p) = C(n,p-1) * (n-p+1)/(p)
   * @param n le n de C(n,p)
   * @param p le p de C(n,p)
   * @return la valeur de C(n,p).
   */
  public static int C2(int n, int p) {
    // cas de terminaison de la récursion
    if (p==0)
      return 1;
    // cas de récursion faisant décroître p 
    // Attention à bien parenthèser: en effet si C2(n,p-1) * (n-p+1)
    // est divisible par p rien ne dit que (n-p+1) l'est.
    // Comme on ne manipule que des quantités de type int l'opération /
    // est la division entière
    return  (C2(n,p-1) * (n-p+1)) / (p);
  }
  /**
   * Affiche les nbLigne premières lignes du triangle de Pascal.
   * @param nbLigne nombre de lignes du triangle de Pascal souhaitées.
   */
  public static void affichePascal(int nbLigne) {
    // pour chaque ligne
    for (int n=0; n<=nbLigne; n++) {
      for (int p=0; p<=n; p++)
	System.out.print(C2(n,p)+" ");
      System.out.println();
    }
  }
  /**
   * Méthode de test.
   * @param args[0] le nombre de ligne du triangle de Pascal souhaitées
   *                spécifié sur la ligne de commande.
   */
  public static void main(String[] args) {
    affichePascal(Integer.parseInt(args[0]));
  }
}

Ce programme est ainsi utilisable jusqu'à la valeur 29 incluse. La fonction C2 permet donc de calculer plus loin que C1. En terme de complexités, on vérifie facilement que les deux ont des complexités en temps et en espace linéairement proportionelles à n pour C1 et p pour C2. Comme dans le pire des cas p vaut n les complexités sont donc identiques. On peut cependant améliorer C2 en l'écrivant de manière itérative :

public static int C3(int n, int p) {
  int r=1;
  for (int pp=1; pp<=p; ++pp)
    r = (r*(n-pp+1))/pp;
  return r;
}

Si la complexité en temps de C3 est linéairement proportionnelle à p, sa complexité en espace est constante.

Exercice 5: Calcul de racine d'un nombre par la méthode de Newton

À partir de la relation de Newton pour la racine carrée de a:

on peut partir de x0 = a et calculer n itérations:

package seance1;

public class Exo5 {
  /**
   * Calcule la valeur de racine carrée de x avec la méthode de Newton
   * en utilisant n termes.
   * @param x nombre dont on cherche la racine.
   * @param n nombre d'itérations dans l'interpolation de Newton
   * @return l'approximation de racine carrée de x avec Newton à n itérations
   */
  public static double calculRacine(double x, int n) {
    double r = x;
    for (int i=0; i<n; i++) {
      r = (r + x/r) / 2;
    }
    return r;
  }
  public static void main(String[] args) {
    double x = Double.parseDouble(args[0]);
    int n = Integer.parseInt(args[1]);
    System.out.println("Avec notre méthode, racine de " +
		       x + " vaut " + calculRacine(x,n));
    System.out.println("Avec Math.sqrt(), racine de " +
  		       x + " vaut " + Math.sqrt(x));
  }
}


Exercice 6: Calcul de logarithme par développement limité

package seance1;
/**
 * Calcul approché du logarithme naturel d'un nombre.
 */
public class Exo6 {
  /** 
   * Calcule le logarithme naturel de x au voisinage de 1
   * par un développement limité à n termes
   * @param x nombre dont on cherche le logarithme naturel, au voisinage de 1.
   * @param n nombre de termes du DL
   * @return  l'approximation de ln(x) au voisinage de 1 avec un DL à n termes.
   */
  public static double developpementLimiteLog(double x,int n) {
    x -= 1.0;
    double r = x;   // Stocke le résultat
    double ppx = x; // Pour les puissances successives de x
    for (int i=2; i<=n; ++i) {
      ppx *= x;
      if (i%2==1)
	r += ppx/i;
      else
	r -= ppx/i;
    }
    return r;
  }
  /**
   * Calcule le logarithme naturel de x avec un DL
   * en se ramenant à des cas où le paramètre est dans l'intervalle [1,1+1/n[.
   * Utilise la fonction Exo5.racine() avec n pour second paramètre.
   * Donc, plus n est grand, plus la précision du calcul de ln est grande.
   * @param x nombre dont on cherche le logarithme naturel.
   * @param n précision souhaitée (grand = grande précision)
   * @return l'approximation de ln(x) avec le degré de précision n.
   */
  public static double ln(double x, int n) {
    if (x<1.0) return -ln(1/x,n);
    if (x>10.0) { // Fait converger plus rapidement au voisinage de 1
      int k=0;       // pour les grands nombres
      while (x>10.0) {
	x /= 10.0;
	++k;
      }
      return (ln(x,n)+k*ln(10.0,n));
    } // Maintenant, 1<=x<=10
    if (x>1.0+1.0/n)
      return 2.0*ln(seance1.Exo5.calculRacine(x,n),n);
    else  // On est suffisament proche de 1 pour appliquer le DL
      return developpementLimiteLog(x,n);
  }
  public static void main(String[] args) {
    double x = Double.parseDouble(args[0]);
    int n = Integer.parseInt(args[1]);
    System.out.println("Avec notre méthode, ln de " +
		       x + " vaut " + ln(x,n));
    System.out.println("Avec Math.ln(), ln de " +
  		       x + " vaut " + Math.log(x));
  }
}


Nicolas.Bedon[at]univ-mlv.fr - Etienne.Duris[at]univ-mlv.fr - © ENPC - Novembre 2002 - http://www-igm.univ-mlv.fr/~duris/ENPC