Python X 的 N 次方的分而治之实现

Question

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

问题：

实现 pow(x, n)，计算 x 的 n 次方。

示例：输入：2.00000, 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达到了base case，然后我们继续power(2,2) ，由于函数 multiply(x,x) 或 multiply(2,2) 在这种情况下，我希望 x 变为 4 (x = 2*2)，然后我们继续 power(2,4)，由于函数乘法 (x,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() 函数总是 returns x，因为行：

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

不要将他们 return 的值赋给任何东西。

Answer 3

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

这是由于功能范围。当您在 multiply() 内更改 x 时，它只会在该函数内更改。您正确地 return 更改了值，但没有将其存储在调用函数中。

将 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 returns 4 而不是 8。

Answer 4

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

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

此函数接受 x 和 n，然后使用这些变量计算子问题，然后 return 原始 x。因此，在您的示例中，调用 test3.power(x, y) 将始终 return 原始 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)，这不是您想要的。希望对您有所帮助。

Python X 的 N 次方的分而治之实现

Python Divide and Conquer Implementation of Nth Power of X

python

divide-and-conquer