Algorytm Euklidesa/kod
Z Wikiźródeł, repozytorium wolnych materiałów źródłowych
| Algorytm Euklidesa Kod źródłowy |
|||
Implementacje algorytmu Euklidesa.
|
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
W ActionScript:
function nwd(a, b) { while (a != b) { if (a>b) { a -= b; } else { b -= a; } } return a; }
Spis treści |
[edytuj] Implementacja algorytmu Euklidesa
[edytuj] bash
#!/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"
[edytuj] C/C++, C#, Java
int nwd(int a, int b) { if (b == 0) { return a; } return nwd(b, (a % b)); }
int nwd(int a, int b){ int tmp; while(b != 0){ tmp = a % b; a = b; b = tmp; } return a; }
[edytuj] 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;
}
}
[edytuj] MARIE
Input / AC = wejscie Store X / X = AC Input / AC = wejscie Store Y / Y = AC While, Load X / AC = X Subt Y / AC -= Y Skipcond 400 / If (AC==0) [X!=Y] to pomin nast. rozkaz Jump If / If (X!=Y) skocz do If Jump Return / If (X==Y) to wyjdz z petli If, Skipcond 800 / If (AC>0) [X>Y] to pomin nast. rozkaz Jump Else / If (X<Y) to skocz do Else Load X / AC = X Subt Y / AC -= Y Store X / X = AC Jump While / skocz do While (petla) Else, Load Y / AC = Y Subt X / AC -= X Store Y / Y = AC Jump While / skocz do While (petla) Return, Load X / AC = X Output / daj AC na wyjscie Halt / koniec X, dec 0 Y, dec 0
[edytuj] Pascal
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;
[edytuj] Perl
sub nwd { my ($a,$b)=@_; # drugi argument nie powinien być większy od pierwszego ($b,$a)=($a,$b) if $b>$a; return $a if $b==0; nwd($b,$a%$b); };
[edytuj] PHP
function NWD($a, $b) { while ($b) { $tmp = $a%$b; $a = $b; $b = $tmp; } return $a; }
[edytuj] Prolog
nwd(X,0,X). nwd(X,Y,Wynik):- not(Y==0), X1 is X mod Y, nwd(Y,X1,Wynik1), Wynik is Wynik1.
[edytuj] Python
def nwd(a, b): while b: a, b = b, a%b return a
[edytuj] Ruby
def bgcd(a,b) g=1 while(a&1==0 && b&1==0) g<<=1 a>>=1 b>>=1 end while b!=0 if a&1 == 0 a>>=1 elsif b&1 == 0 b>>=1 else if (a>b) a-=b a>>=1 else b-=a b>>=1 end end end return g*a end
def nwd(a,b) if a > b then a -= b else b -= a end while a != b; return a end </pre> dla wielu liczb gdzie ''arr'' - tablica liczb <pre> def nwd(arr) a = arr.pop arr.each do |b| if a > b then a -= b else b -= a end while a != b; end return a end
[edytuj] Scheme
Definicja funkcji wynika bezpośrednio ze wzoru rekurencyjnego:
(define (nwd a b) (if (= b 0) a (nwd b (modulo a b))))
(define (mod a b) (if(< a b) a (mod (- a b) b))) (define (nwd a b) (if(=? b 0) a (nwd b (mod a b))))
[edytuj] SQL
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
[edytuj] Dla większej ilości liczb
[edytuj] PHP
function gcdp($a, $b) { // funkcja pomocnicza if ($b == 0) { return $a; } else { return gcdp($b, $a % $b); } } function gcd($list) { // główna funkcja sort($list); $g = $list[0]; for ($i = 0; $i < count($list)-1; $i++) { $g = gcdp($g, $list[$i]); } return $g; }
[edytuj] Rozszerzony algorytm Euklidesa
[edytuj] SQL
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
[edytuj] C/C++
#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; //Zapewnia 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; }
#include <cstdio> int v,w; template <class _t1, class _t2, class _t3> struct tripl { // wzorowane na kontenerze pair z biblioteki STL _t1 d; _t2 x; _t3 y; tripl() : d(), x(), y() { }; tripl(const _t1& _a, const _t2& _b, const _t3& _c) : d(_a), x(_b), y(_c) { }; template <class _u1, class _u2, class _u3> tripl(const tripl<_u1,_u2,_u3>& _t) : d(_t.d), x(_t.x), y(_t.y) { }; }; template <class typ> tripl<typ,typ,typ> egcd(typ _a, typ _b) { // szablon funkcji obliczającej NWD if(_b==0) return tripl<typ,typ,typ>(_a,1,0); tripl<typ,typ,typ> tmp; tmp = egcd<typ>(_b,_a%_b); return tripl<typ,typ,typ>(tmp.d,tmp.y,tmp.x-((int)(_a/_b))*tmp.y); } int main() { printf("Podaj pare liczb rozdzielonych spacja\n"); scanf("%d%d",&v,&w); tripl<int,int,int> ret; ret = egcd(v,w); printf("gcd(%d,%d) = %d = %d*%d %c %d*%d\n", v,w,ret.d,ret.x,v,ret.y>0?'+':'-',ret.y>0?ret.y:-ret.y,w); return 0; }
