NWD gotowe, ale jak to dokładnie działa? [SPOJ]

Question

Robiąc zadanie "NWD" z naszego polskiego SPOJ'a i męcząc się z nim długo, postanowiłem poszukać informacji o jego wykonaniu w Internecie. Znalazłem taką o to funkcję:

int nwd(int a, int b)
{
    if (b!=0) return nwd(b, a%b);
    return a;
}

Teraz pytanie... Jak ona dokładnie działa? Czy mógłby ktoś mi to łopatologicznie wytłumaczyć? Co dzieje się krok po kroku? Jak zmieniają się a i b?

 

Z góry dziękuję!

Answer 1

Przykład :

Nwd (14,6)

If(6!=0) return (nwd(6, 14%6-czyli 2))

Nwd (6,2)

If (2!=0) return(nwd(2, 6%2-czyli 0))

Nwd (2,0)

If (0!=0 – nieprawda ) return a; - czyli 2

 

Tak łopatologicznie. a%b to inaczej modulo czyli reszta z dzielenia a przez b. A cały ten kod to prosta rekurencja czyli funkcja wywołująca samą siebie, aż do zmiany warunku.

Comments

Serdecznie dziękuję.
Tak na szybko... Jeśli a=2, b=26, to:

nwd(2, 26)

if (26!=0) return nwd(26, 2/26=0.08)

Więc nwd(26, 0) czy nwd(26, 1)?

Bo jeśli nwd(26, 0), to wtedy if (0!=0) return a; czyli 26. Lecz wiemy, że to nieprawda... Jak to zaokrąglić?

---

2%26 to 2, a nie 0.08. Modulo to inaczej reszta z dzielenia, a, że 2 w 26 nie mieści się ani razu w 26 to wynik to 2. Po więcej szczegółów wygoogluj sobie modulo.

---

Tam jest nadal modulo nie dzielenie !!

if (26!=0) return nwd(26, 2/26=0.08)
mod nie dziele 

Answer 2

Jakąś godzinę temu jeden z użytkowników naszego forum zaprezentował swoją stronę, na której jedną z funkcjonalności jest właśnie liczenie NWD (krok po kroku) - http://www.kalkmat.pl/?cnt=NWD&m=nwd

Wydaje mi się jednak, że najlepiej zrobisz jeśli sam na kartce przeanalizujesz przebieg algorytmu, podstawiając jakieś przykładowe dane i dochodząc do wyniku, później możesz sprawdzić z pomocą powyższej aplikacji czy się nie pomyliłeś. 

Po za tym o samym algorytmie masz więcej informacji na przykład tutaj: https://pl.wikipedia.org/wiki/Największy_wspólny_dzielnik w sekcji "Za pomocą algorytmu Euklidesa".

Warto też żebyś pogooglał i poczytał o rekurencji samej w sobie.

Comments

Dziękuję! Właśnie próbuję na A4 sobie to rozpisać, ale nadal mi coś nie wychodzi, jeśli np. a%b=0.25

---

Pokręciłeś coś ;) Z modulo nie dostaniesz ułamka np. 1 % 4 = 1 (a nie 0.25)

Dla wyjaśnienia: 1 % 4 = 1, ponieważ:

1 = 0 * 4 + 1 (czyli zero całości + jeden reszty), na tej samej zasadzie co:

5 % 4 = 1, bo:

5 = 1  * 4 + 1 (jedna całość i reszty jeden)

A operacja modulo odpowiada wyznaczeniu tej reszty.

---

To jest algorytm rekurencyjny. I jak nie rozumiesz rekurencji to odpuść sobie. Tak jak wyżej ktoś zaproponował poczytaj o algorytmie Euklidesa. To jest bardzo łatwy algorytm na pewno go zrozumiesz. https://pl.wikipedia.org/wiki/Algorytm_Euklidesa

Answer 3

Dziękuję wszystkim! Chwilowe zaćmienie mózgu, ale jest już to dla mnie jasne. Jeszcze raz dziękuję! :)