Suite à l'article où je décrivais les grands nombres à travers les tableaux, voilà pour tous ceux qui sont obligés d'utiliser les listes, les fonctions correspondantes.
La grande différence avec les tableaux, est que les tableaux se traitent de manière linéaire, alors que les listes se traitent de manière récursive.
Pratiquement, une fonction qui se rappelle stocke sur la pile ses données, et son point de retour à la fin de la fonction appelée sur le stack, et quand la sous-routine se termine, les paramètres de la précédente ( appelée mère ), sont restaurés.
Théoriquement, il y a deux types de récursivité, la récursivité terminale, et la récursivité non-terminale.
La récursivité non-terminale, c'est quand on rappelle la fonction avec les nouveaux paramètres, et qui se termine en renvoyant le résultat, c'est à dire que le résultat va remonter toutes les feuilles de calcul.
Pour la récursivité terminale, on rappelle la fonction en lui passant un accumulateur, c'est lui qui contiendra le retour, et évitera ainsi de tout désempiler lors du retour.
Les deux méthodes sont équivalentes en temps machine, mais il faut les connaître, c'est très utile suivant le type de calculs à effectuer.
Une cellule de la liste contient l'adresse de la suivante, c'est pour cela que l'on les appelle les listes chaînées.
Un exemple, en prenant pour convention le stockage à l'envers du nombre dans la liste, c'est à dire que le premier sera l'unité puissance zéro, on aura, pour 51987:
| 7 | 8 | 9 | 1 | 5 |
La liste correspondante pointera sur le 7, plus facile à utiliser pour additionner deux listes, mais on peut choisir un autre sens. L'avantage des listes étant que, à chaque fois que l'on a besoin d'une nouvelle case, on la crée. Voyons la déclaration d'une liste :
Type
Liste = ^Cellule;
Cellule = Record
Caract : Char;
Suivant : Liste;
End;
Il s'agit d'un pointeur sur un type record, contenant le caractère, ou un byte, suivant son goût personnel, et l'affichage. Ensuite, il faut des instructions pour initialiser une liste :
Function Init : Liste; Begin Init := Nil end;
Et d'autres pour créer le premier élément. On procédera ainsi:
var A : liste; begin a := Init; end;
La liste est initialisée, pour l'allocation, elle se fera toute seule, lors de la première opération, du genre A := CONS ('0', A );, puisque tout est traité avec des caractères par la suite. Voyons cette fonction :
Function Cons (Element : Char; L : Liste) : Liste;
Var
Nouv_Liste : Liste;
Begin
New(Nouv_Liste); (* on cree la cellule *)
Nouv_Liste^.Caract := Element; (* on met le caractere *)
Nouv_Liste^.Suivant := L; (* on prend l'adresse envoyee comme *)
Cons:=Nouv_Liste; (* nouvelle case vide potentielle *)
(* et on rattache le tout *)
End;
Bien évidemment, on ne peut rajouter une case qu'en tête de liste, d'où le besoin d'établir des conventions, comme stocker le nombre à l'envers, et la première case lue sera celle des unités puissance 0.
Une autre fonction nécessaire est savoir si la liste est vide, si c'est le cas, il n'y a rien à traiter :
Function Liste_Est_Vide(L : Liste) : Boolean; Begin Liste_Est_Vide := (L=Nil) End;
Maintenant, pour extraire un nombre, on ne peut extraire que la queue, je m'explique, la tête de la liste pointe sur NIL, au cas où on voudrait rajouter une case, et donc, comme le montre le graphe, c'est la queue de la liste qui contient l'adresse de la cellule suivante et ainsi de suite jusqu'à la tête.
Pour parcourir la liste, on lira la queue, puis on passera à la case suivante... Il n'y a pas de parcours en sens inverse possible, car on ne garde pas trace de la cellule précédente, ce qui est d'ailleurs inutile dans le travail sur les nombres par les listes.
Voici donc comment lire la queue de la liste :
Function Premier (L : Liste) : Char; Begin Premier := L^.Caract End;
Et comment la retirer pour lire la case suivante :
Function Reste (L : Liste) : Liste; Begin Reste := L^.Suivant End;
Maintenant, pour admirer vos essais, voici comment afficher une liste :
Procedure Affiche_Liste(L : Liste);
Begin
If Not Liste_Est_Vide(L) Then
Begin
Write (Premier(L));
Affiche_Liste(Reste(L))
End
End;
Il arrive qu'au bout d'un moment on veuille savoir le nombre d'éléments d'un liste, voici comment y arriver :
Function Longueur (L : Liste) : integer;
Var
TAILLE : Integer;
Begin
TAILLE := 0;
Repeat
L := Reste(L);
TAILLE := TAILLE + 1;
Until Liste_est_vide (L);
LONGUEUR := TAILLE;
End;
Et à cause de la convention de stockage, il arrive parfois que, par la récursivité, que la liste soit renvoyée à l'envers, et donc il faut l'inverser :
Function Miroir (L : liste) : Liste;
Var
L_inv : Liste;
Begin
L_inv := init;
While not Liste_est_vide(L) do Begin
L_inv := cons(premier(L),L_inv);
L := reste (L);
End;
Miroir := L_inv;
End;
Le renversement à été fait de manière linéaire, et ne pouvait pas être fait de manière récursive ici à cause des listes. Voyons maintenant comment comparer deux listes, ci-dessous ce test, on envoie A et B et on veut la comparaison :
Function Test_A_Plus_Grand_Que_B (NA,NB: Liste): Integer;
Var
B: Integer;
(* NB : Valeurs possibles de B:
0: Egalité de NA et NB
1: NA > NB
2: NA < NB *)
Begin
If Longueur(NA)>Longueur(NB)
then B:=1
else If Longueur(NA)<Longueur(NB)
then B:=2
else If Longueur(NA)=Longueur(NB)
then begin
NA:=Miroir(NA);
NB:=Miroir(NB);
While (premier(NA)=premier(NB))
and (not Liste_est_vide(NA)) do Begin
NA:=Reste(NA);
NB:=Reste(NB);
End;
If (Liste_est_vide(NA) and Liste_est_vide(NB))
then B:=0
else If ord(premier(NA)) > ord(premier(NB))
then B:=1
else If ord(premier(NA)) < ord(premier(NB))
then B:=2
end;
Test_A_plus_grand_que_B:=B;
End;
Plus compliqué qu'avec les tableaux, et plus lent oui, mais les inconvénients ont des fois des avantages. Ci-après, une fonction qui extrait p éléments de la liste N, ça peut servir des fois :
Function XTRACT (N : Liste; P : Integer) : Liste;
Var
RES: Liste;
Begin
RES := Init;
N := Miroir(N);
While not(Liste_est_vide(N)) and (P>0) do Begin
RES := Cons(Premier(N), RES);
N := Reste(N);
P := P-1;
End;
XTRACT:=RES;
End;
Après ces quelques amusements, le gros du boulot, l'addition de deux listes, ici c'est très simple et clair, grâce aux listes. En deux mots, la procédure principale reçoit les deux listes NA et NB, teste la nullité, dans le cas contraire additionne NA et NB dans NC, et quand une des deux listes est vide, envoie le traitement à la procédure imbriquée fin_d_add, qui finit le boulot, mais regardez plutôt :
Function Addition (NA, NB : liste) : liste;
Var
NC : Liste;
retenue : Integer;
a,b : Integer;
Procedure fin_d_add(var ND:liste);
Begin
While not (liste_est_vide(ND)) do Begin
NC := cons(chr( ((ord(premier(ND))+retenue-zero) mod 10)+zero),NC);
retenue := (ord(premier(ND))+retenue-zero) div 10;
ND:=reste(ND);
End
End;
Begin
If Liste_est_vide(NA) then NA:=cons('0',NA);
If Liste_est_vide(NB) then NB:=cons('0',NB);
NC :=init;
retenue :=0;
While not ((Liste_est_vide(NA)) and (Liste_est_vide(NB))) do
If ((Liste_est_vide(NA)) and (not(Liste_est_vide(NB))))
then fin_d_add(NB)
Else If ((Liste_est_vide(NB)) and (not(Liste_est_vide(NA))))
then fin_d_add(NA)
Else Begin
A := ord(premier(NA))-zero;
B := ord(premier(NB))-zero;
NC := cons( chr( ( (a+b+retenue) mod 10)+zero), NC);
retenue := ( (a+b+retenue) div 10 );
NA := reste(NA);
NB := reste(NB);
End;
If retenue<>0 then NC := cons(chr(retenue+zero),NC);
Addition:=Miroir(NC);
End;
C'est quand même plus simple que les tableaux non ? Du moins c'est plus clair. Continuons dans le concret, voici la différence de deux listes. Pour simplifier la lecture, on en a fait 3 procédures imbriquées, la première principale, cherche la plus grande, car la différence est positive toujours, et traite la nullité. Après, elle appelle SOUSTRACT, qui fait la soustraction de cellule à cellule jusqu'à ce que une des deux listes soit vide, et c'est la procédure FIN_D_SOUS qui finit le boulot. Admirez :
Function SOUSTRACTION (NA, NB : liste) : liste;
Function SOUSTRACT (NA, NB : liste) : liste;
Var
NC : Liste;
Retenue : Integer;
a,b,ret : Integer;
(********** Fin de la soustraction quand liste vide **********)
Procedure FIN_D_SOUS(Var ND: liste);
Var
C: Integer;
Begin
While not (liste_est_vide(ND)) do Begin
RET :=0;
C :=ord(premier(ND))-zero;
if C<retenue then Begin
C:=C+10;
Ret:=1;
End;
NC :=cons(chr(c-retenue+zero),NC);
retenue :=ret;
ND :=reste(ND);
End
End;
(* Fin de FIN_D_SOUS *)
(* debut de SOUSTRACT *)
Begin
NC :=Init;
Retenue :=0;
A :=0;
B :=0;
While not ((liste_est_vide(NA)) and (liste_est_vide(NB))) do
if liste_est_vide(NB)
then FIN_D_SOUS(NA)
else Begin
A := ord(premier(NA))-zero;
B := ord(premier(NB))-zero;
ret := 0;
If A<(B+retenue) then Begin
A := A+10;
RET := 1;
End;
NC :=cons(chr(a-(b+retenue)+zero),NC);
retenue :=ret;
NA :=Reste(NA);
NB :=Reste(NB);
End;
Soustract:=Miroir(NC);
End;
(* Fin de SOUSTRACT *)
Var
T : Integer;
Begin
T := Test_A_Plus_Grand_Que_B(NA,NB);
If T=0
then Soustraction:=cons('0',nil)
Else If T=1
then Soustraction:=Soustract(NA,NB)
Else If T=2
then Soustraction:=Soustract(NB,NA);
End;
Puisque nous voilà lancés, maintenant voyons la multiplication d'une liste par une constante, chose fort peu aisée, et on remarque ici un retournement du résultat de l'opération :
Function MultC (L1 : Liste; d : integer) : Liste;
Var
Multiplic : Liste;
Retenue : Integer;
Begin
If (d<>0) then Begin
Multiplic:=init;
Retenue:=0;
While not (Liste_est_vide(L1)) do Begin
Multiplic := cons( chr((((ord(premier(L1zero)*d+retenue)
mod 10)+zero), Multiplic);
Retenue := ((Ord(premier(L1))-zero)*d+Retenue) div 10;
L1 := Reste(L1);
End;
If (Retenue<>0)
then Multiplic:=cons( chr (retenue+zero), multiplic);
MultC:=Miroir(Multiplic);
End
Else MultC := cons('0',Nil);
End;
Voici ensuite la multiplication généralisée de deux listes, qui utilise la procédure précédente, et renvoie le tout dans une liste. On procède en prenant le dernier de la plus petite liste, que l'on multiplie par l'autre liste, on met ça dans L_partielle, puis ce nombre étant stocké à l'envers par convention, pour le rajouter à L_totale, il suffit de lui rajouter autant de zéros que son rang :
Function Multiplication (N1, N2 : Liste) : Liste;
Function Multiplicat (L1, L2 : Liste) : Liste;
Var
L_totale : Liste;
L_partielle : Liste;
I : Integer;
N : Integer;
Puiss : Integer;
Begin
L_Totale :=Init;
L_partielle :=Init;
Puiss :=1;
For I := 1 to Longueur (L2) do Begin
L_partielle := (MultC(L1,( ord(premier(L2))) - zero));
For N:=1 to (Puiss-1) do Begin
L_partielle:=Cons('0',L_partielle);
End;
Puiss := Puiss+1;
L_totale := Addition(L_totale,L_partielle);
L2 := Reste(L2);
End;
Multiplicat:=L_Totale;
End;
Begin
If longueur(N1)<Longueur(N2)
then Multiplication:=Multiplicat(N2,N1)
Else Multiplication:=Multiplicat(N1,N2);
End;
Ici plus bêtement, on multiplie p fois N par 10 pour le mettre à la puissance p voulue :
Function PUISS_10 (N : Liste; NB_ZEROS : Integer) : Liste;
Var
I : Integer;
Begin
For I:=NB_Zeros Downto 0 do
N:=Multiplication (N,Cons('1',Cons('0',nil)));
Puiss_10:=N;
End;
Ca c'était le digestif avant le second plat de résistance : la division. Essayez donc de comprendre tout seul, la mise en page me fait damner...
Function DIVISION (NA,NB:liste; Var RESTE: Liste):liste;
Function Divis (N1,N2: Liste; RESULT : Liste; Var RESTE: Liste) : Liste;
Begin
If TEST_A_PLUS_GRAND_QUE_B (Xtract(N1,LONGUEUR(N2)),N2)=2 then
If TEST_A_PLUS_GRAND_QUE_B (Xtract(N1,LONGUEUR(N2)+1),N2)=2 then
Begin
Divis:=Miroir(Result);
Reste:=N1;
End
Else Divis:=Divis(
Soustraction(N1,
Puiss_10(N2,
Longueur(N1)-Longueur(N2)-1)
),
N2,
Miroir(Addition(miroir(Result),
Cons('1',nil))), reste)
Else Divis:=Divis (
Soustraction(N1,
Puiss_10(N2,
Longueur(N1)-Longueur(N2))
),
N2,
Miroir(Addition(Miroir(Result),
Cons('1',nil))), reste)
End;
Begin
if TEST_A_PLUS_GRAND_QUE_B(NA,NB) = 1
then Division := Divis(NA, NB, NIL, reste)
else If TEST_A_PLUS_GRAND_QUE_B(NA,NB) = 2
then Division := Divis(NB, NA, NIL, reste)
else Division := NIL
End;
Vous venez d'admirer un grand moment de récurrence de listes, de rappels de fonctions. Ca serait vraiment très long à schématiser pour vous expliquer, mais je garde un grand espoir de vous faire un jour un cours de numération. Et pour finir, le modulo de A par B, du gâteau :
Function MODULO(NA, NB : Liste) : Liste; Var DIVI, RESTE : Liste; Begin Divi := init; Reste := init; Divi := Division(NA,NB,RESTE); Modulo := reste; End;
Pour aller plus loin ... je signale qu'il existe une fonction pré-existante en C utilisable par LIST.H, et qui dans le même genre definit des arbres binaires... Si cela vous intéresse, je vous en parlerai. Sachez seulement qu'un arbre binaire est une cellule qui pointe sur deux autres cellules et ainsi de suite, ce qui en le représentant sur du papier donne une sorte d'arbre.
Autre chose, si vous faites un travail à base de suites de Fibonnacci, contactez moi, j'ai un rapport de 40 pages au moins et des programmes à ce sujet.
Et si cela vous intéresse, je pourrais vous taper tout le cours de niveau IUT, BTS et 1e année de supérieure, mais plebiscitez moi...
A.Lofficier, la diligente bonne fée de notre école, qui aide de son mieux ceux qui sont en difficulté, et qui me force à "produire du sens". et comme envoi, A celle qui ...