Plus grand commun diviseur Pascal (plus de 2 valeurs)

Question

Comment trouver GCD s'il y a plus de 2 valeurs dans le tableau?

Je pensais trouver la plus petite valeur, et essayer de diviser chaque élément de la matrice par elle et si mod n'est pas 0 alors enlever 1 de cette valeur et recommencer.

Mais je ne reçois que 0 alors c'est la mauvaise façon, des idées?

program GreatestCommonDivisor; 
type mas = array[1..100] of integer; 
var n : integer; 
M : mas; 
Rf : text; 

procedure Skaityti; 
var i : integer; 
Df : text; 
begin 
Assign(Df,'duom1.txt'); 
Reset(Df); 
Readln(Df,n); 

for i := 1 to n do 
    Read(Df,M[i]); 
Close(Df); 
end; 
function GCD(M : array of integer): integer; 
    var i,min : integer; 
    begin 
    min := M[1]; 
    for i := 1 to n do 
    begin 
     if min > M[i] then 
      min := M[i]; 
    end; 
     i := 1; 
    repeat 
     if M[i] mod min = 0 then 
      GCD := min 
     else 
     begin 
      min := min - 1 ; 
      i := 0; 
      continue; 
     end; 
     i := i + 1; 
    until i = n; 
    end; 
var min,i : integer; 
begin 
    Skaityti; 
Assign(Rf,'rez.txt'); 
for i := 1 to n do 
Writeln(Rf,GCD(M),' ',min); 

Close(Rf); 

end. 

Answer 1

Je ne sais pas ce que votre entrée est, mais voici où je pense que vous avez la faille dans votre raisonnement:

D'abord, vous essayez de trouver le plus petit élément que votre GCD potentiel. Hypothèse raisonnable, le gcd ne peut pas être plus grand que cela bien sûr. Cependant, alors vous bouclez votre liste et si le gcd supposé ne se divise pas uniformément, vous le réduisez d'une unité et continuez. Cela ne marchera pas.

Start = 10, 9, 8; min = 8; gcd is undefined (defaults to 0) 
10 mod 8 is not 0, so min = 7 
9 mod 7 is not 0, so min = 6 
8 mode 6 is not 0, so min = 5 
Done, gcd is now 0 

Start = 10, 9, 8, 5, min = 5, gcd is undefined (defaults to 0) 
10 mod 5 is 0, so gcd = 5 
9 mod 5 is not 0, so min = 4 
8 mod 4 is 0, so gcd = 4 
5 mod 4 is not 0 so min = 3 
Done, gcd is now 4 

Voici un programme qui calcule GCD (inefficacement)

Program ShowGCD(output); 
type 
    arr = array of integer; 
var 
    M: arr; 

function GCD(M: arr): integer; 
    var i,min : integer; 
begin 
    min := M[0]; 
    for i := 1 to Length(M)-1 do begin 
     if min > M[i] then 
      min := M[i]; 
     end; 
    i := 1; 
    repeat 
     if M[i] mod min = 0 then 
      GCD := min 
     else 
      begin 
       min := min - 1; 
       i := 0; 
       continue; 
      end; 
     i := i + 1; 
    until i = Length(M); 
end; 

begin 
    M:=arr.Create(15, 45, 25); 
    writeln('GCD: ', GCD(M)); 
end.