題目描述
給定一個double型別的浮點數base和int型別的整數exponent，求base的exponent次方，
保證base和exponent不同時為0
解法1
最直接的思路，計算base的exponent次方，則將base連乘exponent次即可，時間復雜度為O(exponent)
但是要注意處理特殊情況：
- 如果底數base等于0則直接回傳0
- 非0數的0次方等于1
- 當指數為負數時的結果，相當于用1除以指數為正數時的結果
還有一個坑需要注意，下面的代碼中使用了long y = exponent;，需要將exponent轉換為long型別
是因為exponent可以等于-2147483648（int型別的最小值），如果直接進行-exponent操作，由于int型別的最大值是2147483647，則會導致越界，出現錯誤的結果
實作代碼
public double Power(double thebase, int exponent)
{
if(thebase == 0) return 0;
long y = exponent; // 避免越界
if(y < 0){
thebase = 1 / thebase;
y = -y;
}
double ret = 1;
for(double i = 0; i < y; i ++){
ret *= thebase;
}
return ret;
}
解法2
可以根據二分的思路，利用遞回每次求指數的一半的次方結果，然后再將遞回的結果相乘得到完整的指數次方
由于求指數的一半，即整數除以2的結果會自動向下取整，所以需要特殊處理指數為奇數時的情況，當指數為奇數時，需要在遞回結果相乘的基礎上再乘以一次底數
代碼中使用的位運算e >> 1相當于e / 2來計算指數的一半
代碼中通過位運算(e & 1) == 1 來判斷指數是奇數還是偶數（奇數的二進制表示最低位一定是1，偶數的二進制表示最低位一定是0），相當于(e % 2) == 1
使用位運算會有更快的執行效率
實作代碼
public double Power2(double thebase, int exponent)
{
if(thebase == 0) return 0;
if(exponent == 0) return 1;
long e = exponent; // 避免越界
if(exponent < 0){
e = - e;
thebase = 1 / thebase;
}
if(e == 1) return thebase;
double ret = Power2(thebase, (int)(e >> 1));
return (e & 1) == 1 ? thebase * ret * ret : ret * ret;
}
解法3
求解整數m的n次方，一般是mn = m * m * m .....，連乘n次，演算法復雜度是O(n)，這樣的演算法效率太低，我們可以通過減少相乘的次數來提高演算法效率，即快速冪
對于n我們可以用二進制表示，以14為例，14 = 1110
\[m^{14} = m^{1110} = m^{2^{3} * 1 + 2^{2} * 1 + 2^{1} * 1 + 2^{0} * 1} = m^{2^{3} * 1} * m^{2^{2} * 1} * m^{2^{1} * 1} * m^{2^{0} * 0} \]
\[= m^{8} * m^{4} * m^{2} * m^{0} = m^{8} * m^{4} * m^{2} * 1 \]
可以發現這樣的規律，指數n的二進制從低位到高位依次對應底數m的1次方，2次方，4次方，8次方...，當該二進制位是1的時候，則乘以底數對應的次方數，如果該二進制位是0，則不能乘以底數對應的次方數，即乘以1，
例如，m8對應的二進制位是1，所以最終結果中有m8
m1對應的二進制位是0，所以最終結果中只有m0，即1
使用快速冪后，原本需要的14次連乘，現在只需要4次連乘，
那么怎樣得到一個整數的二進制位呢，又怎樣判斷該二進制位是0還是1呢
可以使用與運算和右移運算，例如對于14 = 1110
- 和1按位與得到0，即第一個二進制位是0
- 1110右移一位，得到0111，和1按位與得到1，即第二個二進制位是1
- 0111右移一位，得到0011，和1按位與得到1，即第三個二進制位是1
- 0011右移一位，得到0001，和1按位與得到1，即第四個二進制位是1
- 0001右移一位，得到0000，等于0則，演算法結束
實作代碼
public double Power3(double thebase, int exponent)
{
if(thebase == 0) return 0;
long y = exponent; // 避免越界
if(y < 0){
thebase = 1 / thebase;
y = -y;
}
double ret = 1;
while(y > 0){
if((y & 1) == 1){
ret *= thebase;
}
thebase *= thebase;
y >>= 1;
}
return ret;
}
更多演算法題目的完整描述，AC代碼，以及解題思路可以查看GitHub倉庫Algorithm
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/49173.html
標籤：C#
上一篇：關于ListViewItem的SubItems默認存在一條空白子項
下一篇：c#方法