[python3] 16 数值的整数次方

代码涉及的python3和python2之间的区别仅仅在于print函数是否有括号，在牛客网的python2环境下不需要print任何输出，因此不影响。

题目描述, 不用库函数如何求乘方，以a^n为例

1 若不考虑效率问题，也不考虑错误输入和特殊用例的问题，对a求n次方，即求n次a相乘之后的结果。

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        result = 1
        for i in range(exponent):
            result *= base
        return result
if __name__ == "__main__":
    ss = Solution()
    print (ss.Power(2, 4)) #16

2. 若考虑效率问题，不考虑错误输入和特殊用例的问题，则a^n =(a^(n/2) )* (a^(n/2) ), n为偶数；a^n =(a^((n-1)/2) )*(a^((n-1)/2) ) * a, n为奇数。这个公式可以采用递归的方式实现。递归时需要考虑递归终止条件，在这里即为n == 1, 若n == 1, 则返回a。

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        if exponent == 0:
            return 1
        if exponent == 1:
            return base
        result = self.Power(base, exponent>>1) #exponent>>1相当于exponent/2
        result *= result
        if exponent & 1 == 1: #若exponent是奇数，则在上面的基础上需要再乘以一个base
            result *= base
        return result

if __name__ == "__main__":
    ss = Solution()
    print (ss.Power(2, 5)) #32

3. 若考虑效率问题，同时考虑错误输入和特殊用例的问题。这里的底数和指数不一定总是为正数，也可能是负数和0. 若底数为负数，无论指数是什么，都和正数的乘方一样求得。若底数为0，指数为0，则正常计算为1；若底数为0，指数为正，正常计算为0；若底数为0，指数为负，先求0**(abs(n)), 然后求倒数，0不能作为分母，因此这种情况为错误输入。若底数为正，指数为正，则正常计算；若底数为正，指数为0，则正常计算为1；若底数为正，指数为负，则先计算指数的绝对值 次幂，然后对计算结果求倒数。综上所述，异常输入为底数为0，指数为负的情况。

0^0 = 1

对于异常输入，有三种措施来告知函数调用者，你的输入有问题啦~三种措施分别为返回值，全局变量，和抛出异常。在这里以全局变量返回为例。

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        g_InvalidInput = False
        if base == 0 and exponent < 0:
            g_InvalidInput = True #此时需要函数调用者自己检查g_InvalidInput的返回值，来判断是否输入异常
            return 0

        absExponent = exponent
        if exponent < 0: #若输入的指数为负数，则先计算指数为其绝对值时的值，然后计算结果的倒数
            absExponent = -exponent
        result = self.PowerWithUnsignedExponent(base, absExponent)

        if exponent < 0:
            result = 1/result
        return result
    
    # 不考虑非法输入，不考虑指数为负数时，计算乘方
    def PowerWithUnsignedExponent(self, base, exponent):
        # write code here
        if exponent == 0: #任何底数的0次幂都等于1
            return 1
        if exponent == 1: #递归终止条件
            return base
        result = self.PowerWithUnsignedExponent(base, exponent>>1) #exponent>>1相当于exponent/2
        result *= result
        if exponent & 1 == 1: #若exponent是奇数，则在上面的基础上需要再乘以一个base
            result *= base
        return result

if __name__ == "__main__":
    ss = Solution()
    g_InvalidInput = False
    base = 2
    exponent = -5
    result = ss.Power(base, exponent)
    if g_InvalidInput == True:
        print ("Invalid Input!!!")
    print ("%s ^ %s = %s" %(base, exponent, result))

正确运行