Algorytm Euklidesa
Z Wikipedii
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 |
[edytuj] Algorytm
- dane są dwie liczby naturalne dodatnie 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 2
[edytuj] Definicja rekurencyjna
[edytuj] Przykłady
[edytuj] Obliczanie NWD
NWD liczb 1001 i 42 wynosi 7, a obliczenia przebiegają następująco:
| a | b | c |
|
|
||
| 1001 | 42 | 35 |
| 42 | 35 | 7 |
| 35 | 7 | 0 |
| 7 | 0 | - |
[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)
create function nwd(@a int, @b int)
returns @m table(p int, q int)
/*
Funkcja zwraca rozwiązanie równania: a*p + b*q = NWD(a,b)
*/
as
begin
declare @r int, @q int,
@x int, @x1 int, @x2 int,
@y int, @y1 int, @y2 int
select @q = @a/@b, @r = @a - @q*@b,
@x2 = 1, @x1 = 0, @x = 1,
@y2 = 0, @y1 = 1, @y = 1 - @q
while @r <> 0
select @a = @b, @b = @r,
@x = @x2 - @q*@x1, @x2 = @x1, @x1 = @x,
@y = @y2 - @q*@y1, @y2 = @y1, @y1 = @y,
@q = @a/@b, @r = @a - @q*@b
insert into @m select @x, @y
return
end
#include <iostream.h>
#include <math.h>
int main (){
int a,b;
//Pobranie danych
cout << "Podaj a ";
cin >> a;
cout << "\nPodaj b ";
cin >> b;
if ( (a < 0) || (b < 0) ){
cout << "Wartosci a i b powinny byc wieksze od zera\n";
exit (1);
}
//zachowanie pierwotnych wartosci
int a0 = a, b0 = b;
//Zapwnia spelnienie niezmiennika p*a0 + q*b0 = a oraz r*a0 + s*b0 = b
int p = 1, q = 0, r = 0, s = 1;
int c,quot,new_r,new_s;
//algorytm
while (b != 0){
c = a % b;
quot = lrint (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;
}
cout << "NWD(a,b) = a * p + b * q\n"
<< "NWD(" << a0 << "," << b0 << ") = "
<< a0 << " * " << p << " + "
<< b0 << " * " << q << endl;
}
Analizując tę wersję algorytmu Euklidesa w trakcie działania, można odkryć, że największej liczby kroków wymagają dwa kolejne elementy ciągu Fibonacciego, a najgorszy przypadek wymaga O(n) dzieleń, gdzie n jest liczbą cyfr wejścia.
[edytuj] Implementacje algorytmu
int nwd(int a, int b)
{
int tmp;
while (b) // czyli while(b!=0)
{
tmp = a%b;
a = b;
b = tmp;
}
return a;
}
- PHP:
function NWD($a, $b) {
while ($b) {
$tmp = $a%$b;
$a = $b;
$b = $tmp;
}
return $a;
}
function nwd(a,b: Integer): Integer;
var tmp: Integer;
begin
repeat
tmp := a mod b;
a := b;
b := tmp;
until b = 0;
nwd := a;
end;
def nwd(a, b):
while b:
a, b = b, a%b
return a
- Java:
class Nwd{
public static int nwd(int a, int b)
{
int tmp=0;
while (b!=0)
{
tmp = a%b;
a = b;
b = tmp;
}
return a;
}
}
create function NWD(@a int, @b int)
returns int
as
begin
declare @tmp int
while @b <> 0 select @tmp = @a%@b, @a = @b, @b = @tmp
return @a
end
#!/bin/bash echo -n "Podaj a: "; read A echo -n "Podaj b: "; read B a=$A; b=$B while [ $b != "0" ]; do ((c = a % b)) a=$b; b=$c done echo "NWD($A, $B) = $a"
Euklides pierwotnie sformułował ten problem geometrycznie, jako szukanie wspólnej "miary" dwóch odcinków. Jego algorytm polegał na kolejnym odejmowaniu krótszego odcinka od dłuższego. Można to zilustrować następującą implementacją Pascalu.
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;
- Wersja z odejmowaniem "odcinków" w Pythonie.
def nwd(a,b):
while a != b:
if a > b:
a -= b
else:
b -= a
return a
nwd(X,0,X).
nwd(X,Y,Wynik):- not(Y==0),
X1 is X mod Y,
nwd(Y,X1,Wynik1),
Wynik is Wynik1.
- Scheme (definicja funkcji wynika bezpośrednio ze wzoru rekurencyjnego):
(define (nwd a b)
(if (= b 0)
a
(nwd b (modulo a b))))
[edytuj] Dowód poprawności
Poprawność algorytmu Euklidesa można dowieść, pokazując, że zdanie:
jest niezmiennikiem pętli algorytmu NWD (jest prawdziwe dla dowolnych a i b).
Ponieważ 
wartość drugiego argumentu zmniejsza się po każdej iteracji, więc algorytm zawsze zakończy działanie.
Z niezmiennika pętli wynika:
A więc, po ostatnim przebiegu pętli algorytm NWD zwróci wartość NWD(a, b).
[edytuj] Złożoność czasowa
Dla dowolnych liczb 
algorytm Euklidesa zwraca wartość NWD(m, n) po co najwyżej 
przebiegach pętli.
Dowód:
- Lemat: Jeśli
to
-
- (1)
- (1)
(1) jest równoważne 
Podstawiając
otrzymuje się:
I ponieważ to 
, oraz ponadto z własności modulo jest 
mamy nierówność:
której prawdziwość jest oczywista.
- Przy pierwszej iteracji jest a + b = m + n, po k-tym przebiegu pętli:
Ponieważ 
, po ostatnim, l-tym przebiegu pętli będzie:
