以上内容摘自《编程之美》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好像算出了负数,但它们的结果没有意义。