document.write('
方法一:直接计算法
由于不能使用开方运算,因此最直接的方法就是计算平方。主要思路为:对1到n的每个数i,计算
它的平方m,如果m<n,那么继续遍历下一个值(i+1),如果m=n,那么说明n是某个数的平方,如
果m>n,那么说明n不能表示成某个数的平方。实现代码如下:
#判断一个自然数是否是某个数的平方
def isPower(n):
if n<=0:
print n+"不是自然数"
return False
i=1
while i<n:
m=i*i
if m=-n:
return True
elif m>n:
return False
i+=1
return False
if __name__=="__main__":
n1=15
n2=16
if isPower(n1):
print str(n1)+"是某个自然数的平方"
else:
print str(n1)+"不是某个自然数的平方"
if isPower(n2):
print str(n2)+"是某个自然数的平方"
else:
print str(n2)+"不是某个自然数的平方"
程序的运行结果为:
15不是某个自然数的平方
16是某个自然数的平方
算法性能分析
由于这种方法只需要从1遍历到n0.5就可以得出结果,因此算法的时间复杂度为O(n0.5
)。
方法二:二分查找法
与方法一类似,这种方法的主要思路还是查找从1~n的数字中,是否存在一个数m,使得m的平
方为n。只不过在查找的过程中使用的是二分查找的方法。具体思路为:首先判断mid=(1+n)/2的
平方power与m的大小,如果power>m,那么说明在[1,mid-1]区间继续查找,否则在[mid+1,
n]区间继续查找。
实现代码如下:
def isPower(n):
low=1
high=n
while low<high:
mid=(low+high)/2
power=mid*mid
撑接着在1~mid-1区间查找
if power>n:
high=mid-1
#接着在mid+1到n区间内查找
elif power<n:
low=mid+1
else:
return True
return False
if __name__=="__main__":
n1=15
n2=16
if isPower(n1):
print str(n1)+"是某个自然数的平方"
else:
print str(n1)+"不是某个自然数的平方"
if isPower(n2):
print str(n2)+"是某个自然数的平方"
else:
print str(n2)+"不是某个自然数的平方"
算法性能分析
由于这种方法使用了二分查找的方法,因此,时间复杂度为O(logn),其中,n为数的大小。
方法三:减法运算法
通过对平方数进行分析发现有如下规律:
(n+1)2=n2+2n+1=(n-1)2+(2*(n-1)+1)+2*n+1=……=1+(2*1+1)+(2*2+1)+…+(2*n+1)。通
过上述公式可以发现,这些项构成了一个公差为2的等差数列的和。由此可以得到如下的解决方法:
对n依次减1,3,5,7…,如果相减后的值大于0,那么继续减下一项;如果相减后的值等于0,那么说明
n是某个数的平方;如果相减的值小于0,那么说明n不是某个数的平方。根据这个思路,代码实现
如下:
def isPower(n):
iminus=1;
while n>0:
n=n-minus,
#n是某个数的平方
if n==0:
return True;
#n不是某个数的平方
elif n<0:
return False;
#每次减数都加2
else:
minus+=2;
return False
if __name__="__main__":
n1=15
n2=16
if isPower(n1):
print str(n1)+"是某个自然数的平方"
else:
print str(n1)+"不是某个自然数的平方"
if isPower(n2):
print str(n2)+"是某个自然数的平方"
else:
print str(n2)+"不是某个自然数的平方"
算法性能分析
这种方法的时间复杂度仍然为O(n0\'5)。由于方法一使用的是乘法操作,这种方法采用的是减法操
作,因此这种方法的执行效率比方法一更高。
');