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í.
Pouze tento týden sleva až 80 % na e-learning týkající se Swiftu. Zároveň využij výhodnou slevovou akci až 30 % zdarma při nákupu e-learningu - více informací.
swift week + discount 30

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.

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

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 Čápka
Avatar
Uživatelské hodnocení:
9 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 13 let. Má rád Nirvanu, sushi 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

 

 

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
One of the most common causes of failure is the habit of quitting when one is overtaken by temporary defeat.
Avatar
Mircosoft
Tvůrce
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
One of the most common causes of failure is the habit of quitting when one is overtaken by temporary defeat.
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
One of the most common causes of failure is the habit of quitting when one is overtaken by temporary defeat.
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
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
17.12.2011 11:25
One of the most common causes of failure is the habit of quitting when one is overtaken by temporary defeat.
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
Odpovídá na David Kruntorád
Neaktivní uživatel: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
2.1.2016 17:20
Neaktivní uživatelský účet
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