Exponentiate(Multiply)没有**(Python)

Question

我该怎么做呢:

if p1 == 0:
    return 1
if p1 == 1:
    return temp_obj
if p1 == 2:
    return temp_obj*temp_obj
if p1 == 3:
    return temp_obj*temp_obj*temp_obj
if p1 == 4:
    return temp_obj*temp_obj*temp_obj*temp_obj

不使用**

我实际上是在一个重载pow的类中写这个,而且*已经超载了.

我试过了

for x in range(p1):
  temp_obj = temp_obj * temp_obj

但那没用.价值非常高.

谢谢

Answer 1

这不起作用的原因是因为你对每个功率值的数字进行平方.这意味着p1 = 3,我们得到:

temp_obj = 5
temp_obj = temp_obj * temp_obj = 25
temp_obj = temp_obj * temp_obj = 625
temp_obj = temp_obj * temp_obj = 390625

所以你实际计算了5 ^{2 3}.所以5 ⁸ = 390'625.

我们可以通过每次乘以​​值来解决这个问题,所以:

def power(x, p):
    if not p:
        return 1
    y = x
    for x in range(p-1):
        y *= x
    return y

但是这在线性时间内工作,我们也可以在对数时间内构造一个算法:

def power(x, p):
    if p == 0:
        return 1
    elif p & 1:
        return x * power(x*x, p//2)
    else:
        return power(x*x, p//2)

或者,如果我们想减少递归调用的开销,那么这是一个命令式版本:

def power(x, p):
    r = 1
    while p:
        if p & 1:
            r *= x
        x *= x
        p >>= 1
    return r

例如:

>>> power(5, 6)
15625
>>> power(5, 1)
5
>>> power(5, 0)
1
>>> power(3, 2)
9
>>> power(3, 7)
2187