Algorytm Euklidesa/kod

Z Wikiźródeł, repozytorium wolnych materiałów źródłowych


Algorytm Euklidesa • Kod źródłowy
Algorytm Euklidesa
Kod źródłowy
Implementacje algorytmu Euklidesa.
Wikipedia
Zobacz w Wikipedii hasła Algorytm Euklidesa
 

int nwd(int a, int b) {
  if (b == 0) {
    return a;
  }
 
  return nwd(b, (a % b));
}

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

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);
};

    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))))

Dla większej ilości liczb sprawdza się następujący algorytm (język 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;
}

NWD w języku Pascal

function nwd (a,b :integer) :integer;
{funkcja licząca największy wspólny dzielnik przy pomocy algorytmu euklidesa, wersja nierekursywna}
var c:integer; {robocza}
begin
  c:=a mod b;   {dla ustalenia początkowej wartości c, zakładamy że b<>0}
  while c<>0 do
  begin
    c:=a mod b;
    a:=b;
    b:=c;
  end;    {while}
  nwd:=a;
end;

Poniżej znajduje się inny algorytm, który jest zapisany w języku 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

Kolejny algorytm, również w języku Ruby.

dla dwóch liczb

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

Prosty algorytm wyznaczający NWD zapisany w języku Python:

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

Powyższy algorytm (taki sam jak NWD w ActionScript) staje się pętlą nieskończoną gdy a \le 0 lub b \le 0 (w przeciwieństwie do poniższych algorytmów w C / C++).

Funkcja w C / C++ znajdująca NWD dwóch podanych w argumencie liczb:

/*Funkcja przyjmuje 2 liczby naturalne i zwraca NWD*/
int nwd(int a, int b)
{
int wynik;
 
 
                for(; ;)    // lub while(true), while(1)
                {
                if (b!=0)
                        {
                        wynik = a % b;
                        a = b;
                        b = wynik;
                        }
                else if (b==0)
                        {
                         wynik = a;
                         break;
                        }
                }
 
       return wynik;
}
 
//lub rekurencyjna:
 
int nwd(int m, int n){
    if (n!=0)
         return nwd(n, m%n);
    return m;
}

NWD w Scheme`ie

(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))))

NWD w symulatorze 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

NWD w ActionScript:

function nwd(a, b) {
  while (a != b) {
    if (a>b) {
      a -= b;
    } else {
      b -= a;
    }
  }
  return a;
}

[edytuj] Rozszerzony algorytm Euklidesa

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

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;
   }

C/C++|

#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;
}
Źródło „http://pl.wikisource.org/wiki/Algorytm_Euklidesa/kod”
Utwórz książkę