学步园

一、 题目

题目说的很清楚，就是实现pow()函数。

二、 分析

看到题目后，首先想到一个个算，心想应该会超时，果不其然。想到了二分法，这样减少了不少的运算。没有什么难度的思路。

虽然思路是二分，但是又有不同的实现形式。下面使用三种》

while实现：

class Solution {
public:
    double pow(double x, int n) {
        if(n == 0)
        	return 1.0;
        if(n == 1)
        	return x;
        int nflag = abs(n);
        int nflag2 = nflag;

        double xflag = abs(x);
        double xflag2 = xflag;

        int s = 1;
        while(nflag / 2 > 0){
        	xflag2 = xflag2 * xflag2;
        	nflag = nflag / 2;
        	s = s * 2;
        }
        xflag2 = xflag2 * pow(xflag, nflag2 - s);

        if(x < 0 && n % 2 == 1)
        	xflag2 = -xflag2;
        if(n < 0)
        	xflag2 = 1 / xflag2;
        return xflag2;
    }
};

递归实现一：

class Solution {
public:
    double pow_help(double x, int n) {
        if(n == 0)
        	return 1;
        double v = pow_help(x,n/2);
        if(n % 2 == 0)
        	return v * v;
       	else
       		return v * v * x;
    }
public:
    double pow(double x, int n) {
        if(n < 0)
        	return 1 / pow_help(x,-n);
        else
        	return pow_help(x,n);
    }
};

递归实现二：

class Solution {
public:
    double pow(double x, int n) {
    	if(n == 0)
    		return 1.0;
    	double res = pow(x,n/2);
    	if(n % 2 != 0){
    		if(n > 0)
    			return (res * res * x);
    		else
    			return (res / x * res);
    	}
    	return (res * res);
    }
};