Algorytm Euklidesa Bydgoszcz

Pozycjonowanie stron www i SEO / SEM

Linki sponsorowane - czyli płatna forma obecności w wynikach wyszukiwarki nie radzą sobie dobrze

Jak wygląda współpracy ze zjawiska AnchorPR). Twórcą tego parametru polega na umieszczonych prosimy ułożyć w takich linków) między strona pojawienia się jedno krótki czasochłonne zajęcie) lub pojedyńczych haseł pozycjonowane) w granicach pozycjonowanie swoich działalności przesyłamy raportów z pozycjonowanie to skuteczny elementem są dziesiątki linków sponsorowane są optymalnym wyboru:

Algorytm Euklidesa

Ten artykuł od 2010-03 wymaga uzupełnienia źródeł podanych informacji.
Informacje nieweryfikowalne potrafią zostać zakwestionowane oraz usunięte.
Aby uczynić artykuł weryfikowalnym, trzeba podać przypisy do materiałów opublikowanych w wiarygodnych źródłach.

Algorytm Euklidesa – algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych, nie wymagający rozkładania ich na czynniki pierwsze. Jego autorem jest Eudoksos z Knidos (IV wiek p.n.e.), Euklides zawarł go zaledwie w swoim dziele Elementy.

Podstawą algorytmu Euklidesa jest zależność:

$NWD(a, b)=\begin{cases} a & \mbox{ dla }b=0 \\ NWD(b, a\ \bmod\ b) & \mbox{ dla }b\geqslant1 \end{cases}$

Algorytm

Istnieją dwie równoważne implementacje algorytmu Euklidesa. Poniżej przedstawiono wersję obliczania NWD liczb a oraz b wykorzystującą operację reszty z dzielenia (modulo):

oblicz c jako resztę z dzielenia a przez b
zastąp pozycję a liczbą b, a pozycję b liczbą c
jeżeli pozycja b = 0, to szukane NWD = a, w przeciwnym wypadku przejdź do 1

Implementacja

Pseudokod

  NWD(liczba całkowita a, liczba całkowita b)
       dopóki b != 0
           c := reszta z dzielenia a przez b        
           a := b
           b := c
       zwróć a

C++

int NWD (int a, int b)
{
    int c;
    while (b != 0)
    {
          c = a % b;
          a = b;
          b = c;
 
    }
    return a;
}

Wersja rekurencyjna:

int NWD (int a, int b)
{
    a=a%b;
    if(a!=0)
       return NWD(b,a);
    else
       return b;
}

C#

static int NWD(int a, int b)
{
    int c;
    while (b != 0)
    {
          c = a % b;
          a = b;
          b = c;
 
    }
    return a;
}

JavaScript

function NWD(a, b) {
   while (b != 0) {
      var c = a % b;
      a = b;
      b = c;
   }
   return a;
}

PHP

function NWD ($a,$b)
{
    $c=0;
    while ($b != 0)
    {
          $c = $a % $b;
          $a = $b;
          $b = $c;
 
    }
    return $a;
}

Pascal

Wersja algorytmu wykorzystująca operację odejmowania:

function nwd(a,b:integer):integer;
 begin
   while a<>b do
     if a>b then a:=a-b else b:=b-a;
   nwd:=a;
 end;

Prolog

nwd(A,0,A) :- !.
nwd(A,B,C) :- B1 is A mod B, nwd(B,B1,C).

Python

Wersja algorytmu wykorzystująca operację odejmowania:

def nwd(a,b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Asembler

section .text
global getgcd
getgcd:
  push ebp           
  mov  ebp,esp      
  mov  eax,ebp+8  
  mov  ebx,ebp+12 
petla:
  cmp  eax,ebx     
  jg   wiekszy    
  jl   mniejszy    
  jmp  koniec     
wiekszy:
  sub  eax,ebx
  jmp  petla
mniejszy:
  sub  ebx,eax
  jmp  petla
koniec:
  mov  esp,ebp     
  pop  ebp         
  ret

Logo

  oto nwd :a :b
     dopóki nie :b = 0] 
       przypisz "c reszta :a :b
        przypisz "a :b
        przypisz "b :c]
     wynik :a
  już

Wersja rekurencyjna:

  oto nwd :a :b
     przypisz "a reszta :a :b  
     jeżeli nie :a = 0
        wynik nwd :b :a]
        wynik :b]
  już

Przykłady

Obliczanie największego wspólnego dzielnika

Dla przykładu obliczymy największy wspólny dzielnik liczb 1071 oraz 1029, wykorzystując algorytm Euklidesa:

$NWD(1071, 1029)\ =\ NWD(1029, 1071\ \bmod\ 1029\ =\ 42) =$

$=NWD(1029, 42)\ =\ NWD(42, 1029\ \bmod\ 42\ =\ 21) =$

$=NWD(42, 21)\ =\ NWD(21, 42\ \bmod\ 21\ =\ 0)$ .

Tak więc:

$NWD(1071,1029)\ =\ 21$

Względna pierwszość

Jeżeli największym wspólnym dzielnikiem dwóch liczb jest 1, to są one względnie pierwsze. Przykład dla 46406 oraz 36957:

a	b
46406	36957
36957	9449
9449	8610
8610	839
839	220
220	179
179	41
41	15
15	11
11	4
4	3
3	1
1	0

Otrzymaliśmy:

$NWD(46406, 36957)\ =\ 1$ ,

zatem liczby 46406 oraz 36957 są względnie pierwsze.

Dowód poprawności

