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

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

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：域名申請、虛擬空間、營銷軟件、網(wǎng)站建設(shè)、江孜網(wǎng)站維護、網(wǎng)站推廣。

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

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

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

    double ret = 1.0;
    int flag = 1;//設(shè)定標志位，判斷exp的正負性
    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;
}

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

    但是上面的代碼還是有可優(yōu)化的成分的，比如如果exp的值比較大，那么循環(huán)的次數(shù)也就比較多，這個時間復雜度就為O(N)，如果exp的值為100的話，那么其實，當循環(huán)乘到50的時候，只需要再乘上一個50就能得到結(jié)果，而不需要再循環(huán)50次，而50又可以由相乘25次的結(jié)果再自乘一次得到，而25次的結(jié)果又可以由12次的結(jié)果乘以自身再乘一個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ù)，因為前面說可以將循環(huán)次數(shù)減少，比如100次方可以求50次方再平方，50次方可以求25次方再平方......以此類推，其實就是100->50->25->12(+1)->6->3->1(+1)->0，而我們從最低位倒著算起，base的0次方->base的1次方->base的3次方->base的6次方->base的12次方->......這樣可以發(fā)現(xiàn)，其實就是在exponent的二進制表示位上進行的操作，從最高位到最低位，當比特位值為1時，就將前面的結(jié)果相乘再乘上一個base也就是上面的（+1），如果比特位值為0，就直接將前面的結(jié)果相乘......而從高位到低位就需要用遞歸來獲??；

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

《完》

本文標題：數(shù)值的整數(shù)次方——11
文章網(wǎng)址：http://muchs.cn/article24/iiocce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、動態(tài)網(wǎng)站、網(wǎng)站收錄、靜態(tài)網(wǎng)站、外貿(mào)建站、全網(wǎng)營銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)