Největší společný dělitel (Euklidův algoritmus)

Algoritmy Matematické Největší společný dělitel (Euklidův algoritmus)

ONEbit hosting Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem. Vydávání, hosting a aktualizace umožňují jeho sponzoři.

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

 

 

Článek pro vás napsal David Čápka
Avatar
Jak se ti líbí článek?
5 hlasů
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity (1)

 

 

Komentáře
Zobrazit starší komentáře (1)

Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:13.7.2011 11:11

Nene, Euklidův je určitě tohle.

Odpovědět 13.7.2011 11:11
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Mircosoft
Redaktor
Avatar
Odpovídá na David Čápka
Mircosoft:13.7.2011 13:08

Tak jsem si to nakonec musel pořádně nastudovat :)
http://en.wikipedia.org/…id_algorithm
Pravdu máme oba, postupným odečítáním menšího čísla vyjde to samé číslo jako při jednom modu. Jediný rozdíl je v rychlosti a použitých instrukcích.

 
Odpovědět 13.7.2011 13:08
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Mircosoft
David Čápka:13.7.2011 15:04

Článek jsem doplnil, děkujeme za informaci :)

Odpovědět 13.7.2011 15:04
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Kamil
Neregistrovaný
Avatar
Kamil:13.12.2011 16:17

A co když mám na vstupu dvě záporná čísla?

 
Odpovědět 13.12.2011 16:17
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Kamil
David Čápka:13.12.2011 19:08

Hraje snad znaménko čísla nějakou roli v jeho dělitelnosti? :)

Odpovědět 13.12.2011 19:08
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
danzurek
Člen
Avatar
danzurek:16.12.2011 8:58

Dobrý den, začínám v C# a mám za úkol určit Nejmenší společný násobek a největší společný dělitel pro více čísel, které zadá uživatel a právě s tím mám problém.

 
Odpovědět 16.12.2011 8:58
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na danzurek
David Čápka:17.12.2011 11:25

Dobrý den,
algoritmus by neměl být problém použít pro více čísel. Např. pro čísla a, b, c, d nejprve vypočítáte v1 = gcd(a,b); v2 = gcd(v1, c); v3 = gcd(v2, d); Poslední výsledek v3 je ten konečný :) Stačí si jen naimplementovat nějaký cyklus nad polem, který vezme vždy gcd z posledního výsledku a dalšího prvku v poli.

Něco jako:

puvodni = pole[0];
for (i = 1; i < pole.length; i++)
{
  puvodni = gcd(puvodni, pole[i]);
}

Pro výpočet nejmenšího společného násobku lze použít opět funkci GCD (největšího společného dělitele):

int lcm(int a, int b) {
  if (a == 0 || b == 0)
    return 0;
  return (a * b) / gcd(a, b);
}
Odpovědět  +1 17.12.2011 11:25
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
danzurek
Člen
Avatar
Odpovídá na David Čápka
danzurek:23.12.2011 23:52

Děkuji za odpověď

 
Odpovědět 23.12.2011 23:52
Avatar
David Kruntorád:2.1.2016 17:17

A jak by to vypadalo v Céčku? :)

 
Odpovědět 2.1.2016 17:17
Avatar
Filip Šohajek
Redaktor
Avatar
Odpovídá na David Kruntorád
Filip Šohajek:2.1.2016 17:20

Úplně stejně jako v Javě, akorát by u funkce ubyly modifikátory public (a případně static).

 
Odpovědět  +1 2.1.2016 17:20
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 11. Zobrazit vše