👋Hi~ o(￣▽￣)ブ這里是豬豬程式員
👀 很高興見到你O(∩_∩)O！
🌱 現在正在發芽中…
💞? 博主水平有限，如果發現錯誤，一定要及時告知作者哦 o(￣︶￣)o！感謝感謝！
📫博主的碼云 gitee，平常博主寫的程式代碼都在里面，
??這是一個新的專欄??我希望自己能夠堅持把《劍指offer》這本書的題目刷完，
劍指 Offer 16. 數值的整數次方
- 方法一:直接求解（超出時間限制）
- 方法二:使用遞回（執行用時：0 ms 記憶體消耗：5.3 MB）
- 方法三:二分思想（執行用時：0 ms 記憶體消耗：5.3 MB）
??題目來源
實作
pow(x, n) ，即計算 x 的 n 次冪函式（即，
x^n），不得使用庫函式，同時不需要考慮大數問題，
示例 1：
輸入：x = 2.00000, n = 10
輸出：1024.00000
示例 2：
輸入：x = 2.10000, n = 3
輸出：9.26100
示例 3：
輸入：x = 2.00000, n = -2
輸出：0.25000
解釋：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
方法一:直接求解（超出時間限制）
最簡單的方法就是讓n個x相乘，但這樣會超出時間限制,而且我寫的很冗余—！！！！
double myPow(double x, int n){
double t = 1.0; int i = n;
if (x > 0)
{
if (n > 0)
{
for (i = 0; i < n; i++)
{
t *= x;
}
}
else if (n == 0)
{
t = 1;
}
else
{
for (i = 0; i < -n; i++)
{
t /= x;
}
}
}
else if (x == 0)
{
t = 0;
}
else
{
if (n > 0)
{
for (i = 0; i < n; i++)
{
t *= x;
}
}
else if (n == 0)
{
t = 1;
}
else
{
for (i = 0; i < -n; i++)
{
t /= x;
}
}
}
return t;
}
方法二:使用遞回（執行用時：0 ms 記憶體消耗：5.3 MB）
演算法
演算法流程：
- n=0時，任何x都回傳1
- n=1時，回傳x
- n=-1時，回傳1/x
- 對于其他n值：
1.1 當n為偶數時，myPow(x,n) = myPow(x,n/2)* myPow(x,n/2)
1.2 當n為奇數時：myPow(x,n) = myPow(x,(n-1)/2) * myPow(x,(n-1)/2) * x
遞回時先用一個變數取得myPow(x,n/2)的值再平方，可以降低時間復雜度（減少遞回呼叫的次數）
double myPow(double x, int n){
double t=1;
if(n==0)return 1;
else if(n==1)return x;
else if(n==-1)return 1/x;
else
{
if(n%2==0)
{
t=myPow(x,n/2)*myPow(x,n/2);
}
else
{
t=x*myPow(x,(n-1)/2)*myPow(x,(n-1)/2);
}
}
return t;
}
方法三:二分思想（執行用時：0 ms 記憶體消耗：5.3 MB）
通過二分的思想，我們可以通過x = x^2的操作將冪指數n降低至n/2，直到n=0為止，這樣相比于一次一次乘效率提高了不少，因為使用單次累乘每進行一次冪指數n降低至n-1，而二分累乘冪指數n降低至n/2，
既然是對冪指數n除2操作，那不得不考慮這個n是奇數還是偶數，如果n為偶數，x^n =x^ (2)n/2；如果n為奇數xn =x*x^ (2)(n-1)/2
double myPow(double x, int n){
int i = 0;
double ret = 1.0;
long m = n;//如果n為最小負數，對n取絕對值后會溢位，所以需要long型變數來儲存
if (x == 1 || n == 0)
return 1.0;
if (x == 0)
return 0;
if (n < 0)
{
m = -m;
x = 1 / x;
}
while (m)
{
if (m & 1)
{
ret *= x;//如果n為奇數，對結果補乘一個x；如2的5次方可以轉換成4的2次方再乘2
}
m >>= 1;
x *= x;
}
return ret;
}
對于上述while回圈的代碼我初看的時候其實沒有看懂，但我自己舉了一個例子之后發現就清晰很多了，如果大家不明白的話也可以自己動手舉例子！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/299516.html
標籤：java
上一篇：HTML+CSS+JS實作 ??愛心文字3D旋轉影片特效??
下一篇：Java中的類和物件