Implement pow(x, n).
采用分治思想。
对于n是奇数时，x^n = x^（n/2）* x^（n/2）* x
对于n是偶数时，x^n = x^（n/2）* x^（n/2）
x^（n/2）用一个变量sub记录，x^n = sub * sub * x^(n % 2) 这样 x^（n/2）就计算一次
注意：n有可能是负数 转换为 1.0 / pow(x, -n) 此时-n有可能溢出 n 逐渐减半的过程中就会解决溢出问题。
class Solution {
public:
double pow(double x, int n) {
// 终止条件
if(n < 0){
return 1.0 / pow(x,-n);
}//if
if(n == 0){
return 1.0;
}//if
if(n == 1){
return x;
}//if
// 递归
// x^n = x^(n/2) * x^(n/2) *x^(n%2)
double sub = pow(x,n / 2);
return sub * sub * pow(x,n % 2);
}
};
/*********************************
* 日期：2015-01-29
* 作者：SJF0115
* 题目: 50.Pow(x, n)
* 网址：https://oj.leetcode.com/problems/powx-n/
* 结果：AC
* 来源：LeetCode
* 博客：
**********************************/
#include <iostream>
using namespace std;
class Solution {
public:
double pow(double x, int n) {
// 负数
if(n < 0){
return 1.0 / pows(x,-n);
}//if
// 正数
else{
return pows(x,n);
}
}
private:
double pows(double x,int n){
// 终止条件
if(n == 0){
return 1.0;
}//if
if(n == 1){
return x;
}//if
// 递归
// x^n = x^(n/2) * x^(n/2) *x^(n%2)
double sub = pow(x,n / 2);
return sub * sub * pow(x,n % 2);
}
};
int main(){
Solution solution;
double x = 2.5;
int n = 2;
double result = solution.pow(x,n);
// 输出
cout<<result<<endl;
return 0;
}
原文：http://blog.csdn.net/sunnyyoona/article/details/43273933