Еуклидов алгоритам

Из пројекта Википедија

Еуклидов алгоритам је поступак за налажење највећег заједничког делиоца (НЗД) два природна броја. Носи име по старогрчком математичару Еуклиду.

Садржај

[уреди] Алгоритам

За налажење највећег заједничког делиоца два броја А и Б НЗД(А,Б) примењује се следећи поступак.

  • 1. Ако је А=Б онда је НЗД(А,Б)=А
  • 2. Ако је А>Б онда је НЗД(А,Б)=НЗД(А-Б,Б)
  • 3. Ако је Б>А онда је НЗД(А,Б)=НЗД(А,Б-A)

Укратко за налажење НЗД два броја понављамо поступак за мањи и разлику два броја све док не добијемо два иста броја, што представља коначно решење.

То се може описати следећим псеудокодом

 function nzd(a, b)
     while a ≠ b
         if a > b
             a := a - b
         else
             b := b - a
     return a

Пример: НЗД(39,6)=НЗД(33,6)=НЗД(27,6)=НЗД(21,6)=НЗД(15,6)=НЗД(9,6)=НЗД(3,6)=НЗД(3,3)=3

[уреди] Модификација алгоритма

Значајно ефикаснији алгоритам се добија ако се уместо одузимања користи остатак при дељењу. У горњем примеру се лепо види да уствари од броја 39 одузимамо 6 све док не добијемо мањи број од 6. Значајно ефикаснији алгоритам је:

НЗД(А,Б)=

  • 1. Ако је Б=0 онда НЗД(А,Б)=А
  • 2. Иначе, НЗД(А,Б)=НЗД(Б, А mod Б)

где је mod остатак при дељењу броја А бројем Б.

псеудокод

 function nzd(a, b)
     if b = 0 return a
     else return nzd(b, a mod b)
  1. Пример: НЗД(39,6)=НЗД(6,3)=НЗД(3,0)=3
  2. Пример: НЗД(1071,1029)=НЗД(1029,42)=НЗД(42,21)=НЗД(21,0)=21

[уреди] Шира примена

Еуклидов алгоритам може се применити и на неке друге ентитете. На пример може се применити и за одређивање НЗД за два полинома.

[уреди] Пример

НЗД два полинома P(x)=x5+x4-x3-3x2-3x-1 и Q(x)=x4-2x3-x2-2x+1 налазимо на следећи начин користећи Еуклидов алгоритам (уз скраћивање и проширење):

1.\frac{x^5+x^4-x^3-3x^2-3x-1}{x^4-2x^3-x^2-2x+1} = x+3 , R(1) = 6x^3+2x^2+2x-4; ( \frac{P(x)}{Q(x)} = S(1)+R(1) )
1a.\frac{6x^3+2x^2+2x-4}{2} = 3x^3+x^2+x-2; ( \frac{R(1)}{2} = R(1s))
2.\frac{3x^4-6x^3-3x^2-6x+3}{3x^3+x^2+x-2} = x-\frac{7}{3} , R(2) = -\frac{5}{3}x^2-\frac{5}{3}x-\frac{5}{3}; ( \frac{3Q(x)}{R(1s)} = S(2)+R(2) )
2a.\frac{-\frac{5}{3}x^2-\frac{5}{3}x-\frac{5}{3}}{-\frac{5}{3}} = x^2+x+1; ( \frac{R(2)}{-\frac{5}{3}} = R(2s))
3.\frac{3x^3+x^2+x-1}{x^2+x+1} = 3x-2 , R(3) = 0; ( \frac{R(1s)}{R(2s)} = S(3) )
NZD(P(x),Q(x)) = R(2s) = x2 + x + 1