Pow(x, n)

Implementpow(x,n).

Example 1:

Input:
 2.00000, 10

Output:
 1024.00000

Example 2:

Input:
 2.10000, 3

Output:
 9.26100

Solution:

递归公式为：x^n = x^(n/2) * x^(n/2) * x^(n%2)

我们可以用递归来折半计算，每次把n缩小一半，这样n最终会缩小到0，任何数的0次方都为1，这时候我们再往回乘，如果此时n是偶数，直接把上次递归得到的值返回即可，如果是奇数，则还需要乘上个x的值。还有一点需要引起我们的注意的是n有可能为负数，对于n是负数的情况，我们可以先用其绝对值计算出一个结果再取其倒数即可

class Solution(object):
    def myPow(self, x, n):
        if n == 0:
            return 1.0
        elif n < 0:
            return 1 / self.myPow(x, -n)
        elif n % 2 == 1:
            return self.myPow(x*x,n/2)*x
        else:
            return self.myPow(x*x,n/2)

Simple Solution: Only python support that way.

class Solution:
    # @param x, a float
    # @param n, a integer
    # @return a float
    def pow(self, x, n):
        return x**n