Algorytm Euklidesa

Z RNO-Wiki
(Różnice między wersjami)
m (1 wersji)
Linia 1: Linia 1:
 +
[[Kategoria:Algorytmy]]
 +
 
Algorytm Euklidesa służy do znajdowania największego wspólnego dzielnika dwóch liczb całkowitych a, b.
 
Algorytm Euklidesa służy do znajdowania największego wspólnego dzielnika dwóch liczb całkowitych a, b.
 
Bazuje on na obserwacji
 
Bazuje on na obserwacji

Wersja z 10:35, 1 gru 2007


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