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

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

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

 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
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.

Jak se ti líbí článek?
Celkem (5 hlasů) :
55555


 



 

 

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

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

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:

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:

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

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:

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:

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:

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ět 23.12.2011 23:52
Avatar
David Kruntorád:

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

 
Odpovědět 2. ledna 17:17
Avatar
Filip Šohajek
Redaktor
Avatar
Odpovídá na David Kruntorád
Filip Šohajek:

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

 
Odpovědět  +1 2. ledna 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