以上內容摘自《編程之美》P150-154。
為了方便使用，下面是可拷貝的代碼：
Math.h
#pragma once
class Math
{
public:
Math(void);
~Math(void);
public :
//編程之美P150-154
//求最大公約數，歐幾里德——輾轉相除法
static int Gcd1(int x, int y);
//求最大公約數，歐幾里德——輾轉相除法（變相將除法變成了減法）
static int Gcd2(int x, int y);
static int Gcd3(int x, int y);
inline static bool IsEven(int x);
inline static int Absolute(int x);
};
Math.cpp
#include "Math.h"
Math::Math(void)
{
}
Math::~Math(void)
{
}
int Math::Gcd1(int x, int y)
{
//y, x%y順序不能錯；
return y ? Gcd1(y, x % y) : x;
}
int Math::Gcd2(int x, int y)
{
//與Gcd1相同的方式，但由于x%y計算速度較x-y要慢，但效果相同，所以換用x - y
// 但用減法和除法不同的是，比如和，%20=10，-20=70，也就是-4×=10
// 也就是說迭代次數較Gcd1而言通常是增加了。
return y ? Gcd1(y, x - y) : x;
}
int Math::Gcd3(int x, int y)
{
if(x < y)
return Gcd3(y, x);
if(y == 0)
return x;
else
{
if(IsEven(x))
{
if(IsEven(y))
return (Gcd3(x >> 1, y >> 1) << 1);
else
return Gcd3(x >> 1, y);
}
else
{
if(IsEven(y))
return Gcd3(x, y >> 1);
else
return Gcd3(y, x - y);
}
}
}
bool Math::IsEven(int x)
{
return !(bool)x & 0x0001;
}
int Math::Absolute(int x)
{
return x < 0 ? -x : x;
}
Main.cpp
#include <stdafx.h>
#include <iostream>
#include "Math.h"
using namespace std;
int _tmain(const int & arg)
{
cout<<"Math::Gcd1(42,30) = "<<Math::Gcd1(42,30)<<endl;
cout<<"Math::Gcd1(30,42) = "<<Math::Gcd1(30,42)<<endl;
cout<<"Math::Gcd1(50,50) = "<<Math::Gcd1(50,50)<<endl;
cout<<"Math::Gcd1(0,0) = "<<Math::Gcd1(0,0)<<endl;
cout<<"Math::Gcd1(-42,-30) = "<<Math::Gcd1(-42,-30)<<endl;
cout<<"Math::Gcd1(-42,30) = "<<Math::Gcd1(-42,30)<<endl;
cout<<"------------------------------"<<endl;
cout<<"Math::Gcd2(42,30) = "<<Math::Gcd2(42,30)<<endl;
cout<<"Math::Gcd2(30,42) = "<<Math::Gcd2(30,42)<<endl;
cout<<"Math::Gcd2(50,50) = "<<Math::Gcd2(50,50)<<endl;
cout<<"Math::Gcd2(0,0) = "<<Math::Gcd2(0,0)<<endl;
cout<<"Math::Gcd2(-42,-30) = "<<Math::Gcd2(-42,-30)<<endl;
cout<<"Math::Gcd2(-42,30) = "<<Math::Gcd2(-42,30)<<endl;
cout<<"------------------------------"<<endl;
cout<<"Math::Gcd3(42,30) = "<<Math::Gcd3(42,30)<<endl;
cout<<"Math::Gcd3(30,42) = "<<Math::Gcd3(30,42)<<endl;
cout<<"Math::Gcd3(50,50) = "<<Math::Gcd3(50,50)<<endl;
cout<<"Math::Gcd3(0,0) = "<<Math::Gcd3(0,0)<<endl;
cout<<"Math::Gcd3(-42,-30) = "<<Math::Gcd3(-42,-30)<<endl;
cout<<"Math::Gcd3(-42,30) = "<<Math::Gcd3(-42,30)<<endl;
return 0;
}
不過有一點值得一提，就是所謂性能最好效率最高的Gcd3不支持負數，也就是最后兩行測試代碼無法通過。但是限于對負數的最大公約數并沒有定義，也就是說即便上面的Gcd1和Gcd2好像算出了負數，但它們的結果沒有意義。