float daPower(float x,int n){float ret=1,tmp;if(n==1)return x;tmp=daPower(x,n>>1);ret=tmp*tmp;if(n&1)ret*=x;return ret;}
3 回答
回首憶惘然
TA貢獻(xiàn)1847條經(jīng)驗(yàn) 獲得超11個(gè)贊
float daPower(float x,int n)
這個(gè)代碼應(yīng)該是計(jì)算x的n次冪，不過(guò)寫的挺亂的
ret只是一個(gè)作為返回值的臨時(shí)變量而已，只是單詞“return”的縮寫（我是說(shuō)單詞return，和return語(yǔ)句沒(méi)關(guān)系）
float ret=1,tmp;
if(n==1)return x;//如果n為1，就代表是求某個(gè)數(shù)的1次冪，一個(gè)數(shù)的1次冪肯定是這個(gè)數(shù)本身，能理解吧
tmp=daPower(x,n>>1);//如果上條語(yǔ)句沒(méi)返回就到這里，n>>1就是右移一位，一般可以理解為n/2
ret=tmp*tmp;//上面是把n/2，可是求的還是次冪，所以要把結(jié)果再乘一次，例如x的10次冪等于，x的5次冪乘以x的5次冪，理解了嗎？
if(n&1)ret*=x;//這條語(yǔ)句的意思是，假設(shè)n是奇數(shù)，那么再乘一邊x，意思就是假設(shè)n為5，那么n>>2就為2，兩個(gè)x的2次冪相乘的結(jié)果是n的4次冪，我們要求5次冪，所以這里再乘一次
return ret;
總而言之??很莫名其妙的算法
Helenr
TA貢獻(xiàn)1780條經(jīng)驗(yàn) 獲得超4個(gè)贊
這是快速冪的求法~就是求實(shí)數(shù)x的n次方是多少
ret是一個(gè)返回值，最后返回的ret就是x的n次方
舉個(gè)最簡(jiǎn)單的例子：
比如我們要求2的100次方，常規(guī)做法是將2自乘100次，對(duì)吧？但這個(gè)程序只要乘7次就可以啦~（運(yùn)算級(jí)別降到了log2 100這么少?。?br/>它的運(yùn)行方法是：2^100=2^50×2^50，而2^50=2^25×2^25，以此類推，那么對(duì)于2^100來(lái)說(shuō)，我們只要用tmp記錄一個(gè)2^50，再返回tmp*tmp就可以了（也就是上述程序的ret=tmp*tmp的作用）
再解釋一下tmp=daPower(x,n>>1)的意思，n>>1的意思就是n二進(jìn)制中右移一位（什么那么復(fù)雜啦，就是除以2取整數(shù)嘛?。┮簿推鸬搅怂?^100只要算2^50次方（50由100>>1也就是除以2得到）的作用，至于最麻煩的if(n&1)ret*=x的話嘛~就是一種特殊情況：
首先if(n&1)是判斷n是不是奇數(shù)，（是把n轉(zhuǎn)成了二進(jìn)制，判斷最后一位是否是1，是1就表示是奇數(shù)，不信你試試奇數(shù)二進(jìn)制下最后一位是不是1？）如果是奇數(shù)就看下面：
比如我們算2^101,101不是偶數(shù)，不能單純地101>>1再自乘得到，而要算出2^50，然后再自乘一個(gè)2得到，也就是2^101=(2^50)×(2^50)*2，所以有了if(n&1)ret*=x;（相當(dāng)于ret=ret*x;）這一句話了~最后就返回個(gè)ret
再介紹點(diǎn)好玩的東西，為什么返回值是ret不是ter或者別的什么呢？因?yàn)閞eturn這個(gè)單詞前三個(gè)字母就是ret！為了方便記憶說(shuō)等一下我要返回值，所以很多人都把返回值用ret作變量！謝謝~
慕運(yùn)維8079593
TA貢獻(xiàn)1876條經(jīng)驗(yàn) 獲得超5個(gè)贊
float daPower(float x,int n)
{
float ret=1,tmp;
if(n==1)return x; //剩下1次方的時(shí)候，才是遞歸函數(shù)終止條件
tmp=daPower(x,n>>1);
ret=tmp*tmp;
if(n&1)ret*=x;
return ret;
}
這個(gè)函數(shù)是求 x^n，也就是x的n次方，ret就是所求的返回值，由于這個(gè)函數(shù)用了移位，和遞歸，理解這個(gè)算法上就需要一定的數(shù)學(xué)功底
隨便舉個(gè)例子
假設(shè)調(diào)用的是 float daPower(2.1, 31)，也就是2.1的31次方
這個(gè)算法的過(guò)程就是
float daPower(2.1,31)
{
float ret=1,tmp;
if(n==1)return x; //因?yàn)?n=31，所以此分支沒(méi)有進(jìn)來(lái)
tmp=daPower(x,n>>1); //n>>1就是n/2,所以tmp的值就是 2.1的15次方，遞歸調(diào)用
ret=tmp*tmp; //ret= tmp*tmp bn就是2.1的 30次方
if(n&1)ret*=x; //因?yàn)閚是31，所以此分支進(jìn)入 ret*=x; 也就是2.1的31次
return ret;
}
添加回答
舉報(bào)
0/150
提交
取消