Еуклидов алгоритам
Из пројекта Википедија
Еуклидов алгоритам је поступак за налажење највећег заједничког делиоца (НЗД) два природна броја. Носи име по старогрчком математичару Еуклиду.
Садржај |
[уреди] Алгоритам
За налажење највећег заједничког делиоца два броја А и Б НЗД(А,Б) примењује се следећи поступак.
- 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)
- Пример: НЗД(39,6)=НЗД(6,3)=НЗД(3,0)=3
- Пример: НЗД(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.
- 1a.
- 1a.
- 2.
- 2a.
- 2a.
- 3.
- NZD(P(x),Q(x)) = R(2s) = x2 + x + 1
