python - 求 pow(x,n) 的二等分递归解

Question

我正在研究一个介绍性递归问题:

Pow(x, n) - LeetCode

Implement pow(x, n), which calculates x raised to the power n (x^n).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−231, 231 − 1]

我的二等分解决方案

class Solution:
    def myPow(self, x: float, n: int) -> float:
        #base case
        if n == 0: return 1
        #recur case 
        else:
            half = self.myPow(x, n//2) #floor           
            if n % 2 == 0: #even                      
                return half**2
            if n % 2 != 0: #odd
                return x * (half**2)        

运行测试用例时

    def test_b(self):
        x = 2.0
        n = -2
        answer = 0.25
        check = self.solution.myPow(x, n)
        self.assertEqual(answer, check)

报告错误:

DEBUG x: 2.0, n: -1
DEBUG x: 2.0, n: -1
DEBUG x: 2.0, n: -1
.......
DEBUG x: 2.0, n: -1
DEBUG x: 2.0, n: -1
DEBUG x: 2.0, n: -1
Fatal Python error: Cannot recover from stack overflow.

它停在 n=-1并发现了尴尬的情况

In [10]: -1 // 2                                                                                                              
Out[10]: -1

In [11]: -2 // 2                                                                                                              
Out[11]: -1

修改成功

class Solution:
    def myPow(self, x: float, n: int) -> float:
        """
        Runtime: 36 ms, faster than 99.70%
        Memory Usage: 13.2 MB, less than 5.53%
        """
        #base case
        if n == 0: return 1
        if n == -1: return 1/x
        #recur case 
        else:
            logging.debug(f"x: {x}, n: {n}")            
            half = self.myPow(x, n//2) #floor 

            if n % 2 == 0: #even
                logging.debug(f"even: x: {x}, n: {n}, half:{half}")                            
                return half**2
            if n % 2 != 0: #odd
                logging.debug(f"odd: x: {x}, n: {n}, half:{half}")                            
                return x * (half**2)        

但是，在阅读讨论和其他意见后。我发现所有其他情况都更喜欢基本情况 n < 0

一个明显的例子:

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1
        if n < 0:
            return 1 /self.myPow(x, -n)
        else:
            partial = self.myPow(x, n//2)
            result = partial * partial
            if n % 2 == 1: #odd
                result *= x
            return result

我觉得没必要改负n至-n , cos 2**10 == 2**5 * 2** 5 and 2**-10== 2**-5 * 2**-5

因为人们更喜欢基本案例 n < 0比n == -1 ，有什么好处？

Answer 1

对于“不需要将负数n更改为-n”:
我认为是性能和精度的考虑。

• 性能:整数乘法比浮点运算快
• 精度:当数字很小时，可能会导致精度损失。

所以我们更喜欢先做pow，然后再除法。​​