Algorytm Euklidesa

Z RNO-Wiki


Algorytm Euklidesa służy do znajdowania największego wspólnego dzielnika dwóch liczb całkowitych a, b. Bazuje on na obserwacji

<math>\gcd(a,b) = \gcd(b, a-b) = \gcd(b,a-2b) = \ldots = \gcd(b, a \mod b)</math>

Spis treści

Opis algorytmu (w pseudokodzie)

     Euklides(a,b)
        1. Jeśli b = 0, to
               o wynik algorytmu to a
               o KONIEC 
        2. w przeciwnym wypadku wykonaj:
               o c := a mod b
               o a := b
               o b := c 
        3. idź do kroku nr 1

Implementacja w języku C/C++

Funkcja iteracyjna

  int gcd(int a, int b)
  {
     int mem;
     if (a<b) swap(a,b); // zamienia a <--> b
     while (b!=0)
     {
        mem = b;
        b = a%b
        a = mem;
     }
     return a;

Funkcja rekurencyjna

  int gcd(int a, int b) // funkcja rekurencyjna
  {
     // if (a<b) return gcd(b,a); <--- to nie jest potrzebne, dlaczego?
     if (b==0) return a;
     return gcd(b,a%b);
  }


Zobacz także rozszerzony algorytm Euklidesa

Osobiste