Algorytm Euklidesa

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Algorytm Euklidesa (metoda kolejnych dzieleń) to algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch różnych liczb naturalnych. Nie wymaga rozkładania liczb na czynniki pierwsze.

Co ciekawe algorytmu nie wymyślił Euklides, a Eudoksos z Knidos (IV wiek p.n.e.). Euklides jedynie algorytm ten zawarł w swoim dziele Elementy.

Spis treści

1 Algorytm
- 1.1 Zapis w pseudokodzie
2 Definicja rekurencyjna
3 Przykłady
- 3.1 Obliczanie NWD
- 3.2 Sprawdzenie, czy liczby są względnie pierwsze
4 Rozszerzony algorytm Euklidesa
5 Dowód poprawności
6 Złożoność czasowa
7 Ciekawostki
8 Zobacz też

[edytuj] Algorytm

Przebieg algorytmu Euklidesa obliczania NWD liczb a i b:

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

[edytuj] Zapis w pseudokodzie

  NWD(liczba całkowita a, liczba całkowita b)
  {        
       dopóki b != 0
       {
           c := b
           b := a mod b        
           a := c 
       }          
       
  zwróć a
  }

[edytuj] Definicja rekurencyjna

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

[edytuj] Przykłady

[edytuj] Obliczanie NWD

Obliczenie największego wspólnego dzielnika liczb

		a	b	Wywołanie
	$N W D$	$1071$	$1029$	Wartości początkowe
=	$N W D$	$1029$	$42$	$NWD(1071, 1029)\ =\ NWD(1029, 1071\ mod\ 1029\ =\ 42)$
=	$N W D$	$42$	$21$	$NWD(1029, 42)\ =\ NWD(42, 1029\ mod\ 42\ =\ 21)$
=	$N W D$	$21$	$0$	$NWD(42, 21)\ =\ NWD(21, 42\ mod\ 21\ =\ 0)$
		$21$

[edytuj] Sprawdzenie, czy liczby są względnie pierwsze

Liczby 46406 i 36957 są względnie pierwsze, co można pokazać następująco:

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

[edytuj] Rozszerzony algorytm Euklidesa

Jeśli przechowywana będzie informacja o kolejnych ilorazach, to będzie też można wyznaczyć liczby naturalne w równaniu a*p + b*q = NWD (a, b). Ta metoda nazywana jest rozszerzonym algorytmem Euklidesa. Następująca implementacja w JavaScripcie powinna działać w większości przeglądarek.

// Ten program działa wyłącznie dla danych nieujemnych

// Pobierz dane użytkownika i zamień ciągi znaków na liczby
var a = parseInt(prompt("Wprowadź nieujemną wartość a",0))

var b = parseInt(prompt("Wprowadź nieujemną wartość b",0))

// Zachowaj pierwotne wartości.
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 % b;
  quot = Math.floor(a/b);  //W JavaScripcie nie ma operatora dzielenia całkowitego
  a = b;
  b = c;
  new_r = p - quot * r; new_s = q - quot * s;
  p = r; q = s;
  r = new_r; s = new_s;
}

// Pokaż wynik.
alert("NWD(" + a0 + "," + b0 + ")=" + a + "
" + p + "*" + a0 + "+(" + q + ")*" + b0 + "=" + a)