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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
const
Tab1DItemsMax = 1024 shl 13; { 16 Mo max }
type
TTab1DItems = array[0..Tab1DItemsMax-1] of longint;
TTab1D = object
Items : TTab1DItems;
// Elements du tableau
Length: LongInt;
// Taille du tableau
procedure uiRead;
// saisie
procedure uiWrite;
// affichage
procedure Reset;
// remet tout à zéro
procedure Fill(const aValue: LongInt);
// remplis le tableau avec aValue
function Sort: LongInt;
// Trie le tableau et renvois le nombre de permutations éfféctuées
function CountDoublons: LongInt;
// Compte et renvois le nombre de doublons découvert
procedure Clone(var T: TTab1D);
// Clone le tableau dans T
procedure Split(var T: TTab1D; aFrom, aTo: LongInt);
// Coupe et copie une partie du tableau dans T entre les index aFrom et aTo
procedure Merge(T: TTab1D);
// Fusione le tableau avec T
end;
{ Permut (asm)
Echange les valeurs de deux variables LongInt
paramétres :
A : [I/O] LongInt
B : [I/O] LongInt
Retour :
dans A et B, retourne la valeur de A dans B et de B dans A
Note :
permet de gagner 3 instructions par rapport à une permutation standard
performances théoriques :
Permut Standard = f/6
Permut Asm XChg = f/3
}
procedure permut(var A, B:longInt); register;
asm
mov ecx, DWORD PTR [eax]; // ecx = A
xchg ecx, DWORD PTR [edx]; // B = ecx et ecx = B
mov DWORD PTR [eax], ecx; // A = ecx
{
var T: longInt;
begin
T := A;
A := B;
B := T;
this make 6 instructions :
push ebx;
mov ecx, [eax];
mov ebx, [ebx];
mov [edx], ecx;
mov [eax], ebx;
pop ebx;
}
end;
function TTab1D.sort: longint;
var R, I, J: longInt;
begin
R := -1;
if Length <= Tab1DItemsMax then
begin
R := 0;
for I := Length-1 downto 0 do
for J := 0 to Length-2 do
if Items[J] > Items[J+1] then
begin
permut(Items[J], Items[J+1]);
inc(R);
end;
end;
sort := R;
end;
procedure TTab1D.Split(var T: TTab1D; aFrom, aTo: LongInt);
var N: integer;
begin
T.Length := aTo-aFrom;
for N := aFrom to aTo do
T.Items[N-aFrom] := Items[N];
end;
procedure TTab1D.fill(const aValue: LongInt);
var N: LongInt;
begin
for N := 0 to Length-1 do
Items[N] := 0;
end;
procedure TTab1D.Merge(T: TTab1D);
var N: LongInt;
begin
for N := 0 to T.Length - 1 do
Items[Length+N] := T.Items[N];
Length := Length + T.Length;
end;
procedure TTab1D.uiRead;
var i : longint;
begin
repeat
write('Donner la taille du tableau entre 1 et ', Tab1DItemsMax,' : ');
readln(Length);
until (Length >= 1) and (Length <= Tab1DItemsMax);
writeln('Saisissez les éléments du tableau : ');
for i := 0 to Length-1 do
begin
write(' T[', i, '] = ');
readln(Items[i]);
end;
end;
procedure TTab1D.reset;
begin
Length := Tab1DItemsMax;
Fill(0);
Length := 0;
end;
procedure TTab1D.uiWrite;
var N: LongInt;
begin
writeln('');
write('(',Length,')[');
for N := 0 to Length-1 do
begin
write(Items[N]);
if N < (Length-1) then
write(', ');
end;
writeln(']');
end;
procedure TTab1D.clone(var T: TTab1D);
var N: integer;
begin
for N := 0 to Length - 1 do
T.Items[N] := Items[N];
T.Length := Length;
end;
function TTab1D.countDoublons: longint;
var N, M, R:longint;
T : TTab1D;
begin
R := 0;
clone(T);
T.sort;
// verification des doublons
R := 0;
N := 0;
while N < T.Length do
begin
M := N+1;
while (M < T.Length) and (T.Items[N] = T.Items[M]) do
begin
inc(R);
inc(M);
end;
N := M;
end;
countDoublons := R;
end;
var
Tab : TTab1D;
begin
Tab.Reset;
Tab.uiRead;
Tab.uiWrite;
Tab.Sort;
Tab.uiWrite;
writeln('Nombres de doublons : ', Tab.CountDoublons);
readln;
end. |
