huaxiazhihuo

 

有理数类的一点思考

        在写24点的程序时,要处理除法运算,不可避免地将引入小数点,但本人对于计算机中的浮点数实在没有太多的好感。权衡再三,终于决定下定决心写一个有理数类(以下简称为CRational),以解决除法运算这个问题。并且有理数这个类也是一个很好的C++练习题,可以用来练练手,以下将看到,它的实现虽然不难,但也不是很容易。有理数这个东西,属于用户自定义的数据类型,c++对此的支持,真可谓完美,既不失效率,又具备美观。c++可以让程序员做出来的自定义类型,其行为可以表现得好像是由语言层面实现的那个样子,不管从语法、安全、效率上讲。这一点,所有的语言都没法和c++媲美。
        不管怎么说,CRational的需求相当明确,它一定有分子、分母、然后支持加减乘除这四种运算,于是,一口气马上就能写下它的定义。
class CRational
{
public:
    CRational(
int nNumberator=0int nDenominator=1);
    
int Numberator()const return m_nNum;}
    
int Denominator()const return m_nDe;}

    CRational
& operator+=(const CRational& _Right);
    CRational
& operator-=(const CRational& _Right);
    CRational
& operator*=(const CRational& _Right);
    CRational
& operator/=(const CRational& _Right);
    CRational 
operator-()const    // 一元操作符,用以取反
    {
        
return CRational(-m_nNum, m_nDe);
    }


private:
    
int m_nNum;
    
int m_nDe;
}
;
         嗯,我承认代码很匈牙利,中MFC的毒太深。毋庸置疑,分子分母只能获取,不能设置,函数名中,没有加Get的前缀,实在是因为代码中它出现的地方太多了,所以能避免就尽量避免。没有涉及资源分配,析构函数可以忽略,拷贝构造函数和赋值函数也不用写了,编译器将会提供缺省的实现,足以满足我们的要求。貌似应该还要有一个返回求取小数值的操作,但是,这个类本身就是为了避免操作小数点,而且,计算小数点值可通过分子/分母的方法计算出来。总之,CRational的终极接口就是这个样子了。
        每个有理数都有一个标准的等价类,这个标准的有理数的分子、分母都不能再约分了,而且可以暂时假设符号位出现于分子中,分母则为正整数,比如说,3/6、-4/-8都等价于1/2,因此,在这个有理数类中,必须有一个标准化的操作,问题是,这个标准化函数是返回一个标准的有理数还是将有理数自身直接就标准化了。经过多方面的权衡,特别是为了兼容现有的整型变量(int, char, short等),整型变量可看成分母为1的有理数,我决定让CRational一直处于标准化的状态下,标准化的状态由CRational自己来维持,客户无须知道标准化的这个细节,因此,将void standarlize()声明于其private的区域下,其实现如下:
void CRational::standarlize()
{
    
if (m_nDe < 0)
    
{
        m_nDe 
= -m_nDe;
        m_nNum 
= -m_nNum;
    }

    
int nGcd = gcd(abs(m_nNum), m_nDe);
    m_nNum 
/= nGcd;
    m_nDe 
/= nGcd;
}

        其中,毫无疑问,gcd为最大公约数,gcd没有访问CRational的任何非静态(nonstatic)变量,因此,它必将不可成为CRational的非静态函数。将gcd声明为静态函数,虽然可避免污染全局空间,但也使得外部代码必须通过CRational来调用gcd函数,语法上不方便,而且,gcd本身就是一个独立性很强而且又通用的函数,从意义上,它也不应该属于CRational里面的东西。因此,gcd只能为全局函数。关于静态函数和全局函数的选择,鉴于“类的接口要尽可能的小”的原则和其他的一些问题,只要函数不访问类的静态变量,也不通过类的变量来访问到其非静态成员,它就应该是全局函数。全局函数是好东西,某些语言为了坚持所谓的纯粹的面向对象,故意不支持,实在让人用起来很不痛快,它的污染全局空间的问题,完全可以通过命名空间来解决。总之,只要可能的话,就应该将函数声明为全局函数,没什么不好。好了,请看gcd的实现。
unsigned int gcd(unsigned int x, unsigned int y)   
{   
    unsigned  
int  nTimes=0;   
    
for (; 0 == (x&1&& 0 == (y&1); x>>=1, y>>=1)
        
++nTimes;

    
if (x < y)
        swap(x, y);

    
while (y > 0)
    
{
        
for (; 0 == (x & 1 );x >>= 1 )
            ;   

        
if (x < y)
            swap(x, y);
        x 
-= y;
        
if (x < y)
            swap(x, y);
    }

    
return x << nTimes;
}
 
        其算法源于《编程之美》,可看成是非递归的版本。咦,怎么会这么长,与日常所见的到似乎不太一样,高效算法的代码貌似都会很长,好比strlen。再仔细看,里面居然没有取余的操作。嗯,它的算法核心,用移位和减法这两种快速的运算来替代取模这种慢速运算。
有了standarlize()之后,CRational的几个函数的实现如下所示:
CRational::CRational(int nNumberator, int nDenominator)
: m_nNum(nNumberator), m_nDe(nDenominator)
{
    assert(nDenominator 
!= 0);
    standarlize();
}


CRational
& CRational::operator+=(const CRational& _Right)
{
    m_nNum 
= m_nNum*_Right.m_nDe + _Right.m_nNum*m_nDe;
    m_nDe 
*= _Right.m_nDe;
    standarlize();
    
return *this;
}
……
        构造函数中,似乎应该检查分母为0的情况,然后抛出异常。但是,这属于契约使用的问题,用户违背的契约,一切后果,必须自己承担,我们的代码无须对此负责。
        此外,就是各种+、-、*、/、==、输出等各种全局运算符重载的操作了。得益于C++的缺省类型转换,我们不用再做其他事情,就可以很好地让我们的CRational很好地与融入到原有的各种整型世界中去。当然,为了效率起见,似乎有必要针对各种整型提供+、-、*、/的各种重载版本(complex就是这样做的),但在此,确实没有必要。缺省类型转换有时虽然会带来一些问题,但是,当确实需要它的时候,它就能发挥重大作用了。C++的各种特性就是这样,你可以不用,它也不打扰你(你要故意或无意用错,那也没办法),当真正需要到的时候,特性的威力就显示出来了。很多人之所以愿意沉迷于C++,就在于它不剥夺程序员的任何一点选择的权利。
ostream& operator << (ostream& outconst CRational& rat)
{
    cout 
<< rat.Numberator();
    
if (rat.Denominator() != 1)
        cout 
<<  "/" << rat.Denominator();
    
return out;
}


CRational 
operator+(const CRational& _Left, const CRational& _Right)
{
    CRational _Tmp(_Left);
    
return _Tmp += _Right;
}
……
        嗯,一再写这些入门级的文章,本座也很自觉有失身价,也算是对网络世界的一点回报吧。只要有一个人看了,能有所启发,在下就心满意足了,为免误人子弟,也欢迎有人批评指正。

posted on 2012-06-04 11:23 华夏之火 阅读(1318) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(6)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