TD-3, Listes, grands entiers

TD-3, Listes, grands entiers

Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/TD-3/

Envoyez vos programmes à Luc.Maranget@inria.fr. Les solutions sont ici.

Avertissement

Ce TP contient trois exercices, le premier est un classique ---ce qui s'enseigne en classe et vaut d'être imité (Régis Debray, Loués soient nos seigneurs). Les deuxièmes et troisièmes sont plus longs et se complètent. Ceux qui maîtrisent bien les listes peuvent s'abstenir de ce premier exercice, afin de disposer d'assez de temps pour le troisième.

1	Tri fusion des listes

Le but de cet exercice est l'écriture d'un algorithme simple et efficace de tri des listes.

1.1

Principe

Soient l₁ et l₂, deux listes triées d'entiers. La fusion de l₁ et de l₂ est une nouvelle liste triée d'entiers qui regroupe les éléments de l₁ et l₂. Il est relativement facile de calculer cette fusion en un temps proportionnel à la somme des longueurs de l₁ et l₂. Le principe du tri complet d'une liste d'entiers l consiste à itérer la fusion sur les couples de sous-listes de l.

Au commencement, on produit une liste de listes d'entiers ll₁, dont les éléments sont des listes de longueur un, à raison d'une liste par élément de l. Les éléments de ll₁ sont donc des listes triées.

On définit ensuite un procédé. On se donne ll, liste de de listes triées d'entiers, telle que ll contient deux listes ou plus. On construit une nouvelle liste ll' plus courte que ll en fusionnant deux à deux des éléments de ll. Plus précisément, un élément de ll' est la fusion de deux éléments successifs de ll. Par définition de la fusion, les éléments de ll' sont des listes triées. Par le procédé, ll' a en gros deux fois moins d'éléments que ll.

On calcule donc ll₁, ll₂, ... , ll_k, ..., en itérant le procédé. Au bout d'un moment, ll_k ne contient plus qu'une seule liste qui est une copie triée de l. Soit, si n est la longueur de la liste l, le procédé s'appliquant en gros log₂(n) fois et le coût des fusions étant proportionnel à n, on a un tri en nlog(n).

1.2

Programmation

Voici notre amie la classe IntList des listes d'entiers, en compagnie d'une copine la classe IntListList des listes de listes d'entiers.

class IntList {
  int cont ;
  IntList rest ;

  IntList (int cont, IntList rest) {
    this.cont = cont ;
    this.rest = rest ;
  }

  public String toString () {
    StringBuffer r = new StringBuffer () ;

    IntList me = this ;
    r.append("{") ;
    if (me != null) {
      while (me.rest != null) {
        r.append(me.cont + ", ") ;
        me = me.rest ;
      }
      r.append(me.cont) ;
    }
    r.append("}");
    return r.toString () ;
  }
}

Noter que ces classes possèdent déjà des méthodes toString, de sorte que l'on affichera les listes directement par println.

Écrire une classe MergeSort qui trie une liste d'entiers. La démarche suivante est suggérée :

Écrire une méthode préliminaire qui fabrique une liste d'entiers aléatoires dont la taille est passée en argument.
```
  static IntList randomList(int n) // Renvoie une liste de longueur n
```
Écrire la méthode merge, qui réalise la fusion :
```
  static IntList merge(IntList l1, IntList l2)
```
Écrire une méthode startList qui calcule ll₁ à partir de l (voir la section précédente).
```
  static IntListList startList (IntList l)
```
Programmer le procédé de la section précédente en une méthode mergeElts.
```
  static IntListList mergeElts (IntListList ll)
```
Terminer en écrivant une méthode sort qui trie son argument.
```
  static IntList sort (IntList l)
```
Testez le tout en écrivant la méthode main idoine.

Si tout se passe bien (ce dont je ne doute pas), vous devriez obtenir quelque chose de ce style :

maranget@manche ~/TD/TD-3 > java MergeSort 10
La liste : {133, 140, 228, 59, 66, 183, 212, 210, 37, 83}
La liste triée : {37, 59, 66, 83, 133, 140, 183, 210, 212, 228}

Vous pouvez ensuite tester votre programme sur des listes plus longues, que se passe-t-il ? Si il y a problème, comment y remédier ? Solution.

2	Grands entiers (naturels)

2.1

Principe

