Python的X的N次方除法和征服实现

Question

作为一个新的python程序员，我正在研究Leetcode问题，不知道为什么我的代码不起作用，所以我非常感谢您的建议：

问题：

实现pow（x，n），它计算x的幂n。

示例：输入：2.000000，10

输出：1024.00000

这是我的python代码（我尝试使用分而治之的概念）：

class Solution:
    def myPow(self, x, n):
        if n == 0:
            return 0
        if n == 1:
            return x
        return self.power(x,n)
    def power(self,x,n):
        if n == 1:
            return x
        self.power(x,n//2)
        self.multiply(x,x)
        return x
    def multiply(self,x,y):
        x = x*y
        return x
test3=Solution()
test3.myPow(2,4)

但是结果给出2而不是16。我希望上面的代码可以如下工作：

power（2,4）-> power（2,2）-> power（2,1），由于n == 1，它达到了基本情况，然后继续进行power（2,2），由于在这种情况下，函数乘法（x，x）或乘法（2,2），我希望x变为4（x = 2 * 2），然后由于函数乘法（x），我们继续乘幂（2,4） ，x），x = 4 * 4 = 16

我不知道为什么我做错了，有专家可以给我一些建议吗？

Answer 1

class Solution:
    def myPow(self, x, n):
        if n == 0:
            return 1
        if n == 1:
            return x
        return self.power(x,n)

    def power(self,x,n):
        if n == 1:
            return x
        x = self.power(x,n//2)
        return self.multiply(x,x)

    def multiply(self,x,y):
        x = x*y
        return x

test3=Solution()
test3.myPow(2,4)

此代码仅解决了代码中的一些小问题，但仍应考虑功率n为奇数的情况。

Answer 2

x ^ 0始终等于1，因此myPow（）中的第一个“ if”不正确。同样，您的power（）函数总是返回x，因为这些行：

self.power(x,n//2)
self.multiply(x,x)

不分配它们返回的值。

Answer 3

您没有将self.power()和self.multiply()的返回值存储在power()中。

这是由于功能范围。在x中更改multiply()时，仅在该功能中更改。您正确返回了更改后的值，但没有将其存储在调用函数中。

将power()更改为您的示例的以下作品（2 ^ 4）。

def power(self,x,n):
    if n == 1:
        return x
    x = self.power(x,n//2)
    x = self.multiply(x,x)
    return x

但是，您的算法存在缺陷，因为2 ^ 3返回4而不是8。

Answer 4

[首先，我会注意到x ^ 0 = 1，但是您的代码指出，在if中的第一个myPow语句中，该值应等于零。其次，您的大问题是您没有存储任何中间结果。在power功能中，您具有：

def power(self,x,n):
  if n == 1:
    return x
  self.power(x,n//2)
  self.multiply(x,x)
  return x

此函数接受x和n，然后使用这些变量计算子问题，然后返回原始的x。因此，在您的示例中，调用test3.power(x, y)将始终返回原始x值。相反，请执行以下操作。

def power(self,x,n):
  if n == 1:
    return x

  # Account for when n is not even.
  n1 = n // 2
  n2 = n - n1

  # Calculate powers.
  x1 = self.power(x, n1)
  x2 = self.power(x, n2) 

  # Combine divide-and-conquer answers and return.
  x = self.multiply(x,x)
  return x

[还要注意，我更改了功能以将问题分解为n1和n2的幂。这是因为您的函数无法正确处理power(2, 3)之类的内容。在这种情况下，原始函数将计算出您不想要的power(2, 3 // 2) = power(2, 1)。希望对您有所帮助。