Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

NWD - algorytm Euklidesa

SPIS TREŚCI
Podrozdziały

Problem

Dla danych dwóch liczb naturalnych a  i b  należy znaleźć największą liczbę naturalną c, która dzieli bez reszty liczbę a  i dzieli bez reszty liczbę b.


Liczba c  o powyższej własności nosi nazwę NWD – największego wspólnego dzielnika a  i b ( ang. GCD – greatest common divisor ). NWD znajdujemy za pomocą znanego algorytmu Euklidesa, będącego jednym z najstarszych algorytmów, ponieważ pojawił się on w dziele Elementy  napisanym przez Euklidesa około 300 p.n.e. Właściwie Euklides nie podał algorytmu dla liczb, lecz dla dwóch odcinków. Chodziło w nim o znalezienie wspólnej miary ( czyli odcinka jednostkowego ), która mogłaby posłużyć do zmierzenia obu danych odcinków – wspólna miara odkłada się w każdym z odcinków całkowitą liczbę razy.

Rozwiązanie 1

Euklides wykorzystał prosty fakt, iż NWD liczb a  i b  dzieli również ich różnicę. Zatem od większej liczby odejmujemy w pętli mniejszą dotąd, aż obie liczby się zrównają. Wynik to NWD dwóch wyjściowych liczb.

Algorytm Euklidesa

Wejście:

a, b  liczby naturalne, których NWD poszukujemy, a, b  ∈ N.

Wyjście:

NWD liczb a  i b.

Lista kroków:

 K01: Dopóki a  ≠ b,
wykonuj
krok K02
 
K02:     Jeśli a  < b,
    to b  ← b  - a
    inaczej a  ← a  - b
od większej liczby odejmujemy mniejszą aż się zrównają 
K03: Pisz a wtedy dowolna z nich jest NWD
K04: Zakończ  

Przykładowe programy

 Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje z pierwszego wiersza dwie liczby a  i b, a następnie wypisuje w następnym wierszu ich NWD. Żadna z liczb a  i b nie może wynosić 0 – wtedy różnica nie zmienia większej z nich i program działa w nieskończoność. Niedogodność tę da się prosto zlikwidować – proponuję to jako ćwiczenie dla czytelników.
Pascal
// NWD - wersja z odejmowaniem
// Data   : 12.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program prg;

var a, b : cardinal;

begin
  readln ( a, b );
  while a <> b do
    if a < b then b := b - a
    else          a := a - b;
  writeln ( a );
end.
C++
// NWD - wersja z odejmowaniem
// Data   : 12.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main( )
{
  unsigned int a, b;

  cin >> a >> b;
  while( a != b )
    if( a < b ) b -= a; else a -= b;
  cout << a << endl;
  return 0;
}
Basic
' NWD - wersja z odejmowaniem
' Data   : 12.03.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger a, b

Input a, b
While a <> b
  If a < b Then b -= a: Else: a -= b
Wend
Print a
End
Wynik:
18 24
6
Algorytm Euklidesa
(C)2020 mgr Jerzy Wałaszek

a =
b =


...

Na początek:  podrozdziału   strony 

Rozwiązanie 2

Pierwsze rozwiązanie problemu znajdowania NWD jest złe z punktu widzenia efektywności. Wyobraźmy sobie, iż a jest równe 4 miliardy, a b  jest równe 2. Pętla odejmująca będzie wykonywana dotąd, aż zmienna a  zrówna się ze zmienną b, czyli w tym przypadku 2 miliardy razy – trochę dużo. Tymczasem można wykorzystać operację reszty z dzielenia. Mniejszą liczbę można odjąć od większej liczby tyle razy, ile wynosi iloraz całkowity tych liczb. Po odejmowaniu pozostaje reszta z dzielenia – a Euklides właśnie zauważył, iż NWD dzieli również różnicę danych liczb, czyli:

NWD ( a, b  ) = NWD ( a  mod b, b  )

Ponieważ reszta zawsze jest mniejsza od dzielnika, wymieniamy a  z b, b  z a  mod b. Jeśli otrzymamy wynik b  = 0, to w a  jest ostatni dzielnik dzielący bez reszty różnicę.

Algorytm Euklidesa

Wejście:

a, b – liczby naturalne, których NWD poszukujemy, a, b ∈ N.

Wyjście:

NWD liczb a  i b.

Zmienne pomocnicze:

t  – tymczasowo przechowuje dzielnik, t ∈ N.

Lista kroków:

