Discussion :

[Jerome Briot]

codons l'algorithme de Euclide permettant de déterminer le plus grand commun diviseur entre deux nombres entiers

Le code suivant détermine le plus grand commun diviseur ("greatest common divisor" en anglais) entre une liste d'entiers contenus dans deux tableaux :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
function gcd = findgcd(a,b)
%FINDGCD
%
 
% Author : Jerome Briot (Dut)
% Contact : dutmatlab#yahoo#fr -or- briot#cict#fr
% Profil : www.mathworks.com/matlabcentral/newsreader/author/94805
%        : www.developpez.net/forums/u125006/dut/
%
% Version : 1.0 - 04 Sep 2009
%
 
% MATLAB : 7.6.0.324 (R2008a)
% System : Linux 2.6.24-24-generic
%
 
error(nargchk(2,2,nargin));
 
if ndims(a)~=ndims(b)
    error('A and B must have the same number of dimensions');
end
 
if numel(a)~=numel(b)
    error('A and B must have the same number of elements');
end
 
gcd = ones(size(a))*-1;
idx = (a & b);
gcd(idx) = 2*(~bitget(a(idx),1) & ~bitget(b(idx),1));
 
idx = ~gcd;
 
if ~any(idx)
    return
end
 
gcd(idx) = euclidalgo(a(idx),b(idx));
 
function g = euclidalgo(aa,bb)
 
for n=1:numel(aa)
 
    if aa(n)<bb(n)
        m = bb(n);
        g(n) = aa(n);
    else
        g(n) = bb(n);
        m = aa(n);
    end
 
    r = mod(m,g(n));
    while r>0
        m = g(n);
        g(n) = r;
        r = mod(m,g(n));
    end
end

Voici un fichier démo :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function demofindgcd
%DEMOFINDGCD
%
 
% Author : Jerome Briot (Dut)
% Contact : dutmatlab#yahoo#fr -or- briot#cict#fr
% Profil : www.mathworks.com/matlabcentral/newsreader/author/94805
%        : www.developpez.net/forums/u125006/dut/
%
% Version : 1.0 - 04 Sep 2009
%
 
% MATLAB : 7.6.0.324 (R2008a)
% System : Linux 2.6.24-24-generic
%
 
a = [6 27 8 2 0 1268  462];
b = [35 6 0 4 0 1254 1071];
 
gcd = findgcd(a,b);
 
sprintf('%5d %5d %5d %5d %5d %5d %5d\n',[a;b;gcd].')

Qui renvoie ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
    6    27     8     2     0  1268   462
   35     6     0     4     0  1254  1071
    1     3    -1     2    -1     2    21

La troisième ligne contient le plus grand commun diviseur entre chaque élément de la première ligne et celui de la seconde lui correspondant.

La valeur -1 est retournée si au moins une des deux valeurs est 0.

Voila... si vous avez des remarques, des questions ou des suggestions, n'hésitez pas

Mais rappelez-vous que je ne suis pas un spécialiste dans ce domaine

Note : Ne sachant pas si ces codes sont justes, je ne les ai pas optimisés (et donc pas commentés)