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