Algorytm Euklidesa

Algorytm Euklidesa został wymyślony przez Eudoksosa z Knidos jeszcze przed naszą erą, aczkolwiek dopiero Euklides spisał go w swoim dziele "Elementy" (gr. Stoicheia geometrias) i stąd pochodzi jego nazwa. Dzięki niemu możemy obliczyć NWD (największy wspólny dzielnik) dwóch liczb naturalnych różnych od siebie, dzięki czemu można np. stwierdzić, czy dane dwie liczby są względnie pierwsze. Algorytm jest dość szybki, wykonuje on maksymalnie 2*log(a+b) operacji, podczas gdy dobrze napisany brut wykonuje max b^2 operacji, gdzie b to mniejsza z dwóch liczb.

Algorytm

(1)

\begin{align} a, b \in \mathbb{N} \end{align}

(2)

\begin{align} NWD(a,b)= \begin{cases} a & \ dla \ b = 0 \\ NWD(b, a\bmod{b}) & \ dla \ b > 0 \end{cases} \end{align}

Implementacja (C++)

Funkcja

int NWD(int a, int b) {
  if(b)
    return NWD(b, a%b);
 
  return a;
}

Przykład zastosowania

Input

248 128

Wprowadzone zostają dwie liczby.

Output

8

Wynikiem jest jedna liczba - największy wspólny dzielnik dwóch wprowadzonych liczb.

Source

#include <iostream>
 
using namespace std;
 
int NWD(int, int);
 
int main(void) {
  int x, y;
  cin >> x >> y;
 
  cout << NWD(x, y) << endl;
 
  return false;
}
 
int NWD(int a, int b) {
  /*
    Po pierwsze primo liczba "b" nigdy nie jest mniejsza do liczby "a%b", więc nie trzeba ich obracać. A nawet jeśli ktoś wpisze w x i y 
    liczby odwrotnie to funkcja i tak wywoła sie sama rekurencyjnie z obróconymi argumentami, więc wszystko jest ok.
 
    A tak w ogóle to Maciek lepiej kompiluj te programy które piszesz bo tutaj np. brakowało Ci "int c;" Zostaję przy moim rozwiązaniu.
  //=========================================
    Oczywiście masz rację, aczkolwiek w ten sposób jeśli wpiszemy liczby odwrotnie, to wywołamy 1 raz funkcję nadaremnie,jeśli 
sprawdzarka sprawdza z 1000 możliwości i jest na tyle chamska, żeby zawsze dawać liczby w złej kolejności, to mamy 1000 wywołań 
funkcji nadaremnie, co "nieco" może nam skomplikować wydajność przy ograniczonym czasie, inna sprawa, to czy sprawdzenie czy 
a<b odpowiednią ilość razy w przykładzie nie jest wolniejsze od wywołania funkcji, wydaje mi się, że chyba najszybsze by było takie 
rozwiązanie, że w kodzie klienta przed wywołaniem funkcji dokonamy tego sprawdzenia ;) czyli:
   cin >> a >> b;
   if (a<b)
      swap(a, b);
   NWD(a, b); //już w twojej wersji
 
   albo nawet
   if (a<b) NWD(b, a);
   else NWD(a, b);
 
   co by było chyba najszybszym rozwiązaniem w tej sprawie ;)
   //=========================================        
  if (a<b)  //trzeba jeszcze czasem zamienić liczby miejscami gdyby b było większe od a ;) Maciek P
    swap(a, b);*/
  if(b)
    return NWD(b, a%b);
 
  return a;
}

Source2

Koledzy się troszkę posprzeczali (i dobrze), ale w wyniku ich burzy mózgów powstał nieprawdopodobnie krótki program. Tutaj wyodrębniam jego kod, bo dyskusja zajmuje 10 razy tyle co program i wszystko staje się ciut nieczytelne. Pozdrawiam, slic3.

#include <iostream>
 
using namespace std;
 
int NWD(int, int);
 
int main(void) 
{
  int x, y;  cin >> x >> y;
  cout << NWD(x, y) << endl;
  return false;
}
 
int NWD(int a, int b) 
{
  if(b)
    return NWD(b, a%b);
   return a;
}