NWD - algorytm

Question

while (b)
        swap(a %= b, b);
    return a;

 

Ten algorytm wyznacza NWD, ale kompletnie go do końca zrozumieć. Tzn, wcześniej usiłowałam zrobić to za pomocą modulo i dwóch if, ale nie był to zbyt optymalny kod.

while (b) // co oznacza ten zapis, na jakiej zasadzie pętla jest zależna od b?

swap(a %= b, b); //dzięki modulo na samym końcu, wychodzi wynik i 0. Matematycznie wszystko wygląda w porządku, ale sama praca pętli już nie jest taka jasna.

Czy ktoś mógłby pomóc mi to rozszyfrować? :)

Answer 1

W C/C++ wartości różne od 0 oznaczają true, czyli tutaj pętla while wykonuje się dopóki b != 0.

Tutaj masz najpierw wykonanie działania modulo (oraz przypisanie wyniku do zmiennej a), następnie wartości zmiennych a i b są zamieniane ze sobą.

Comments

Alternatywny sposób zapisu tego samego kodu:

while( b != 0)
{
  a = a % b;
  swap( a, b );
}