python实现pow函数（求n次幂，求n次方）

冷不防 2022-10-08 02:28 217阅读 0赞

实现 pow(x, n)，即计算 x 的 n 次幂函数。其中n为整数。

**解法1：暴力法**

不是常规意义上的暴力，过程中通过动态调整底数的大小来加快求解。

代码如下：

class Solution:
        def myPow(self, x: float, n: int) -> float:
            judge = True
            if n<0:
                n = -n
                judge = False
            if n==0:
                return 1
            final = 1     # 记录当前的乘积值
            tmp = x       # 记录当前的因子
            count = 1     # 记录当前的因子是底数的多少倍
            while n>0:
                if n>=count:
                    final *= tmp  
                    tmp = tmp*x
                    n -= count
                    count +=1  
                else:
                    tmp /= x
                    count -= 1
            return final if judge else 1/final

**解法2：根据奇偶幂分类（递归法，迭代法，位运算法）**

*  如果n为偶数，则pow(x,n) = pow(x^2, n/2)；
 *  如果n为奇数，则pow(x,n) = x\*pow(x, n-1)。

递归代码实现如下：

class Solution:
        def myPow(self, x: float, n: int) -> float:
            if n<0:
                n = -n
                return 1/self.help_(x,n)
            return self.help_(x,n)
    
        def help_(self,x,n):
            if n==0:
                return 1
            if n%2 == 0:  #如果是偶数
                return self.help_(x*x, n//2)
            # 如果是奇数
            return self.help_(x*x,(n-1)//2)*x

迭代代码如下：

''' Python大型免费公开课，适合初学者入门 加QQ群：579817333 获取学习资料及必备软件。 '''
    class Solution:
        def myPow(self, x: float, n: int) -> float:      
            judge = True
            if n < 0:
                n = -n
                judge = False     
            final = 1
            while n>0:
                if n%2 == 0:
                    x *=x
                    n //= 2
                final *= x
                n -= 1
            return final if judge else 1/final

其实跟上面的方法类似，只是通过位运算符判断奇偶性并且进行除以2的操作（移位操作）。

代码如下：

class Solution:
        def myPow(self, x: float, n: int) -> float:      
            judge = True
            if n < 0:
                n = -n
                judge = False      
            final = 1
            while n>0:
                if n & 1:   #代表是奇数
                    final *= x
                x *= x
                n >>= 1     # 右移一位
            return final if judge else 1/final

**类型二：求n开方**

实现 pow(x, n)，即计算 x 的 n 次幂函数。其中x大于0，n为大于1整数。

解法：二分法求开方

思路就是逐步逼近目标值。以x大于1为例：

1.  设定结果范围为\[low, high\]，其中low=0, high = x，且假定结果为r=(low+high)/2；
2.  如果r的n次方大于x，则说明r取大了，重新定义low不变，high= r，r=(low+high)/2；
3.  如果r的n次方小于x，则说明r取小了，重新定义low=r，high不变，r=(low+high)/2；

代码如下：

class Solution:
        def myPow(self, x: float, n: int) -> float: 
            # x为大于0的数,因为负数无法开平方（不考虑复数情况）
            if x>1: 
                low,high = 0,x
            else:
                low,high =x,1
            while True:
                r = (low+high)/2
                judge = 1
                for i in range(n):
                    judge *= r
                    if x >1 and judge>x:break # 对于大于1的数，如果当前值已经大于它本身，则无需再算下去
                    if x <1 and judge<x:break # 与上类似
                if abs(judge-x)<0.0000001: # 判断是否达到精度要求
                    print(pow(x,1/n))   # pow函数计算结果
                    return r
                else:
                    if judge>x:
                        high = r
                    else:
                        low = r