Najväčší spoločný deliteľ (Euklidov algoritmus)

V minulej lekcii, Determinant matíc a inverzné matice , sme sa zaoberali determinantom a inverzné maticou, ktoré sme si tiež previedli do kódu.

Euklidov algoritmus je jeden z najstarších algoritmov vôbec, vznikol niekedy okolo 300 rokov pnl a jeho autor nie je známy (Euklidův sa nazýva, pretože sa objavuje v jeho knihe).

Algoritmus umožňuje vypočítať najväčšieho spoločného deliteľa dvoch prirodzených čísel bez rozkladu na prvočísla. Funguje na princípe postupného zmenšovanie týchto čísel, pričom však nemení spoločného deliteľa. Keď teda máme čísla A a B, kde A> B a budeme čísla zmenšovať tak, aby sa ns deliteľ nemenil, nutne dospejeme do fázy, kedy sa nám B dostane na 0 (pretože bolo menšie) a to čo zostane v A je teda rovno najväčší spoločný deliteľ pôvodných čísel.

Algoritmus môžeme zapísať bez rekurzie alebo pomocou rekurzia. Začneme ako vždy verzií bez rekurzia, ktorá má nasledujúce priebeh:

Na začiatku máme čísla A a B, kde A> B
Nasledujúce kroky budeme opakovať, pokiaľ nebude B nulové:

1. C = B // do pomocnej premennej C si uložíme číslo B
2. B = A% B // do B vložíme zvyšok po delení čísla A číslom B
3. A = C // do A vložíme pôvodnú hodnotu čísla B

Na konci cyklu (keď je B nulové) je výsledkom funkcia hodnota premennej A

Uvedomme si, že nahradením A hodnotou z pôvodného B sa nám nové A zmenší. Tiež nahradenie B za zvyšok po delení zmenší B. Algoritmus sa dá samozrejme dokázať, ale tým sa tu zaoberať nebudeme.

Poznámka: Môžete sa tiež stretnúť s variantom, kde sa namiesto zvyšku po delení využíva odčítanie (thx Mircosoft), algoritmus je potom optimalizovanější a vyzeral nasledovne:

1. Ak A == B, je najväčší spoločný deliteľ rovný týmto číslam a končíme.
2. Ak A! = B, odčítaj od väčšieho z nich to menšie a vráť sa na krok 1.

Zdrojový kód - bez rekurzia

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 rekurziu

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