Solutions du TD-4, listes

1  Tri fusion

Voici la classe MergeSort, dont toutes les méthodes sont récursives, ansi qu'une autre classe MergeSortBis dont toutes les méthodes sont itératives. (Les classes IntList et IntListList étaient données).

En effet, le programme récursif est incapable de trier des listes trop longues car la pile des appels de méthodes est assez limitée, ce qui limite radicalement la longueur des listes triables, sans que l'algorithme soit en cause. Néamoins, il s'agit d'une limitation de l'implémentation de Java disponible sur ma machine (ça plante pour 1000 éléments). et on ne peut pas condamner systématiquement le style récursif, qui reste le plus facile à programmer.
  static IntList merge(IntList l1, IntList l2) {
    if (l1 == null)
      return l2;
    if (l2 == null)
      return l1;

    if (l1.cont <= l2.cont)
      return new IntList (l1.cont,merge(l1.rest,l2));
    else
      return new IntList (l2.cont,merge(l1,l2.rest));
  }
En effet, ici, le code itératif de merge est un peu tordu, car il faut impérativement rendre une liste triée. L'idée consiste à ajouter des éléments en fin de liste et non pas en début de liste comme ont le fait d'habitude. Pour éviter des parcours de liste abusifs, on conserve un pointeur p sur la dernière cellule de la liste en cours de construction. En outre, on commence par allouer une cellule supplémentaire en tête de liste afin d'éviter le cas particulier de la première itération où aucune cellule n'est normalement allouée à l'itération précédente :
 static IntList merge(IntList l1, IntList l2) {
    IntList r = new IntList (-1,null); // première cellule bidon.
    IntList p = r ; // pointeur vers la dernière cellule de la liste r

    while (l1 != null && l2 != null)
      if (l1.cont <= l2.cont) {
        p.rest = new IntList (l1.cont,null);
        p = p.rest ;
        l1 = l1.rest ;
      } else {
        p.rest = new IntList (l2.cont,null);
        p = p.rest ;
        l2 = l2.rest ;
      }
    if (l1 == null)
      p.rest = l2;
    else if (l2 == null)
      p.rest = l1;

    return r.rest;
  }
Dans le cas des autres méthodes (comme startList ou mergeElt), l'ordre des éléments de liste n'a plus d'importance, on peut donc construire la liste résultat sans s'en préocuper :
  static IntListList startList (IntList l) {
    IntListList r = null ;

    while (l != null) {
      r = new IntListList (new IntList (l.cont,null),r) ;
      l = l.rest ;
    }
    return r;

  }
Donc si l est {1, 2, 3}, startList(l) renvoie {{3}, {2}, {1}}. Mais ce n'est pas grave.

Moralité : pensez à la récursion en premier, surtout lors d'un contrôle sur table, où la pile des appels de méthodes n'est pas limitée. (En revanche, vous n'avez pas d'ordinateur pour debugger un code difficile et le code itératif sera souvent plus long à écrire...)

Seconde moralité : rien n'est absolu en programmation et il faut parfois programmer en itératif.

2  Grands entiers

Voici la classe BigNat, les classes IntList et TestNat étaient données, pour compiler il faut aussi les classes NatPair et IntListPair (pour la division qui était la question 3.2). Ne vous laissez pas distraire par le code de la soustraction et de la division qui sont à la fin.

Un premier point à noter, entre entiers, la division réalisée est la division euclidienne. Inutile donc d'écrire :
  int q = (a - (a % b)) / b ;
  int q = (int)(a / b) ;
Pour être sûr que ``ça tombe juste''. Ces deux écritures sont équivalentes à :
  int q = a / b ;
Le code de l'addition est récursif, il y a peu à dire.
private static IntList addListCarry (IntList la, IntList lb, int carry) {
    if (la == null && lb == null)
      return bigger(carry) ;
    if (la == null) {
      if (carry == 0)
        return lb ;
      else
        return addListCarry (bigger(carry), lb, 0) ;
    }
    if (lb == null) {
      if (carry == 0)
        return la ;
      else
        return addListCarry(la, bigger(carry), 0) ;
    }
    int t = la.cont + lb.cont + carry ; // < 2^31 - 1
    if (t >= BASE)
      return consDigit (t - BASE, addListCarry (la.rest, lb.rest, 1)) ;
    else
      return consDigit (t, addListCarry (la.rest, lb.rest, 0)) ;
  }
Tout de même, remarquez que les cas qui terminent la récursion sont traités en premier. Ensuite, on a l'esprit libre pour traiter l'étape inductive. Remarquez aussi que les cas symétriques où une des deux listes est vide est pas l'autre, sont traités par du code symétrique.

Le code de la multiplication de la liste l par le chiffre d est itératif (pour rire un peu). Afin de présenter les chiffres dans le bon ordre, il faut ici encore construire la liste résultat en ajoutant des cellules en queue (et non pas en tête). On commence donc par s'assurer que le résultat n'est pas zéro (ie, il y a au moins un chiffre), puis on calcule le chiffre des unités. On a donc une première cellule de liste :
private static IntList multListCarry (int d, IntList l, int carry) {
    if (d == 0 || l == null)
      return bigger(carry) ;

    // Multiplication des unite's
    long t = (long)d * (long)l.cont + (long) carry ;
    IntList r = new IntList ((int)(t % BASE), null) ; // r est le re'sultat
    IntList tr = r ; // Dernie`re cellule alloue'e
    carry = (int)(t / BASE);
Ensuite on itère, chaque nouvelle cellule est rangée à sa place. C'est à dire comme cellule qui vient après celle allouée précedemment (tr), soit tr.rest = ..., où ... est la nouvelle cellule.
    l = l.rest ;
    for ( ; l != null ; l = l.rest) {
      t = (long)d * (long)l.cont + (long) carry ;
      tr.rest = new IntList ((int)(t % BASE), null) ;
      tr = tr.rest ;
      carry = (int)(t / BASE) ;
    }
Reste à ne pas oublier la retenue et c'est fini :
    // Traitement de la retenue
    tr.rest = bigger(carry) ;
    return r ;
  }
Ensuite la multiplication d'un grand nombre par un autre se fait en itérant la mutiplication par un chiffre selon l'algorithme classique :
  private static IntList shiftList (IntList l) { // multiplication par la base
    return consDigit(0, l) ;
  }

  BigNat mult (BigNat b) {
    IntList r = null ;
    IntList me = l ;
    IntList him = b.l ;
    for ( ; him != null ; him = him.rest, me  = shiftList(me)) {
      r = addList(r, multList(him.cont, me)) ;
    }
    return new BigNat (r) ;
  }
Le code itératif (quand même un peu compliqué) de la multiplication par un chiffre est à comparer au code récursif :
private static IntList multListCarry (int d, IntList l, int carry) {
  if (l == null)
    return bigger(carry) ;
  long t = (long)d + (long)l.cont + (long)carry ;
  return
    consDigit ((int) (t % BASE),
               multListCarry(d, l.rest, (int)(t  / BASE))) ;
Noter qu'il n'y a pas grand souci d'efficacité. On aurait pu essayer d'adapter un algorithme plus astucieux, présenté dans le cadre des polynomes par B. Werner dans son TD de la semaine dernière. Mais il n'est pas sûr que les listes soient la structure de donnée la mieux adaptée dans ce cas.

3  Rationnels

Voici les classes Ratio et Pi.

Il y a une astuce pour calculer la série :
1 +
1
3
+
1 * 2
3 * 5
+ ··· +
1 * 2 * ··· * n
3 * 5 * ··· * (2n + 1)
qui est de la forme :
1 + k(1) + k(1)k(2) + ··· + k(1)k(2)···k(n-1)k(n)
avec k(n) = n/2*n+1. On l'écrit :
1 + k(1) (1 + k(2) (1 + ··· + k(n-1) (1 + k(n))))
Soit, on considère la suite w0 = 1+ k(n), et wk+1 = 1 + k(n-k+1) w(k). On a 1+wn-1 égal à la somme de la série, soit égal à notre approximation par défaut de pi/2. Cette technique produira des dénominateurs plus petits que le calcul direct. C'est très semblable à la méthode de Horner pour évaluer les polynomes.

4  Pi en décimal

Voici la classe PiDecimal. Le calcul est exactement le même que précédemment, c'est l'affichage qui change. Pour obtenir l'affichage décimal, il suffit d'éffectuer la division, exactement comme on le ferait à la main :
  void print (int k) {
    NatPair qr = num.div(denom) ;

    System.out.print(qr.q) ;
    if (k > 0 && qr.r.compareTo(new BigNat (0)) > 0) {
      System.out.print (".") ;
      for (int i = k ; i > 0 ; i--) {
        BigNat a = qr.r.mult (new BigNat (10)) ;
        qr = a.div(denom) ;
        System.out.print(qr.q) ;
      }      
    }
  }
Pour une précision de 2-n, le résultat est affiché avec 1+(n+1)/3 décimales, c'est suffisant pour voir toutes les décimales justes (car log10(2) vaut un peu moins de 1/3).

Le code de la division elle même suit l'énoncé. Les chiffres du quotient sont calculés des poids forts vers les poids faibles. C'est ici encore, plus ou moins ce que l'on fait à la main :
  private static IntListPair divList (IntList a, IntList b) {

//  a < b -> q = 0, r = a
    if (compareList (a,b) < 0)
      return new IntListPair(null,a) ;
    
// appel récursif et fabrication du dividende a0 à cette étape
// on est maintenant dans le cas 2 (b <= a0 < BASE * b
    IntListPair p = divList(a.rest,b) ;
    IntList a0 = consDigit (a.cont, p.r);

// Recherche dichotimique du chiffre courant du quotient
    int g = 0 ;     // entre zéro
    int d = BASE ;  // et la base (strictement)
    int q ;
    IntList r ;
    while (true) {
      q = g + (d - g) / 2 ; // chiffre à essayer
      IntList bq = multList (q,b) ;
      if (compareList (a0,bq) < 0) // essai trop grand (strictement)
        d = q ;
      else {
        r = subList(a0,bq) ;
        if (compareList(b,r) > 0)  // quotient trouvé (a0 -bq < b)
          break ;
        else {
          g = q+1 ; // trop petit (strictement) (a0 - bq >= b)
        }
      }
    }
// Après sortie de la boucle (par break), r est le reste, q est le
// chiffre du quotient
    return new IntListPair (consDigit (q,p.q),r) ;
  }
La recherche dichotomique est notoirement difficile à programmer. Pour y arriver, il convient d'avoir les idées claires. Ici on recherche un chiffre q dans l'intervale [0 ... BASE[ et tel que 0 <= a0-bq < b, dont on sait qu'il existe (par hypothèse et par nature de la division euclidienne). À une étape, on cherche dans [g ... d[. Par l'existence du quotient, la recherche aboutira, pourvu qu'il y aie progression d'une étape à la suivante, c'est à dire. pourvu que d-g diminue strictement d'une étape à la suivante. Or, pour g < d, le chiffre testé q = g + (d-g)/2 est strictement plus petit que d, mais peu être égal à g, dans le cas d-g < 2. D'où l'affectation g = q+1 qui par ailleurs est correcte, car dans ce cas, q est strictement plus petit que le quotient et donc, le quotient est bien dans l'intervalle [q+1 ... d[.


Ce document a été traduit de LATEX par HEVEA.