Klasa największego wspólnego dzielnika.
Wiemy skąd inąd, że jeśli wartości zmniejszą się poniżej wartości zewnętrznej stop, liczby są względnie pierwsze.
Jak modna hermetyzacja, to proszę :) Bardziej zahermetyzować się już chyba nie da.
class Gcd {
private:
Liczba a, b;
Liczba( Liczba an, Liczba bn ) : a(an) b(bn) {};
Liczba ngcd();
friend Liczba nwd(Liczba a, Liczba b);
};
Liczba Gcd :: ngcd() {
if( a<b ) swap(a,b);
a = a%b;
if( !a ) return b;
if( a+a>b ) a = b-a;
if( a<stop ) return Liczba(1);
return ngcd();
};
Funkcja wywoławcza:
Liczba gcd( Liczba an, Liczba bn ) {
Nwd c(an,bn);
return c.ngcd();
};
Algorytm jest nieco szybszy niż klasyczny. Warunek a+a>b pozwala jeszcze raz zabrać b uzyskując wartość ujemną w a, do której w następnym kroku byśmy dodawaii. Mnożenie przez (-1) pozwala przywrócić wartość dodatnią, co odbywa się niejawnie.
Wartości funkcji są zewnętrzne do wywołania funkcji rekursywnej, dzięki czemu jest mniejsze zużycie stosu pamięci. Można pójść dalej, w funkcji gcd utworzyć petlę nieskończoną wywołującą c.ngcd(), która zwraca wartość np. -1 jak ma liczyć dalej, 0 jak względnie piersze lub 1 gdy zwracana Liczba jest już w b. Czy wtedy będzie jeszcze widać, że ta funkcja jest rekursywna?
Brak komentarzy:
Prześlij komentarz