數(shù)值的整數(shù)次方——11

   實(shí)現(xiàn)函數(shù)double Power(double base, int exponent)，求base的exponent次方。不得使用庫(kù)函數(shù)，同時(shí)不需要考慮大數(shù)問(wèn)題。

    首先可以想到的是，如果exponent是個(gè)大于零的數(shù)，可用循環(huán)來(lái)進(jìn)行相乘，而如果exponent是個(gè)復(fù)數(shù)，依然可以將base進(jìn)行相乘，最后再取其倒數(shù)也就是用1去除以相乘結(jié)果。程序設(shè)計(jì)如下：

#include <iostream>
#include <math.h>
using namespace std;

double my_pow(double base, int exp)
{
    if(exp == 0)//當(dāng)exp為0的時(shí)候，不論base為多少結(jié)果都為1
        return 1;
    if((base == 0) || (base == 1))//當(dāng)base為0或者1的時(shí)候不論exp為多少結(jié)果都為base
        return base;

    double ret = 1.0;
    int flag = 1;//設(shè)定標(biāo)志位，判斷exp的正負(fù)性
    if(exp < 0)
    {
        flag = 0;
        exp *= (-1);
    }
    while(exp--)
    {
        ret *= base;
    }
    if(flag == 0)
        ret = 1/ret;
    return ret;
}

int main()
{
    double base = 6.123784;
    int exp = -5;
    double ret = my_pow(base, exp);
    cout<<"my_pow ret: "<<ret<<endl;
    cout<<"pow ret: "<<pow(base, exp)<<endl;
    return 0;
}

上面的栗子中，為了驗(yàn)證結(jié)果的正確性與否在輸出結(jié)果的比較中調(diào)用了庫(kù)函數(shù)的pow來(lái)進(jìn)行比較，運(yùn)行程序得結(jié)果：

    但是上面的代碼還是有可優(yōu)化的成分的，比如如果exp的值比較大，那么循環(huán)的次數(shù)也就比較多，這個(gè)時(shí)間復(fù)雜度就為O(N)，如果exp的值為100的話，那么其實(shí)，當(dāng)循環(huán)乘到50的時(shí)候，只需要再乘上一個(gè)50就能得到結(jié)果，而不需要再循環(huán)50次，而50又可以由相乘25次的結(jié)果再自乘一次得到，而25次的結(jié)果又可以由12次的結(jié)果乘以自身再乘一個(gè)base而得到......因此，將上面的代碼改為如下：

double GetPow(double base, int exp)
{
    double ret = 1;
    if(exp != 0)
    {   
        ret = GetPow(base, exp>>1);
        if((exp & 0x1) == 0)
        {
            ret *= ret;
        }
        else
        {
            ret *= (ret * base);
        }   
    }   
    return ret;
}

double my_pow(double base, int exp)
{ 
    if((base == 0) || (base == 1)) 
        return base;

    int flag = 1;
    if(exp < 0)
    {   
        flag = 0;
        exp *= (-1);
    }   

    double ret = GetPow(base, exp);

    if(flag == 0)
        ret = 1/ret;
    return ret;
}

解釋一下上面的GetPow函數(shù)，因?yàn)榍懊嬲f(shuō)可以將循環(huán)次數(shù)減少，比如100次方可以求50次方再平方，50次方可以求25次方再平方......以此類推，其實(shí)就是100->50->25->12(+1)->6->3->1(+1)->0，而我們從最低位倒著算起，base的0次方->base的1次方->base的3次方->base的6次方->base的12次方->......這樣可以發(fā)現(xiàn)，其實(shí)就是在exponent的二進(jìn)制表示位上進(jìn)行的操作，從最高位到最低位，當(dāng)比特位值為1時(shí)，就將前面的結(jié)果相乘再乘上一個(gè)base也就是上面的（+1），如果比特位值為0，就直接將前面的結(jié)果相乘......而從高位到低位就需要用遞歸來(lái)獲??；

運(yùn)行程序，結(jié)果和pow庫(kù)函數(shù)相同。

《完》