本文轉載自【微信公眾號：五角錢的程式設計師，ID:xianglin965】經微信公眾號授權轉載，如需轉載與原文作者聯繫
文章目錄
16. 數值的整數次方題目連結題目描述解題思路實現代碼
16. 數值的整數次方
題目連結
NowCoder
題目描述
給定一個 double 類型的浮點數 base 和 int 類型的整數 exponent，求 base 的 exponent 次方。
解題思路
下面的討論中 x 代表 base，n 代表 exponent。
比如，我們求n的32次方，我們先知道n的16次方，在16次方的基礎上再平方就可以，同理，我們可以先求8次方，4次方，2次方，因此我們求32次方就變成了先求平方，在此基礎上求4次方，再求8次方，再求16次方，最後就可以求得32次方。
我們提出如下的公式：
因為(x*x)n/2可以通過遞歸求解，並且每次遞歸n都減小一半，因此整個算法的時間複雜度為O(logN)。
實現代碼
package 數值的整數次方;
/*
作者 :XiangLin
文件 :Solution.java
IDE :IntelliJ IDEA
*/
public class Solution {
public double power(double base,int exponent){
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
boolean isNagivate = false;
if (exponent < 0){
isNagivate = true;
exponent = -exponent;
}
double pow = power(base * base,exponent/2);
if (exponent % 2 != 0){
pow = pow * base;
}
return isNagivate? 1 / pow : pow;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.power(2.2,5));
}
}