On représente un entier arbitraire par la liste de ses chiffres dans une base B. Ainsi l'entier n = c₀ + c₁B + ··· + c_n-1B^n-1 + c_nBⁿ est représenté par la liste {c₀, c₁,... c_n-1, c_n} de ses chiffres qui sont des entiers strictement plus petits que B, avec la convention que le chiffre le plus significatif c_n est non-nul. En outre, zéro est représenté par la liste vide. Notez aussi que l'ordre de la liste est le chiffre le moins significatif en premier (ce qui facilitera l'arithmétique).

Pour faciliter l'affichage la base B est multiple de 10, on pourra faire le choix B = 10 (simplicité), B <= 10⁴ (calculs intermédiaires en int) ou B <= 10⁹ (calculs intermédiaires en long).

La classe BigNat des grands entiers aura donc sensiblement cette forme :

class BigNat {
  final static int BASE = 10 ; // Base maximale 1000000000
  private IntList l;

  private BigNat (IntList l) { // Constructeur pour les besoins internes
    this.l = l ;
  }

  BigNat (int i) {  // Constructeur appelé de l'exterieur
    ...
  }
}

(La classe IntList est donnée, elle possède une méthode toString, utile pour le mise au point).

2.2

Programmation

Équipez la classe BigNat de son constructeur, puis d'une méthode toString et des opérations addition et multiplication. On suggère la démarche suivante (vous êtes libre de procéder autrement, mais vous devez respecter les signatures des méthodes non-privées, afin de bénéficier de la procédure de test finale).

Écrire une méthode :
```
private static IntList consDigit (int d, IntList l)
```
qui ajoute un chiffre en tête de d'une liste de chiffres, en prenant bien garde à ne pas introduire de zéro en position la plus significative.
Écrire une méthode :
```
private static IntList bigger (int i)
```
qui prend un entier (positif) en argument et renvoie la liste de ses chiffres.
Écrire le constructeur BigNat(int i).
Écrire la méthode d'addition :
```
BigNat add(BigNat b)
```
Telle que a.add(b) renvoie le grand entier qui représente la somme des grands entiers représentés par a et b. On suggère la démarche suivante :
1. Écrire une méthode privée d'addition de deux listes avec retenue :
```
private static IntList addListCarry (IntList la, IntList lb, int carry)
```
  Étant données deux listes de chiffres la et lb (représentant les entiers a et b), et un chiffre carry (retenue), cette méthode renvoie la liste des chiffres de l'entier somme de a de b et de la retenue.
2. Écrire la méthode qui réalise la somme de deux listes de chiffres sans retenue initiale :
```
private static IntList addList (IntList la, IntList lb)
```
3. Écrire la méthode add.
Écrire la méthode toString. On prendra soin, dans le cas où la base n'est pas 10, de ne pas oublier de zéros. On aura sans doute besoin de quelques méthodes privées auxiliaires et de la classe StringBuffer.
Écrire la méthode de multiplication en suivant une démarche analogue au cas de l'addition.
```
BigNat mult(BigNat b)
```
C'est la multiplication qui impose les contraintes les plus strictes sur la base B. En effet, la multiplication de deux chiffres plus un chiffre de retenue vaut au maximum (B-1)(B-1) + B-1, soit est bornée par B² qui doit donc être majoré par le plus grand entier positif manipulable.

type entier plus grand entier base maximale pourquoi

int 2³¹ - 1 10⁴ 10⁸ < 2³¹-1 < 10¹⁰

long 2⁶³ - 1 10⁹ 10¹⁸ < 2⁶³-1 < 10²⁰

En outre, dans le cas de calculs en long, on a 10⁹ < 2³¹, autrement dit les chiffres peuvent bien être stockés comme des int.

Notez bien que vous pouvez afficher les listes à tout moment ce qui peut vous aider à mettre au point votre programme, avant même d'avoir écrit toString.

Vous testerez ensuite votre classe BigNat à l'aide de la classe TestNat. Vous obtiendrez ceci :

maranget@manche ~/TD/TD-3 > java TestNat 50
Puissances de deux de 1 a 50
2^1 = 2
2^2 = 4
2^3 = 8
  ....

2^50 = 1125899906842624
Les deux nombres suivants doivent etre egaux
2251799813685248
2251799813685248
Factorielles de 1 a 50
1! = 1
2! = 2
3! = 6
  ...
50! = 30414093201713378043612608166064768844377641568960512000000000000

La sortie complète est en textnat.txt, à comparer à votre sortie redirigée vers un fichier et par la commande diff.

Il est conseillé de commencer par B=10, en effet les listes de chiffres correspondent alors à l'intuition héritée de l'école primaire. Ensuite, augmentez la base, et voyez si votre code fonctionne encore.

Solution.

3	Rationnels

Écrire une classe Ratio des nombres rationnels (positifs). Le numérateur et le dénominateur seront bien évidemment des grands entiers BigNat.

La classe Ratio devra exporter les méthodes suivantes :

// Trois constructeurs
Ratio (BigNat num, BigNat denom)
Ratio (int num, int denom) // contruire num/denom
Ratio (int num)            // construire num/1

Ratio add (Ratio b)
Ratio mult (Ratio b)
public String toString ()

Avec les significations attendues.

3.1

Grecs et modernité

Les anciens se sont énormément fatigués pour trouver un encadrement du nombre pi. Or, ils ne savaient manipuler que des rationnels, qu'ils écrivaient sous forme de fractions. (La découverte de l'irrationalité de racine de 2 ayant même, paraît-il, été tenue secrète).

