TD-3, Listes, grands entiers
|
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.
Le but de cet exercice est l'écriture d'un algorithme simple et
efficace de tri des listes.
Soient l1 et l2, deux listes triées d'entiers.
La fusion de l1 et de l2 est une nouvelle liste triée
d'entiers qui
regroupe les éléments de l1 et l2.
Il est relativement facile de calculer cette fusion en un temps
proportionnel à la somme des longueurs de l1 et l2.
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 ll1, dont
les éléments sont des
listes de longueur un, à raison d'une liste par élément de l.
Les éléments de ll1 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 ll1, ll2, ... , llk, ...,
en itérant le procédé.
Au bout d'un moment, llk 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 log2(n) fois et le coût des
fusions étant proportionnel à n, on a un tri en nlog(n).
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 ll1 à
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) |
|
On représente un entier arbitraire par la liste de ses chiffres dans
une base B. Ainsi l'entier n = c0 + c1B + ··· + cn-1Bn-1
+ cnBn est représenté par la liste {c0, c1,...
cn-1, cn} de ses chiffres qui sont des entiers strictement plus
petits que B, avec la convention que le chiffre le plus
significatif cn 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 <= 104 (calculs
intermédiaires en int) ou B <= 109 (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).
É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 :
-
É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.
- É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)
- É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 B2 qui doit donc être majoré par le plus grand entier positif
manipulable.
type entier |
plus grand entier |
base
maximale |
pourquoi |
|
int |
231 - 1 |
104 |
108 < 231-1 < 1010 |
long |
263 - 1 |
109 |
1018 < 263-1 < 1020 |
En outre, dans le cas de calculs en long, on a 109 < 231,
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.
É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.
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 * ··· * n |
|
3 * 5 * ··· * (2n + 1) |
|
On sait aussi que le reste de cette série est majorée par
1/2n.
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.
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 qt un nombre de cet intervalle, il y a alors trois
sous-cas :
-
Le produit bqt est strictement supérieur à a, alors il est
clair que q est strictement plus petit que qt.
- Autrement, (bqt <= a), on peut calculer rt = a - bqt
et il vient :
-
Si rt < b, alors qt est le quotient et rt le reste.
- Sinon, q est nécessairement strictement plus grand que qt.
Ces remarques permettent de programmer la recherche de q par
dichotomie. Ce qui assurera
un nombre d'étapes maximum de l'ordre de log2(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 à
{a0, a1,... an} et
{b0, b1,... bm} respectivement.
On considère j maximal tel que
{aj, aj+1, ... an} est supérieur ou égal à {b0,
b1,... bm}, 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
{aj-1, r0, r1, ... rk} 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 LATEX par
HEVEA.