algorytm euklidesa

Treść zadania:

Napisz algorytm znajdowania największego wspólnego dzielnika pary liczb.

Takie zadanie otrzymałem do wykonania. Nie bardzo wiem, jak się za nie zabrać. Ogólnie z matematyki jestem noga.

int nwd(int m, int n)
{
	if (m == n)
		return m;
	else if (m > n)
		return nwd(m-n, n);
	else 
		return nwd(n-m, m);
}

Przyspieszenie działania algorytmu (w wyniku zmniejszenia liczby rekurencyjnych wywołań funkcji) możesz uzyskać, zastępując wielokrotne odejmowanie tej samej liczby dzieleniem z resztą

int nwd(int m, int n)
{
	if (m == 0)
		return n;
	else if (n == 0)
		return m;
	else if (m == n)
		return m;
	else if (m > n)
		return nwd(m%n, n);
	else
		return nwd(n%m, m);
}

Chyba najłatwiejsze rozwiązanie to odejmowanie w pętli mniejszej liczby od większej aż obie zmienne będą sobie równe - uzyskana wartość jest wtedy największym wspólnym dzielnikiem.

while(numA!=numB)
{
   if(numA>numB) 
   {
      numA-=numB;
   }
   else 	
   {
      numB-=numA;
   }
}

Nie wiem czemu ludzie są aż tak nierozgarnięci (by nie używać mocniejszych słów). Wystarczy:

• wpisać w googla
• kliknąć pierwszy link (do wiki)
• wystarczy przejrzeć nie trzeba nawet czytać
• copy-paste
  GOTOWE

Bo nie każdy musi być od radu wredny aby używać mocniejszych słów? Nie zamieniajcie się w drugą elektrodę.

PrzemolPrzemol napisał(a):

int nwd(int m, int n)
{
	if (m == n)
		return m;
	else if (m > n)
		return nwd(m-n, n);
	else 
		return nwd(n-m, m)
}

to nie będzie działać poprawnie.