Python 递归(指数)

Question

快速幂，我需要编写一个计算n^b比n乘法更快的算法！算法的复杂性将为 O(logn(。我有一个代码，我能够通过前 20 次测试(我看不到数字(，但我无法改进算法以通过最后 5 次测试。有什么建议可以改进吗？

def quick_power(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    elif n == 2:
        return x * x
    elif n % 2 != 0:
        return x * quick_power(x, n - 1)
    elif n % 2 == 0:
        return quick_power(x, n // 2) * quick_power(x, n // 2)

x = int(input())
n = int(input())
print(quick_power(x, n))

Answer 1

你的想法是正确的方向，你的代码原则上没有错。关键是你需要区分两种状态，偶数和奇数

if n is even: x^n = (x^(n/2))^2
if n is odd: x^n = x*x^(n-1)

，你实际上做到了。

如果不知道您最近的 5 次测试，就很难弄清楚它失败的原因。但您可以尝试以下简化代码。

def quick_power(x, n):
  if n == 0:
    return 1
  elif n % 2 == 0:
    return quick_power(x, n / 2)**2
  else:
    return x * quick_power(x, n-1)
print(quick_power(3, 5))