•Buatlah algoritma iteratif dan rekursif
untuk menghitung gcd dari dua bilangan bulat positif.
•Analisis :
•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.
1. Rekursif
#include <iostream>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int gcd(int c, int d){
int r;
while (d>0){
r=c%d;
c=d;
d=r;
}
}
int main(int argc, char** argv) {
int a, b;
cout<<"masukan angka : ";cin>>a;
cout<<"masukan angka lagi : ";cin>>b;
cout<<"hasil gcd = "<<gcd(a,b)<<endl;
return 0;
}/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int gcd(int c, int d){
int r;
while (d>0){
r=c%d;
c=d;
d=r;
}
}
int main(int argc, char** argv) {
int a, b;
cout<<"masukan angka : ";cin>>a;
cout<<"masukan angka lagi : ";cin>>b;
cout<<"hasil gcd = "<<gcd(a,b)<<endl;
return 0;
2. iteratif
#include <iostream>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int gcd(int c, int d)
{
if (d==0) return (c);
if (c<d) return (gcd(d,c));
return (gcd(c-d,d));
}
int main(int argc, char** argv) {
int a, b;
cout<<"masukan angka : ";cin>>a;
cout<<"masukan angka lagi : ";cin>>b;
cout<<"hasil gcd : "<<gcd(a,b)<<endl;
return 0;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int gcd(int c, int d)
{
if (d==0) return (c);
if (c<d) return (gcd(d,c));
return (gcd(c-d,d));
}
int main(int argc, char** argv) {
int a, b;
cout<<"masukan angka : ";cin>>a;
cout<<"masukan angka lagi : ";cin>>b;
cout<<"hasil gcd : "<<gcd(a,b)<<endl;
return 0;
}
Tampilan
keeduanya memiliki tampian output yang sama