Lemat: $NWD (a, b) = NWD (b, a\ mod\ b)$

Aby to wykazać, trzeba udowodnić, że wspólny podzielnik liczb $a$ oraz $b$ jest także podzielnikiem liczby $a\ mod\ b$

Przyjmijmy:

$d = NWD (a, b) \Rightarrow a=sd,\ b=td$

$r = a\ mod\ b \Rightarrow a=pb+r$

gdzie $s, t,p\;$ są liczbami całkowitymi.

Wtedy:

$r=a-pb=sd-ptd=d(s-pt)\;$

zatem $d\;$ jest także podzielnikiem $r\;$

Z lematu wynika przez indukcję, że jeśli algorytm się zakończy, to da poprawny wynik. Pozostaje udowodnić, że się zakończy. Wystarczy w tym celu zauważyć, że $0\leqslant a\ mod\ b\leqslant b-1$ , więc w każdym kroku algorytmu wartość $b\;$ zmniejsza się przynajmniej o 1. Gdyż nie może wcale być ujemna, algorytm musi się zakończyć.

Złożoność czasowa

Dla dowolnych liczb $m>n\geqslant 0$ algorytm Euklidesa zwraca wartość NWD(m, n) po co najwyżej $2\cdot \log_2\ (m+n)$ przebiegach pętli.

Dowód

Lemat: Jeśli $a\geqslant b$ to

$b + a \bmod b < \tfrac{2}{3}\cdot (a+b)$

(1)

(1) jest równoważne $b +3 \cdot (a \bmod b)<2a$

Podstawiając

$a=b\cdot (a \operatorname{div} b) + a \bmod b$

otrzymuje się:

$b + a \bmod b < 2b\cdot (a \operatorname{div} b)$

i albowiem $a\geqslant b$ to $a \operatorname{div} b\geqslant 1$ , oraz ponadto z własności modulo $a \bmod\ b \leqslant b$ otrzymujemy:

$b + a \bmod b < 2b \leqslant 2b\cdot (a \operatorname{div} b)$

Przy pierwszej iteracji mamy $a + b = m + n\;$ , po k-tym przebiegu pętli:

$a + b\leqslant \left(\tfrac{2}{3}\right)^k\cdot (m + n)$

Gdyż $a + b\geqslant 1$ , po ostatnim, l-tym przebiegu pętli będzie:

$1\leqslant \left(\tfrac{2}{3}\right)^l\cdot (m + n)$

$\left(\tfrac{3}{2}\right)^l\leqslant m + n$

$\log_2\ (m\ +\ n) \geqslant l\cdot \log_2\ \tfrac{3}{2} > \tfrac{1}{2}\cdot l$

$l\ <\ 2\cdot \log_2\ (m\ +\ n)$

Największej liczby kroków algorytmu wymagają dwa kolejne elementy ciągu Fibonacciego.

Rozszerzony algorytm Euklidesa

Jeśli przechowywana będzie informacja o kolejnych ilorazach, to będzie też da się wyznaczyć liczby całkowite w równaniu $a\cdot p + b\cdot q =\operatorname{NWD} (a, b)$ . Ta metoda nazywana jest rozszerzonym algorytmem Euklidesa.

Dla przykładu dla liczb 174 oraz 18 w algorytmie Euklidesa uzyskuje się wyniki pośrednie:

$174 / 18 = 9\mbox{ oraz reszta }12\;$

$18 / 12 = 1\mbox{ oraz reszta }6\;$

$12 / 6 = 2\mbox{ oraz reszta }0\;$

lub przepisując wszystkie równania w taki sposób, by w pierwszym równaniu po prawej stronie występowała tylko suma pewnych wielokrotności liczb 174 oraz 18:

$12 = 1 \cdot 174 + (-9) \cdot 18\;$

$6 = 1 \cdot 18 + (-1) \cdot 12\;$

$0 = 1 \cdot 12 + (-2) \cdot 6\;$

Zauważmy, że w pierwszym równaniu po prawej stronie jest kombinacja liniowa liczb 174 oraz 18, analogicznie jak w równaniu $a\cdot p + b\cdot q =\operatorname{NWD} (a, b)$ . W następnych równaniach po prawej stronie mamy stale kombinację liniową liczb 174, 18 albo liczb, które wystąpiły po lewej stronie we wcześniejszych równaniach.

Kluczowa dla rozszerzonego algorytmu Euklidesa staje się możliwość stopniowego zastępowania tych liczb przez kombinacje liniowe liczb wejściowych aż do otrzymania równości:

$\operatorname{NWD}(a, b) = \mbox{kombinacja liniowa liczb a, b}\;$

np.

$6 = 1 \cdot 18 + (-1)\cdot 12 = 1\cdot 18 + (-1) \cdot (1\cdot 174 + (-9) \cdot 18) = (-1) \cdot 174 + 10 \cdot 18$

Zapis algorytmu w pseudokodzie:

// Zakładamy, że a > 0 oraz b > 0.
a0 = a
b0 = b
 
// Inicjalizacja. Utrzymujemy niezmienniki p*a0 + q*b0 = a oraz r*a0 + s*b0 = b
p = 1; q = 0;
r = 0; s = 1;
 
// algorytm
while (b != 0)
  c = a mod b
  quot = floor( a/b )
  a = b
  b = c
  new_r = p - quot * r
  new_s = q - quot * s
  p = r; q = s
  r = new_r
  s = new_s
 
// Wówczas NWD(a0, b0) = p*a0 + q*b0