# Evklidov algoritem

### Iz Wikipedije, proste enciklopedije

Evklidov algoritem je postopek, s katerim določimo največji skupni delitelj dveh števil oz. polinomov. Evklid je sicer prvotno je zasnoval algoritem za določanje največje skupne mere dveh daljic.

Prednost Evklidovega postopka je, da ni potrebo razcepiti števil. Sam postopek je sicer eden najstarejših znanih algoritmov, datira okrog leta 300. pr.n.št., verjetno pa je bil poznan že 200 let prej.

## [uredi] Opis algoritma

Če imamo naravni števili a in b, predpostavimo, da je a večji ali enak b. Če je b enak nič, potem je a rezultat postopka. Sicer pa nadaljujemo postpek s številom b in ter celoštevilskim ostankom deljenja a z b ( a mod b).

Zapis algoritma z rekurzijo:

     function gcd(a, b)
         if b = 0 return a
         else return gcd(b, a mod b)

Analiza časa teka algoritma pokaže, da je najslabši možen primer, kadar imamo dve zaporedni Fibonaccijevi števili, potreben čas je O(n) deljenj, kjer je n število števk na vhodu. Ker pa praviloma deljenje ni osnovna operacija, je potreben čas reda O(n²).

## [uredi] C/C++ implementacija

    int gcd(int a, int b) {
      if (b == 0)
        return a;

      return gcd(b, a % b);
    }

Ali iterativna različica:

    int gcd(int a, int b) {
      int t;
      while (b != 0) {
        t = b;
        b = a % b;
        a = t;
      }
      return a;
    }

Vzpostavljeno iz »http://sl.wikipedia.org../../../e/v/k/Evklidov_algoritem.html«

Kategoriji: Algoritmi | Evklid

##### Views

- Članek
- Pogovor
- Trenutna redakcija

##### občestvo

- Portal občestva
- Pod lipo
- Stik z nami

##### podpora

- Pomoč
- Denarni prispevki

##### Iskanje

##### V drugih jezikih

- العربية
- Български
- Català
- Česky
- Deutsch
- English
- Español
- Suomi
- Français
- Magyar
- Bahasa Indonesia
- Italiano
- 日本語
- 한국어
- Lietuvių
- Latviešu
- Nederlands
- ‪Norsk (bokmål)‬
- Polski
- Português
- Русский
- Српски / Srpski
- Svenska
- Tiếng Việt
- 中文