: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > działania na liczbach >

N W D   O R A Z   N W W

 

0 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 29 30

 
       

Największego wspólnego dzielnika liczb a i b podobnie jak w przypadku rozkładu można szukać maksymalnie do wartości Sqrt(Min(a, b)) pod warunkiem wcześniejszego sprawdzenia czy mniejsza z tych liczb nie dzieli przypadkiem liczby większej z nich, np. (a=5 i b=5) lub (a=7 i b=21).
Ponieważ szukamy największego z dzielników więc rozsądnym pomysłem jest przeszukiwanie w dół, od wartości maksymalnej do najmniejszej możliwej, czyli 1:

Function Nwd(A, B : LongInt) : LongInt;
Var
  I, Max : LongInt;
Begin
  If A<B Then
    Begin
      Max:=A;
      A:=B;
      B:=Max;
    End;
  If (A Mod B)=0 Then Nwd:=B
  Else
    Begin
      I:=Round(Sqrt(B));
      While (I>1) And (((A Mod I)<>0) Or ((B Mod I)<>0)) Do Dec(I);
      Nwd:=I;
    End;
End;

Pierwsza instrukcja If ustawia liczby A i B w taki sposób, aby A>=B.
Największy wspólny dzielnik jest liczbą, która oprócz podzielności liczb A i B dzieli również liczbę A-B, co może znacznie przyspieszyć wyznaczanie NWD w przypadku dużych liczb o niewielkiej różnicy. Jeśli liczby A i B są uporządkowane w taki sposób, że A>=B, to po instrukcji przypisania można dodać warunek:

I:=Round(Sqrt(B));
If A-B<I Then I:=A-B;

Inna metoda wyznaczania NWD polega na dzieleniu większej z liczb przez kolejne reszty: zakładając, że A>=B wyznaczamy resztę R1 z dzielenia A przez B, następnie wyznaczamy resztę R2 z dzielenia liczby B przez R1, następnie resztę R3 z dzielenia liczby R1 przez R2, resztę R4 z dzielenia R2 przez R3, itd. aż do wyznaczenia takiej reszty Rn z dzielenia liczby Rn-2 przez Rn-1, która jest równa zero. Wówczas przedostatnia otrzymana reszta, tj. Rn-1 jest równa NWD(A, B).
Dla A=220 i B=132 wyglądałoby to następująco:

 R:=220 Mod 132; {R=88}
 A:=132;
 B:=88;
 R:=A Mod B;     {R=44}
 A:=88;
 B:=44;
 R:=A Mod B;     {R=0, NWD=B=44}

Widać w powyższym schemacie, że wystarczy po wykonaniu każdego dzielenia podmienić wartości liczb A i B:

Function Nwd(A, B : LongInt) : LongInt;
Var
  R, Max : LongInt;
Begin
  If A<B Then
    Begin
      Max:=A;
      A:=B;
      B:=Max;
    End;
  R:=A Mod B;
  While R<>0 Do
    Begin
      A:=B;
      B:=R;
      R:=A Mod B;
    End;
  Nwd:=B;
End;

NWW

NWW(A, B)=(A*B) Div NWD(A, B).