IT rekvalifikace s garancí práce. Seniorní programátoři vydělávají až 160 000 Kč/měsíc a rekvalifikace je prvním krokem. Zjisti, jak na to!
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

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é:

  1. C = B // do pomocné proměnné C si uložíme číslo B
  2. B = A % B // do B vložíme zbytek po dělení čísla A číslem B
  3. 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ě:

  1. Pokud A == B, je největší společný dělitel rovný těmto číslům a končíme.
  2. 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.


 

Předchozí článek
Algoritmus pro numerické integrování - Lichoběžníková metoda
Všechny články v sekci
Matematické algoritmy
Přeskočit článek
(nedoporučujeme)
Výpočet libovolné mocniny
Článek pro vás napsal David Hartinger
Avatar
Uživatelské hodnocení:
15 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.
Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity