我试图确定给定的正整数 ( N ) 是否为 3 的幂,即是否存在非负整数 ( x ) 使得 ( 3^x = N )。挑战在于 ( N ) 可能非常大,最多有 ( 10^7 ) 位数字。
这是我想要实现的逻辑:
- 如果(N)小于或等于0,则返回-1。
- 使用对数计算确定 ( N ) 是否是 3 的幂。
- 如果它是 3 的幂,则打印 (x) 的值;否则,打印 -1。
我已经尝试了以下代码,但我担心大整数的精度问题:
import math
def is_power_of_three(N):
if N <= 0:
return -1
log3_N = math.log10(N) / math.log10(3)
if abs(log3_N - round(log3_N)) < 1e-10:
return int(round(log3_N))
else:
return -1
# Example usage:
N = int(input("Enter a number: "))
print(is_power_of_three(N))
问题:
- 有没有更有效的方法来检查(N)是否是3的幂,特别是对于非常大的值?
- 在计算如此大的整数的对数时,如何处理 Python 中的精度问题?
- 是否有其他方法可以实现同样的目标?
10
最佳答案
4
任何涉及重复除法的方法在处理如此大的数字时都会很慢。
相反,考虑使用数字的位长度(实际上是其以 2 为底的对数的上限)来近似相应的 3 的幂,然后检查它是否确实相等:
import math
def what_power_of_3(n):
if n <= 0:
return -1
k = math.floor(n.bit_length() * (math.log(2) / math.log(3)))
if n == 3**k:
return k
else:
return -1
这很快:测试只需要一次指数运算,因此对于例如 3**10000000,在我的智能手机上只需要几秒钟。
简单概括一下为什么这是正确的:
由于相等性检查,如果n
不是 3 的幂,则答案将始终正确(因为n == 3**k
不可能为真)。因此,足以证明k
当 时,此答案始终正确n == 3 ** k
。设k > 0
,n = 3 ** k
,和t = n.bit_length()
。然后,3 ** k < 2 ** t < 3 ** (k + 1)
根据 的定义bit_length()
。因此k < t * log(2) / log(3) < k + 1
,因此n.bit_length() * (math.log(2) / math.log(3))
将是严格k
介于和之间的分数值k+1
;因此,floor
该值的 恰好是k
。
15
-
2哦天哪,在我的桌面上只需要 0.02 秒。你赢了,回答得好
–
-
非常优雅,并且能及时返回问题所要求的值。我大约在一秒钟内就完成了 3**1000000。
– -
问题1:为什么不呢
k = math.floor(math.log(n, 3))
?
–
-
1谢谢。从数学上看,这看起来不错。但对于浮点数,我仍然不太确定。
– -
3我刚刚重读了这个问题:它已经用过了
round(log3_N))
。你建议用别的东西代替……我想你应该说说为什么你的更好。
–
|
您的函数应该返回布尔值。返回“标记值”-1
似乎很奇怪,而且不符合习惯用法。
使用对数的另一种方法是使用重复除法。因为我们要除以底数,所以运行时间复杂度是对数的(但对于非常大的数字来说更糟糕)。
def is_power_of(n, d):
if n == 1: return True
if n < d: return False
while n >= d:
if n % d: return False
if n == d: return True
n //= d
return False
现在,如果您需要知道数字是三的哪个-1
幂,这就是您返回的原因,那么我仍然建议您不要返回-1
而是None
。并且使用不同的函数名称。
def power_of(n, d):
if n == 1: return 0
if n < d: return None
exp = 1
while n >= d:
if n % d: return None
if n == d: return exp
exp += 1
n //= d
return None
0
|
要检查数字n的幂p,可以将该数字转换为底数p,然后检查第一位数字(左边)是否为 1,其余数字是否为 0。
x = 3**100000
y = x - 1
z = x - 9
a = 30
def ternary (n):
if n == 0:
return '0'
nums = []
while n:
n, r = divmod(n, 3)
nums.append(str(r))
return ''.join(reversed(nums))
def is_power_of_3(n):
nstr = ternary(n)
return nstr[0] == '1' and '1' not in nstr[1:] and '2' not in nstr[1:]
print("x = {}\ny = {}\nz = {}\na = {}".format(is_power_of_3(x), is_power_of_3(y), is_power_of_3(z), is_power_of_3(a)))
我举了4个例子,只不过x
是3的幂。
输出:
x = True
y = False
z = False
a = False
real 2.60s
user 2.59s
sys 0.01s
cpu 99%
仅需测试一个值:
x = True
real 0.88s
user 0.87s
sys 0.01s
cpu 99%
|
这在速度上不会与 nneonneo 匹敌。然而,它试图完全保持在整数运算范围内,尽管需要 O(log(N)) 次除法。
需要注意的一点是:如果你取一个很大的数字,那么很有可能它不是 3 的幂。因此,你应该尽快排除:可能在将输入字符串转换为整数之前。
3 的任何幂的形式为 3**(4k+m),其中 m 为 0、1、2 或 3。m 每个值对应的最后一位数字为 1、3、9 或 7。任何其他数字结尾都会被立即拒绝。
如果以 1 结尾,则检查 x 是否是 3**4 的幂,即 81
如果以 3 结尾,则检查 x 是否能被 3 整除以及 x/3 是否是 81 的幂。
如果以 9 结尾,则检查 x 是否能被 9 整除以及 x/9 是否是 81 的幂。
如果以 7 结尾,则检查 x 是否能被 27 整除,并且 x/27 是否是 81 的幂。
因此,除了初始检查之外,您还要询问某个数是否是 81 的幂。此外,81 的每个幂都以数字 1 结尾。
然后,一个数字可能是给定数字的偶数幂或奇数幂。因此,对于新的测试数字 y,检查 y 或 y/81 是否是 81 的幂。然后您将递归,测试 81、81^2、81^4、81^8 等的幂。
def test( n, x ): # n is 81, 81^2, 81^4, 81^8 etc.
if x == 1 or x == n: return True
if x % 10 != 1: return False
if x % n != 0: return False
nsq = n * n
return test( nsq, x ) or test( nsq, x // n )
def isPowerOf3( x ):
lastDigit = x % 10
if lastDigit == 1:
return test( 81, x )
elif lastDigit == 7 and x % 27 == 0:
return test( 81, x // 27 )
elif lastDigit == 9 and x % 9 == 0:
return test( 81, x // 9 )
elif lastDigit == 3 and x % 3 == 0:
return test( 81, x // 3 )
return False
for i in range( 10000000 ):
if ( isPowerOf3( i ) ): print( i )
print( isPowerOf3( 3**100000 ) )
print( isPowerOf3( 3**100000 + 1 ) )
是的,倒数第二个测试需要几秒钟:
1
3
9
27
81
243
729
2187
6561
19683
59049
177147
531441
1594323
4782969
True
False
|
–
–
–
–
–
|