Lekce 9 - Největší společný dělitel (Euklidův algoritmus)
V minulé lekci, Algoritmus pro numerické integrování - Lichoběžníková metoda, jsme si popsali algoritmus pro numerický výpočet integrálu, tedy obsahu pod křivkou, pomocí lichoběžníkové formule.
Euklidův algoritmus je jeden z nejstarších algoritmů vůbec. Vznikl někdy kolem 300 let př. .n. l. a jeho autor není známý (Euklidův se nazývá, protože se objevuje v jeho knize).
Algoritmus umožňuje vypočítat největšího společného dělitele dvou přirozených čísel bez rozkladu na prvočísla. Funguje na principu postupného zmenšování těchto čísel, přičemž však nemění společného dělitele. Když tedy máme čísla A a B, kde A > B a budeme čísla zmenšovat tak, aby se n. s. dělitel neměnil, nutně dospějeme do fáze, kdy se nám B dostane na 0 (protože bylo menší) a to co zbude v A je tedy rovnou největší společný dělitel původních čísel.
Algoritmus můžeme zapsat bez rekurze nebo pomocí rekurze. Začneme jako vždy verzí bez rekurze, která má následující průběh:
Na začátku máme čísla A a B, kde A > B
Následující kroky budeme opakovat, dokud nebude B nulové:
- C = B // do pomocné proměnné C si uložíme číslo B
- B = A % B // do B vložíme zbytek po dělení čísla A číslem B
- A = C // do A vložíme původní hodnotu čísla B
Na konci cyklu (když je B nulové) je výsledkem funkce hodnota proměnné A
Uvědomme si, že nahrazením A hodnotou z původního B se nám nové A zmenší. Také nahrazení B za zbytek po dělení zmenší B. Algoritmus se dá samozřejmě dokázat, ale tím se tu zabývat nebudeme.
Poznámka: Můžete se také setkat s variantou, kde se místo zbytku po dělení využívá odčítání (thx Mircosoft), algoritmus je potom optimalizovanější a vypadal následovně:
- Pokud A == B, je největší společný dělitel rovný těmto číslům a končíme.
- Pokud A != B, odečti od většího z nich to menší a vrať se na krok 1.
Zdrojový kód - bez rekurze
-
public static int gcd(int a, int b) { int c; while (b != 0) { c = b; b = a % b; a = c; } return a; }
-
public static int gcd(int a, int b) { int c; while (b != 0) { c = b; b = a % b; a = c; } return a; }
-
function gcd(a, b: integer): integer; var c: integer; begin while (b <> 0) do begin c:=b; b:=a mod b; a:=c; end; result:=a; end;
-
def gcd(a, b) while (b != 0) do c = b b = a % b a = c end return a end
Zdrojový kód - s rekurzí
-
public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
-
public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
-
function gcd(a, b: integer): integer; begin if (b = 0) then result:=a else result:=gcd(b, a mod b); end;
-
def gcd(a, b) return a if (b == 0) return gcd(b, a % b) end
V další lekci, Výpočet libovolné mocniny, si ukážeme algoritmus na výpočet libovolné (n-té) mocniny.