Algorytm Euklidesa

Z RNO-Wiki
(Różnice między wersjami)
m (Wycofano edycję użytkownika Pranavwright (dyskusja). Autor przywróconej wersji to Rno.)
Linia 49: Linia 49:
 
== Zobacz także ==
 
== Zobacz także ==
 
# [[rozszerzony algorytm Euklidesa]]
 
# [[rozszerzony algorytm Euklidesa]]
 
[http://cvresumewritingservices.org/ Resume]
 

Wersja z 21:05, 21 cze 2011

Algorytm Euklidesa służy do znajdowania największego wspólnego dzielnika dwóch liczb całkowitych a, b. Bazuje 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

Schemat blokowy algorytmu

Euklides.png

Implementacja w języku C/C++

Funkcja iteracyjna

int gcd(int a, int b)
{
     int mem;
     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

  1. rozszerzony algorytm Euklidesa
Osobiste