x是我的输入。
我需要找到I,j>;=0和n,m>;1,例如x = i**m+j**n
现在我一直在这样做,但这是一个缓慢的方法!!我如何改进它?在
from math import sqrt
import numpy as np
def check(x):
for i in range(1,int(np.ceil(sqrt(x)))):
for j in range(1,int(np.ceil(sqrt(x)))):
for m in range(2,x/2+1):
for n in range(2,x/2+1):
if((pow(i,m) +pow(j,n))==x):
print 'Yes';
return ;
print 'No';
谢谢你!在
这里不时会出现一个问题,关于确定一个正整数是否是另一个正整数的整数幂。一、 给定正整数},使
z
求正整数j
和{z == j**n
。这可以在时间复杂度O(log(z))
中完成,因此速度相当快。在所以找到或开发这样一个例程:调用它},然后检查
is_a_power(z)
,如果z
是(0, 0)
的幂,则返回一个元组(j, n)
。然后循环i
和{x - i**m
是否为幂。当它成为一体,你就完蛋了。在我让你从这里完成代码,除了一个指针。给定
x
和i
,其中i > 1
,你可以找到m
的上限,这样i**m <= x
注意,}。在
i == 1
是一个特殊情况,因为在这种情况下,i**m
实际上并不依赖于{你可以通过找到所有小于x的幂(i**m)来逆转这个过程,然后你只要检查这些幂的任何一对加起来是否等于x
上面的代码很简单,但可以进行优化,例如,通过在while循环中集成检查一对是否等于x,在大多数情况下可以提前停止。在
上面的代码在O(sqrt(x)*log(x)*log(x))中工作,速度更快。在
您可以阅读代码中的注释来理解它。在
相关问题 更多 >
编程相关推荐