GCD

Algoritma GCD (c,d : integer) : integer
Versi Iteratif	Versi Rekursif
Deskripsi While (d>0) do r < c mod d c  < d {menyimpan harga r terakhir} d < r {harga  r terakhir untuk menghentikan perulangan} end while gcd < c	Deskripsi if(d=0) then gcd < c else if (c<d) then gcd < gcd(d,c) else gcd < gcd (c, -d, d)

Listing

• Iteratif

#include <cstdlib>

#include <iostream>

#include <conio.h>

using namespace std;

class GCD{

friend ostream& operator<<(ostream&, GCD&);

friend istream& operator>>(istream&, GCD&);

public:

int HitungGCD(int,int);

private:

int x,y;

};

int GCD::HitungGCD(int c,int d){

int r;

while(d>0){

r=c%d;

c=d;

d=r;

}

return(c);

}

istream& operator>>(istream& in,GCD& a){

cout<<"MASUKKAN BILANGAN PERTAMA   : ";

in>>a.x;

cout<<"MASUKKAN BILANGAN KEDUA     : ";

in>>a.y;

return in;

}

ostream& operator<<(ostream& out, GCD& a){

out<<"GCD (" << a.x << "," << a.y << ") = ";

out<<a.HitungGCD(a.x,a.y);

return out;

}

int main(int argc, char *argv[])

{

GCD run;

cin>>run;

cout<<run;

getch();

return 0;

}

• Rekursif

int HitungGCD(int c, int d)

{

if(d==0)return(c);

if(c<d)return(HitungGCD(d,c));

return(HitungGCD(c-d, d));

}