1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
#!/usr/bin/instantfpc
//program polynome;
{$mode objfpc}{$H+}
type
p_monome = ^monome;
monome = record
coef : Integer;
deg : Integer;
suiv : p_monome;
end;
// Création d'un monome
function CreerMonome(C: Integer; D: Integer): p_monome;
begin
new(Result);
Result^.coef := C;
Result^.deg := D;
Result^.suiv := Nil;
End;
// Création d'un monome à partir d'un autre, sans reprendre le monome suivant.
function CopieMonome(m: p_monome): p_monome;
begin
new(Result);
Result^ := m^;
Result^.suiv := Nil;
End;
// Création d'un polynome à partir d'un tableau de coef (utile pour les tests)
// les coef sont triés selon l'ordre croissant des
function Tab2Poly(T: array of Integer): p_monome;
var
i : Integer;
// astuce: son suivant pointera sur la liste à créer, c'est une variable locale,
// l'allocation/désallocation sont réalisée par la gestion auto. de la pile.
// Cette solution sera reprise dans d'autres routines
teteProv: monome; // tête provisoire !
p: p_monome;
begin
teteProv.suiv := Nil; // précaution sans doute exagérée.
p := @teteProv;
for i := low(T) to high(T) do
begin
if T[i] <> 0 then
begin
p^.suiv := CreerMonome(T[i], low(T)+high(T) - i);
p := p^.suiv;
end;
end;
Result := teteProv.suiv; // premier monome effectif
End;
// Copie du monome paramètre et de ses suivants
// C'est la version polynome de CopieMonome
function CopiePoly(m: p_monome): p_monome;
var
teteProv: monome;
cour: p_monome;
begin
teteProv.suiv := Nil;
cour := @teteProv;
while (m <> Nil) do
begin
cour^.suiv := CopieMonome(m);
cour := cour^.suiv;
m := m^.suiv;
end;
Result := teteProv.suiv;
End;
procedure DetruitPoly(var P: p_monome);
var
t: p_monome;
begin
while (P <> Nil) do
begin
t := P^.suiv;
Dispose(P);
P := t;
end;
end;
// Addition, algo linéaire, dérivé de l'algo de fusion de liste
// Traite tous les monomes de P et Q, qu'ils aient le même degré ou non.
// L'inconvéninet est que la forme s'éloigne un peu de l'algorithme mathématique
function Addition(P,Q: p_monome): p_monome;
var
teteProv: monome;
cour: p_monome;
begin
teteProv.suiv := Nil;
cour := @teteProv;
while true do
begin
if (P = Nil) and (Q = Nil) then
begin
// plus de monome à traiter ni dans P ni dans Q
break;
end
else if (P = Nil) then
begin
// plus de monome dans P, on prend ce qui reste dans Q
cour^.suiv := CopiePoly(Q);
end
else if (Q = Nil) then
begin
// plus de monome dans Q, on prend ce qui reste dans P
cour^.suiv := CopiePoly(P);
end
else if (P^.deg > Q^.deg) then
begin
cour^.suiv := CopieMonome(P);
cour := cour^.suiv;
P := P^.suiv;
end
else if (P^.deg < Q^.deg) then
begin
cour^.suiv := CopieMonome(Q);
cour := cour^.suiv;
Q := Q^.suiv;
end
else // égalité de degré
begin
cour^.suiv := CopieMonome(P);
cour := cour^.suiv;
cour^.coef := cour^.coef + Q^.coef;
P := P^.suiv;
Q := Q^.suiv;
end;
end;
result := teteProv.suiv;
End;
procedure WritePoly(intro: String; p: p_monome);
begin
if p = Nil then
begin
writeLn(Intro, 'Polynome vide !!!');
end
else
begin
write(Intro);
while true do
begin
write(p^.coef, '.X^', p^.deg);
p := p^.suiv;
if (p = Nil) then
begin
writeLn;
break;
end
else
begin
write(' + ');
end;
end;
end;
End;
var
P,Q,S: p_monome;
begin
try
// Nil !!
WritePoly('Nil = ', Nil); writeLn;
// (X^2 + X + 1)
P := Tab2Poly([1,1,1]);
WritePoly('P = ', P); writeLn;
// (X^3+X+1)
Q := Tab2Poly([1,0,1,1]);
WritePoly('Q = ', Q); writeLn;
// Somme (X^3+X^2+2.X+2)
S := Addition(P,Q);
WritePoly('P+Q = ', S); writeLn;
finally
DetruitPoly(S);
DetruitPoly(Q);
DetruitPoly(P);
end;
End. |
Multiplication de deux polynômes avec liste chaînée
Répondre avec citation
Partager