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 * 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.