求最大公約數的3個實現
實現代碼:
/// 求最大公約數(歐幾里德算法/輾轉相除法)(遞歸)
int gcd1(int m, int n)
{
if (n == 0) return m;
else return gcd1(n, m%n);
}
/// 求最大公約數(歐幾里德算法/輾轉相除法)(迭代)
int gcd2(int m, int n)
{
int r = 0;
while (n != 0)
{
r = n;
n = m % n;
m = r;
}
return m;
}
/// 求最大公約數(更相減損法)
int gcd3(int m, int n)
{
while (m != n)
{
if (m > n) m -= n;
else n -= m;
}
return m;
}
測試代碼:
int _tmain(int argc, _TCHAR* argv[])
{
int nGcd = gcd1(16, 40);
assert(nGcd == 8);

nGcd = gcd2(16, 40);
assert(nGcd == 8);

nGcd = gcd3(16, 40);
assert(nGcd == 8);

system("pause");
return 0;
}
/// 求最大公約數(歐幾里德算法/輾轉相除法)(遞歸)
int gcd1(int m, int n)
{
if (n == 0) return m;
else return gcd1(n, m%n);
}
/// 求最大公約數(歐幾里德算法/輾轉相除法)(迭代)
int gcd2(int m, int n)
{
int r = 0;
while (n != 0)
{
r = n;
n = m % n;
m = r;
}
return m;
}
/// 求最大公約數(更相減損法)
int gcd3(int m, int n)
{
while (m != n)
{
if (m > n) m -= n;
else n -= m;
}
return m;
}測試代碼:
int _tmain(int argc, _TCHAR* argv[])
{
int nGcd = gcd1(16, 40);
assert(nGcd == 8);
nGcd = gcd2(16, 40);
assert(nGcd == 8);
nGcd = gcd3(16, 40);
assert(nGcd == 8);
system("pause");
return 0;
}posted on 2014-05-27 10:28 楊粼波 閱讀(691) 評論(0) 編輯 收藏 引用 所屬分類: C++