K01: Dopóki b  ≠ 0,
wykonuj kroki K02...K04
 
K02:     t  ← b zapamiętujemy dzielnik
K03:     b  ← a  mod b wyznaczamy resztę z dzielenia, która staje się dzielnikiem
K04:     a  ← t poprzedni dzielnik staje teraz się dzielną
K05: Pisz a NWD jest ostatnią dzielną
K06: Zakończ  

Przykładowe programy

 Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje z pierwszego wiersza dwie liczby a  i b, a następnie wypisuje w następnym wierszu ich NWD.
Pascal
// NWD - wersja z resztą z dzielenia
// Data   : 12.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program prg;

var a, b, t : cardinal;

begin
  readln ( a, b );
  while b <> 0 do
  begin
    t := b;
    b := a mod b;
    a := t;
  end; 
  writeln ( a );
end.
C++
// NWD - wersja z resztą z dzielenia
// Data   : 12.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main( )
{
  unsigned int a, b, t;

  cin >> a >> b;
  while( b )
  {
    t = b;
    b = a % b;
    a = t;
  } 
  cout << a << endl;
  return 0;
}
Basic
' NWD - wersja z resztą z dzielenia
' Data   : 12.03.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger a, b, t

Input a, b
While b
  t = b
  b = a Mod b
  a = t
Wend
Print a
End
Na początek:  podrozdziału   strony 

Rozwiązanie 3

Istnieje algorytm znajdowania NWD, w którym nie wykonuje się dzieleń – są one kłopotliwe dla małych procesorów, np. dla kontrolerów jednoukładowych, i zajmują stosunkowo dużo czasu procesora. Algorytm ten wykorzystuje fakt, iż wszystkie liczby są przechowywane w komputerze w postaci ciągu bitów. Operacje dzielenia z resztą zastępuje się przesunięciami bitów, które są proste w realizacji i wykonywane szybko, nawet na najprostszym sprzęcie komputerowym. W efekcie otrzymujemy około 60% przyrost szybkości wyznaczania NWD w stosunku do standardowego algorytmu Euklidesa. Opisywany algorytm nosi nazwę binarnego algorytmu NWD ( ang. binary GCD algorithm ).

Algorytm redukuje problem znajdowania NWD przez stosowanie poniższych równoważności:

  1. NWD ( 0, b  ) = b, ponieważ każda liczba naturalna dzieli zero, a b  jest największą liczbą dzielącą b. Podobnie NWD ( a, 0 ) = a. Natomiast NWD ( 0, 0 ) nie jest zdefiniowane.
  2. Jeśli liczby a  i b  są parzyste, to NWD ( a, b  ) = 2 × NWD ( a / 2, b / 2 ), ponieważ obie posiadają wspólny podzielnik 2.
  3. Jeśli liczba a  jest parzysta a b  jest nieparzysta, to NWD ( a, b  ) = NWD ( a / 2, b  ), ponieważ 2 nie jest wspólnym podzielnikiem i można go pominąć. Podobnie jest w przypadku odwrotnym, gdy a  jest nieparzyste a b  jest parzyste, wtedy NWD ( a, b  ) = NWD ( a, b / 2 ).
  4. Jeśli obie liczby a  i b  są nieparzyste i a  ≥ b, to NWD ( a, b  ) = NWD ( ( a b  ) / 2, b  ), inaczej jeśli obie są nieparzyste i  a  < b, to NWD ( a, b  ) = NWD ( ( b - a  ) / 2, a  ). Takie same operacje wykonuje w pętli podstawowy algorytm Euklidesa – od większej liczby odejmuje mniejszą. Podzielenie różnicy przez 2 daje zawsze liczbę całkowitą, ponieważ odejmowane są dwie liczby nieparzyste.
  5. Kroki 3 i 4 należy powtarzać aż do otrzymania b = 0. Wtedy NWD jest równy 2 k × a, gdzie k  jest liczbą wspólnych czynników 2 wyeliminowanych w kroku 2. Mnożenie 2 k wykonujemy przez przesunięcie bitów zmiennej a  o k  pozycji w lewo.

Algorytm Euklidesa

Wejście:

a, b – liczby naturalne, których NWD poszukujemy, a, b ∈ Z.

Wyjście:

NWD liczb a  i b.

Zmienne pomocnicze:

k  – przechowuje liczbę wspólnych podzielników 2, k ∈ Z.
r
  – wykorzystywane do przechowywania różnicy a  i b, r  ∈ Z.

