1

基于这个答案，我在Python 3.x中实现了一个简单的算法来确定一个整数n是否是另一个整数的幂base。但是，该算法不会返回正确的结果。链接答案中的代码是：

while (n % 3 == 0) {
    n /= 3;
}
return n == 1;

（评论表明检查n == 0也是必要的，逻辑上）。这是我的代码：

def is_power(n: int, base: int) -> bool:
    if n == 0:
        return false
    while (n % base == 0):
        n /= base
    return n == 1

我编写了简单的测试代码来测试一定范围的基数和指数，但它返回的结果是不正确的。测试代码：

for base in range(3, 10):
    print("Base: {0}".format(base))
    for exp in range(30, 40):
        b = is_power(pow(base, exp), base)
        if not(b):
            print("{: <3}: {: <5}".format(exp, str(b)))

我用更大的范围测试了这个，但为了输出，我在这个例子中限制了它。这输出：

Base: 3
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 4
Base: 5
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 6
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 7
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False
Base: 8
Base: 9
30 : False
31 : False
32 : False
33 : False
34 : False
35 : False
36 : False
37 : False
38 : False
39 : False

这显然是不正确的。我试过调试一个小例子，在哪里n = pow(3, 35)并在循环中base = 3产生这些值：n

50031545098999707
1.6677181699666568e+16

循环结束，因为 50031545098999707 / 3 == 1.667718169966656 9 e+16 （注意最后一位不同）。这是问题吗？Python的计算失败了吗？如果不是，这个算法有什么问题？

如果我改用该算法，该算法也会失败得更多math.pow，但我并不一定对此感到惊讶，因为检查一个示例证明了这一点pow并且math.pow并不总是返回相同的值。

import math
pow(3, 35) == math.pow(3, 35) # 50031545098999707 != 5.0031545098999704e+16
4

2 回答 2

7

由于您使用的是 Python 3，因此您应该使用

def is_power(n: int, base: int) -> bool:
    if n == 0:
        return false
    while (n % base == 0):
        n //= base
    #     ^^ note two slashes
    return n == 1

在 Python 3.x 中，该/操作始终执行“实数除法”并返回一个浮点数，但在您链接到的算法中，它期望/进行整数除法，这是通过//("floor division")运算符。

正如您所料，测试失败的真正原因是浮点运算缺乏精度。/当返回一个无限精度的实数时，该算法仍然是正确的。以 3.0 34为例，

3.0 ** 34 == 16677181699666569
          == 0b111011001111111100111011110011000100000011001010001001

默认的浮点格式只支持5个3位的精度，但是上面的数字需要5个4位来表示，所以我们要对最后一位（即1）进行四舍五入，导致

             0b111011001111111100111011110011000100000011001010001000
                                                                    ^
          == 16677181699666568

其模数为 3 将返回 2，这将打破循环并返回 false。

（我还没有检查为什么它向下而不是向上取整，但即使它向上取整，模数仍然不为零，所以它仍然会返回 false。）

于 2012-07-21T20:40:32.710 回答
2

想想你的算法：你想做/=什么？

浮点除法？还是整数除法？您的问题显然使用了前者，但请手动尝试，看看它是否会起作用——您将继续除以base并得到非整数。

在 python 3 中，整数除法是//.

于 2012-07-21T20:51:46.510 回答