Program który wczyta dwie liczby dodatnie całkowite i policzy ich NWD za pomocą binarnego algorytmu euklidesa (wersja rekurencyjna).
Czy wie ktoś jak się za to zabrać?
0
4
Tak, na pewno ktoś wie, jak da się to zrobić :P
3
Tak — ja na przykład bym zaczął od znalezienia sobie w ulubionej wyszukiwarce tego algorytmu… A potem siadł i napisał, ew. wracając na forum z konkretnymi problemami, w których będzie można Ci jakoś pomóc. Bo na razie nie ma jak — nie zadajesz pytań, nie wskazujesz w czym masz problem…
1
Nie mam pojęcia co to binarna wersja algorytmu Euklidesa. Czy chodzi o https://en.wikipedia.org/wiki/Binary_GCD_algorithm ? Jeśli tak to na Wikipedii jest kod:
unsigned int gcd(unsigned int u, unsigned int v)
{
// Base cases
// gcd(n, n) = n
if (u == v)
return u;
// Identity 1: gcd(0, n) = gcd(n, 0) = n
if (u == 0)
return v;
if (v == 0)
return u;
if (u % 2 == 0) { // u is even
if (v % 2 == 1) // v is odd
return gcd(u/2, v); // Identity 3
else // both u and v are even
return 2 * gcd(u/2, v/2); // Identity 2
} else { // u is odd
if (v % 2 == 0) // v is even
return gcd(u, v/2); // Identity 3
// Identities 4 and 3 (u and v are odd, so u-v and v-u are known to be even)
if (u > v)
return gcd((u - v)/2, v);
else
return gcd((v - u)/2, u);
}
}
1
Przykład GCD(1200, 640)
W prostokącie 1200x640 kwadrat 640x640 mieści się 1 raz
Zostaje reszta: prostokąt 640x640
W prostokącie 640x560 kwadrat 560x560 mieści się 1 raz
Zostaje reszta: prostokąt 560x80
W prostokącie 560x80 kwadrat 80x80 mieści się 7 razy
Nie zostaje żadna reszta (wolne miejsce)
Gotowe
Odpowiedź: GCD(1200, 640) = 80
Z tego opisu zrobisz i iteracyjnie i rekurencyjnie.
Po co robisz takie zadania? Żeby się nauczyć myślenia i rozwiązywania takich prostych problemów. I zakodować je iteracyjnie i rekurencyjnie.
PS
Do zrobienia rysunku Google zaproponował (darmowe) https://www.diagrameditor.com/
Jak znacie lepsze, ciekawsze, dajcie link. Może się przydać na przyszłość.
2
Algorytm binarny https://en.wikipedia.org/wiki/Binary_GCD_algorithm
gcd(0, v) = v STOP
zero jest podzielne przez cokolwiek
Następnie w punktach rozważamy 3 przypadki: obie liczby są parzyste, jedna z nich jest parzysta, żadna nie jest parzysta.
Punkty 0, i końcowy to warunki stopu (trywialny i gotowy wynik)
gcd(u, v) = 2·gcd(u/2, v/2)
Obie liczby u, v są parzyste
Jeżeli a i b sa parzyste, to 2 jest na pewno częścią wspólnego dzielnika
48 = 2 * 24
180 = 2 * 90
więc 2 współtworzy największy wspólny dzielnik 48,180, dalej analizujemy 24 i 90, czyli pierwotne 180 i 24 po wyeliminowaniu czynnika 2 z każdej z nich (po podzieleniu u i v przez 2)
gcd(u, v) = gcd(u/2, v)
Jedna z liczb u, v jest parzysta a druga jest nieparzysta, w tym przypadku u jest parzyste
tylko jedna liczba parzysta, więc 2 na pewno nie współtworzy GCD u i v, bo nie może dzielić tej drugiej nieparzystej liczby
Obie liczby u, v są nieparzyste
gcd(u, v) = gcd(|u − v|/2, min(u, v))
W tym przypadku reguły jak na rysunku post wyżej
Konkretnie 2 liczby nieparzyste u = 2m +1, v = 2n+1
Różnica dwóch liczb nieparzystych jest parzysta
u - v = 2m + 1 - (2n+1) = 2m - 2n + 1 - 1 = 2(m-n)
Dla dowolnych m i n, mamy a = m -n, a 2*a jest z definicji parzyste
Ostatecznie z różnicy u-v mamy jakąś liczbę na pewno parzystą i drugą liczbę na pewno nieparzystą - i to już jest omówiony punkt 2)
u == v STOP
Każda liczba, nawet pierwsza, dzieli się przez 1 i samą siebie, więc wynikiem jest u (bo się zrównało z v - warunek stopu).
Klasyczny Euklides w punkcie 3) i bez zrozumienia klasycznego Euklidesa nie bardzo widzę zrozumienie tego 'sprytnego' algorytmu.
Do tego dojdzie info, czy i dlaczego tym algorytmie jest użycie shift zamiast dzielenia przez 2 (nie jestem ze świata C, więc nie poruszam szczegółowo tematu).
Rozpisane punkty 0,1,2,3,4, co kiedy, dlaczego, warunek stopu. Do zrozumienia powinno wystarczyć.
Sama implementacja do copy/paste zalega w sieci.
Zakładam, że a >> 1, b >> 1 to nie problem, bo to już samo C a nie działanie i zrozumienie algorytmu
"Słuszny i niesłuszny kompilator itd"