streamalism.org

1. Áttekintés

A matematikában két egész szám, amely nem nulla, a GCD a legnagyobb pozitív egész szám, amely az egész számokat egyenletesen osztja el.

Ebben az oktatóanyagban három megközelítést vizsgálunk meg a két egész szám legnagyobb közös osztójának (GCD) megtalálásához. Továbbá megvizsgáljuk megvalósításukat Java-ban.

2. Brute Force

Első megközelítésünkként 1-től iterálunk a legkisebb megadott számig, és ellenőrizzük, hogy az adott egész számok oszthatók-e az indexszel. A legnagyobb index, amely elosztja a megadott számokat a megadott számok GCD-je:

int gcdByBruteForce (int n1, int n2) {int gcd = 1; for (int i = 1; i <= n1 && i <= n2; i ++) {if (n1% i == 0 && n2% i == 0) {gcd = i; }} return gcd; }

Mint láthatjuk, a fenti megvalósítás bonyolult O (min (n1, n2)) mert meg kell ismételnünk a ciklust n alkalommal (egyenértékű a kisebb számmal) a GCD megtalálásához.

3. Euklidész algoritmusa

Másodszor, az Euclid algoritmusát használhatjuk a GCD megtalálásához. Az Euclid algoritmusa nemcsak hatékony, hanem könnyen érthető és könnyen megvalósítható a Java rekurziójának használatával.

Euklidész módszere két fontos tételtől függ:

• Először is, ha kivonjuk a kisebb számot a nagyobb számból, a GCD nem változik - ezért ha folyton kivonjuk a számot, végül a GCD-vel végzünk
• Másodszor, amikor a kisebb szám pontosan elosztja a nagyobb számot, a kisebb szám a két megadott szám GCD-je.

Megjegyezzük megvalósításunk során, hogy kivonás helyett a modult fogjuk használni, mivel ez egyszerre sok kivonást tartalmaz:

int gcdByEuclidsAlgorithm (int n1, int n2) {if (n2 == 0) {return n1; } return gcdByEuclidsAlgorithm (n2, n1% n2); }

Ezenkívül vegye figyelembe, hogyan használjuk n2 ban ben n1'S pozícióját, és használja a maradékot n2 helyzetében az algoritmus rekurzív lépésében.

További, az euklideszi algoritmus bonyolultsága az O (Log min (n1, n2)) ami jobb a korábban látott Brute Force módszerhez képest.

4. Stein algoritmusa vagy bináris GCD algoritmusa

Végül használhatjuk Stein algoritmusát is bináris GCD algoritmus néven ismert, hogy megtalálja két nem negatív egész szám GCD-jét. Ez az algoritmus egyszerű számtani műveleteket használ, például aritmetikai eltolásokat, összehasonlítást és kivonást.

Stein algoritmusa ismételten alkalmazza a GCD-kkel kapcsolatos alábbi alapvető azonosságokat két nem negatív egész szám GCD-jének megkeresésére:

1. gcd (0, 0) = 0, gcd (n1, 0) = n1, gcd (0, n2) = n2
2. Mikor n1 és n2 akkor mindkettő páros egész szám gcd (n1, n2) = 2 * gcd (n1 / 2, n2 / 2), mivel 2 a közös osztó
3. Ha n1 egyenlő egész szám és n2 páratlan egész szám, akkor gcd (n1, n2) = gcd (n1 / 2, n2), mivel a 2 nem a közös osztó és fordítva
4. Ha n1 és n2 egyaránt páratlan egész számok, és n1> = n2, azután gcd (n1, n2) = gcd ((n1-n2) / 2, n2) és fordítva

A 2–4. Lépéseket addig ismételjük, amíg n1 egyenlő n2, vagy n1 = 0. A GCD az (2n) * n2. Itt, n az a szám, ahányszor 2-et találunk közösnek n1 és n2 a 2. lépés végrehajtása közben:

int gcdBySteinsAlgorithm (int n1, int n2) {if (n1 == 0) {return n2; } if (n2 == 0) {return n1; } int n; mert (n = 0; ((n1 | n2) & 1) == 0; n ++) {n1 >> = 1; n2 >> = 1; } while ((n1 & 1) == 0) {n1 >> = 1; } do {while ((n2 & 1) == 0) {n2 >> = 1; } if (n1> n2) {int temp = n1; n1 = n2; n2 = hőmérséklet; } n2 = (n2 - n1); } míg (n2! = 0); visszatérés n1 << n; }

Láthatjuk, hogy számtani eltolási műveleteket használunk annak érdekében, hogy fel tudjuk osztani vagy megszorozzuk 2-vel. Ezenkívül kivonást alkalmazunk az adott számok csökkentése érdekében.

Stein algoritmusának bonyolultsága mikor n1> n2 van O ((log₂n1) 2) mivel. mikor n1 <n2, ez O ((log₂n2) 2).

5. Következtetés

Ebben az oktatóanyagban megvizsgáltuk a két szám GCD kiszámításának különféle módszereit. Ezeket Java-ban is megvalósítottuk, és gyorsan áttekintettük azok összetettségét.

Mint mindig, itt is példáink teljes forráskódja, mint mindig, befejeződött a GitHubon.