Program GCD dengan perulangan rekursif

Selamat datang kembali di postingan flowchart program!!
Pada postingan kali ini saya akan menampilkan flowchart program untuk menghitung nilai GCD dari dua buah nilai inputan. Berikut ini adalah contoh kasusnya :

Nilai pertama : n
Nilai kedua : m

Jika n ≠ 0 dan m integer non negatif, kita dapat menulis : m = q.n + r
untuk suatu integer non negatif q dan r dengan 0 ≤ r < n.
contoh (190,34) :
34 | 190  190 = 5(34) + 20, r = 20
20 | 34  34 = 1(20) + 14, r = 14
14 | 20  20 = 1(14) + 6, r = 6
6 | 14  14 = 2(6) + 2, r = 2
2 | 6  6 = 3(2) + 0, r = 0 stop !
•gcd didefinisikan sebagai berikut :

gcd(c,d) = c, jika d = 0

= gcd(c-d, d), jika d > 0 dan c > d.

•berlaku hukum komutatif, gcd(c,d) = gcd(d,c).
Berikut ini adalah programnya :
Flowchart :
Main():
Procedur :
Berikut ini adalah versi C++ nya :
#include <iostream>
#include <conio.h>

using namespace std;

class hitung{
friend istream& operator>>(istream&, hitung&);
friend ostream& operator<<(ostream&, hitung&);
public:
int gcd(int c, int d);
private:
int x,y;
};

int hitung::gcd (int c,int d){

if (d==0)
{
cout << "Nilai GCD = "<<c << endl;      }
else
{
if (c<d)
{
gcd(d,c);
}
else
{
gcd(c-d,d);
}
}
};

istream& operator>>(istream& in, hitung& input){
cout<<"Masukkan nilai pertama : ";
in>>input.x;
cout<<"Masukkan nilai kedua : ";
in>>input.y;
};

ostream& operator<<(ostream& out, hitung& output){
output.gcd(output.x,output.y);
};
int main()
{
hitung jalankan;
cin>>jalankan;
cout<<jalankan;

getch();
}


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s