Pour le moment nous en sommes un peu au même point qu'eux avec notre classe Ratio. Tout de même, quelques hommes célèbres ont fait avancer les mathématiques entre temps et on sait que la série suivante converge vers pi/2 :

1 +

1 * 2

3 * 5

+ ··· +

1 * 2 * ··· * n

3 * 5 * ··· * (2n + 1)

On sait aussi que le reste de cette série est majorée par 1/2ⁿ.

En déduire un programme Pi qui donne un encadrement à 2^-k près de pi pour k donné.

maranget@manche ~/TD/TD-3 > java Pi 7
Nombre de termes : 8
Minorant de PI : 108184320/34459425
Majorant de PI : 13882052385/4410806400

Solution.

3.2

Modernité

Il n'est pas sûr qu'Archimède aurait été très satisfait de nos fractions, elles ne sont pas réduites et ce sont loin d'être les plus simples possibles (22/7 fournit une approximation de l'ordre de la nôtre ci-dessus !). Nous n'allons pas aborder cette question qui nous entraînerait un peu loin mais plutôt effectuer les divisions. Ce qui nous donnera des résultats sous une forme plus conforme aux habitudes modernes.

Il va donc falloir commencer enrichir la classe BigNat, des méthodes suivantes :

Une méthode compareTo de comparaison, il est conseillé de suite le modèle de compareTo des chaînes.
```
int compareTo(BigNat b)
```
Une méthode de soustraction :
```
BigNat sub(BigNat b)
```
Si dans ``a.sub(b)'', b est strictement plus grand que a, la méthode sub devra échouer.

Ces deux premières méthodes ne présentent guère plus de difficultés algorithmiques que l'addition et la multiplication. Il est vivement conseillé d'adopter la même démarche qu'à la section 2, car la division utilisera largement les comparaisons et soustractions sur les listes de chiffres.

En effet, la division est plus difficile à programmer.

Considérons la méthode privée de division sur les listes de chiffres

private static IntListPair divList (IntList a, IntList b)

Cette méthode renvoie un objet de la classe IntListPair qui est la paire des listes quotient et reste de la division de a par b.

Il est clair que si a < b, alors le quotient est zéro et le reste a.

Intéressons nous ensuite au cas b <= a et a < B * b, alors le quotient de la division de a par b est un chiffre de la base et toute la difficulté consiste à le trouver. On remarquera :

Le quotient q est forcément dans l'intervalle (0... B(.
Soit q_t un nombre de cet intervalle, il y a alors trois sous-cas :
- Le produit bq_t est strictement supérieur à a, alors il est clair que q est strictement plus petit que q_t.
- Autrement, (bq_t <= a), on peut calculer r_t = a - bq_t et il vient :
  - Si r_t < b, alors q_t est le quotient et r_t le reste.
  - Sinon, q est nécessairement strictement plus grand que q_t.

Ces remarques permettent de programmer la recherche de q par dichotomie. Ce qui assurera un nombre d'étapes maximum de l'ordre de log₂(B). Nous venons en fait de décrire l'étape clé de l'algorithme classique de division, mais sans réponse intuitive aucune à la question ``en a combien de fois b ?''. L'algorithme de Knuth vu en cours est plus efficace, puisqu'il permet de trouver directement le chiffre du quotient, mais la dichotomie n'est pas ridicule.

Il reste à itérer convenablement cette étape pour en finir. Posons, les listes a et b égales à {a₀, a₁,... a_n} et {b₀, b₁,... b_m} respectivement. On considère j maximal tel que {a_j, a_j+1, ... a_n} est supérieur ou égal à {b₀, b₁,... b_m}, on applique l'étape clé obtenant un chiffre, q et une liste de chiffres r. Le chiffre q est le chiffre le plus significatif du quotient, on obtiendra le suivant en divisant {a_j-1, r₀, r₁, ... r_k} par b... Et ainsi de suite, jusqu'à épuiser tous les chiffres de a.

Une fois réalisée la division sur les listes de chiffres, reste à en faire profiter le monde extérieur.

NatPair div (BigNat b)

Où la classe NatPair, décrit les paires de grands entiers.

Ouf, il n'en faut pas plus pour enrichir la classe Ratio d'une méthode print

void print (int k)

qui affiche l'écriture décimale du rationnel avec k chiffres après la virgule (sans arrondi).

maranget@manche ~/TD/TD-3 > java PiDecimal 100
Minorant de PI : 3.1415926535897932384626433832794342
Majorant de PI : 3.1415926535897932384626433832802231

Solution.

Dernière modification : 2002-11-27

Ce document a été traduit de L^AT_EX par H^EV^EA.