Lista kroków:

K01: Jeśli a  = 0,
to pisz b i zakończ
NWD ( 0, b ) = b
K02: Jeśli b  = 0,
to pisz a i zakończ
NWD ( a, 0 ) = a
K03: k  ← 0 inicjujemy liczbę wspólnych podzielników 2
K04: Dopóki a  i b  są parzyste,
wykonuj
kroki K05...K07
usuwamy z a i b wspólne czynniki 2, zapamiętując ich liczbę w k
K05:     a  ← a  shr 1 przesuwamy bity a o 1 w prawo
K06:     b  ← b  shr 1 przesuwamy bity b o 1 w prawo
K07:     k  ← k  + 1  
K08: Jeśli a  = 0,
to a  ← b
i idź do kroku K18
NWD ( 0, b ) = b
K09: Dopóki a  jest parzyste,
wykonuj
a  ← a  shr 1
eliminujemy podzielniki 2 z a
K10: Dopóki b  jest parzyste,
wykonuj
b  ← b  shr 1
eliminujemy podzielniki 2 z b, teraz a i b są nieparzyste
K11: Jeśli a  ≥ b,
to idź do kroku K16
 
K12: r  ← ( b  - a  ) shr 1 NWD ( a, b ) = NWD ( ( b-a )/2, a )
K13: b  ← a zamieniamy b z a
K14: a  ← r a z różnicą r
K15: Idź do kroku K17  
K16: a  ← ( a  - b  ) shr 1 NWD ( a, b ) = NWD ( ( a-b )/2, b )
K17: Jeśli b  ≠ 0,
to idź do kroku K08
 
K18: Jeśli k  > 0,
to a  ← a  shl k
przesuwamy bity a o k pozycji w lewo mnożenie przez 2 k
K19: Pisz a  
K20: Zakończ  

Przykładowe programy

 Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje z pierwszego wiersza dwie liczby a  i b, a następnie wypisuje w następnym wierszu ich NWD.
Pascal
// NWD - wersja binarna z przesuwem bitów
// Data   : 13.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program prg;

var a, b, k, r : cardinal;

begin
  readln ( a, b );
  if( a = 0 ) or ( b = 0 ) then writeln ( a or b )
  else
  begin
    k := 0;
    while( ( a or b ) and 1 ) = 0 do
    begin
      a := a shr 1;
      b := b shr 1;
      inc ( k );
    end;
    repeat
      if a = 0 then
      begin
        a := b;
        break;
      end;
      while( a and 1 ) = 0 do a := a shr 1;
      while( b and 1 ) = 0 do b := b shr 1;
      if a < b then
      begin
        r := ( b - a ) shr 1;
        b := a;
        a := r;
      end
      else a := ( a - b ) shr 1;
    until b = 0;
    if k > 0 then a := a shl k;
    writeln ( a );
  end;
end.
C++
// NWD - wersja binarna z przesuwem bitów
// Data   : 14.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main( )
{
  unsigned int a, b, k, r;

  cin >> a >> b;
  if( !a || !b ) cout << ( a | b ) << endl;
  else
  {
    for( k = 0; ! ( ( a | b ) & 1 ); k++ )
    {
      a >>= 1;
      b >>= 1;
    }
    do
    {
      if( !a )
      {
        a = b; break;
      }
      while( ! ( a & 1 ) ) a >>= 1;
      while( ! ( b & 1 ) ) b >>= 1;
      if( a < b )
      {
        r = ( b - a ) >> 1;
        b = a;
        a = r;
      }
      else a = ( a - b ) >> 1;
    } while( b );
    if( k ) a <<= k;
    cout << a << endl;
  }
  return 0;
}
Basic
' NWD - wersja binarna z przesuwem bitów
' Data   : 13.03.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger a, b, k, r

Input a, b
if( a = 0 ) Or ( b = 0 ) Then
    Print a Or b
Else
  k = 0
  while( ( a Or b ) And 1 ) = 0
    a = a Shr 1
    b = b Shr 1
    k += 1
  Wend
  Do
    If a = 0 Then
      a = b
      Exit Do
    End If
    while( a And 1 ) = 0: a = a Shr 1: Wend
    while( b And 1 ) = 0: b = b Shr 1: Wend
    If a < b Then
      r = ( b - a ) Shr 1
      b = a
      a = r
    Else
      a = ( a - b ) Shr 1
    End If
  Loop Until b = 0
  If k > 0 Then a = a Shl k
  Print a
End If
End
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.