實現(xiàn)函數(shù)double Power(double base, int exponent),求base的exponent次方。不得使用庫函數(shù),同時不需要考慮大數(shù)問題。
讓客戶滿意是我們工作的目標(biāo),不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶,將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴,公司提供的服務(wù)項目有:域名申請、虛擬空間、營銷軟件、網(wǎng)站建設(shè)、江孜網(wǎng)站維護(hù)、網(wǎng)站推廣。
首先可以想到的是,如果exponent是個大于零的數(shù),可用循環(huán)來進(jìn)行相乘,而如果exponent是個復(fù)數(shù),依然可以將base進(jìn)行相乘,最后再取其倒數(shù)也就是用1去除以相乘結(jié)果。程序設(shè)計如下:
#include <iostream> #include <math.h> using namespace std; double my_pow(double base, int exp) { if(exp == 0)//當(dāng)exp為0的時候,不論base為多少結(jié)果都為1 return 1; if((base == 0) || (base == 1))//當(dāng)base為0或者1的時候不論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; }
上面的栗子中,為了驗證結(jié)果的正確性與否在輸出結(jié)果的比較中調(diào)用了庫函數(shù)的pow來進(jìn)行比較,運行程序得結(jié)果:
但是上面的代碼還是有可優(yōu)化的成分的,比如如果exp的值比較大,那么循環(huán)的次數(shù)也就比較多,這個時間復(fù)雜度就為O(N),如果exp的值為100的話,那么其實,當(dāng)循環(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的二進(jìn)制表示位上進(jìn)行的操作,從最高位到最低位,當(dāng)比特位值為1時,就將前面的結(jié)果相乘再乘上一個base也就是上面的(+1),如果比特位值為0,就直接將前面的結(jié)果相乘......而從高位到低位就需要用遞歸來獲?。?/p>
運行程序,結(jié)果和pow庫函數(shù)相同。
《完》
本文標(biāo)題:數(shù)值的整數(shù)次方——11
文章網(wǎng)址:http://bm7419.com/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)