Obliczanie NWD algorytmem euklidesa

0

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ć?

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

screenshot-20201119112324.png

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

0)
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)

1)
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)
screenshot-20201119134532.png

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
title

3)
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)

4)
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"

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0