【正确答案】方法一：直接计算法
由于不能使用开方运算，因此最直接的方法就是计算平方。主要思路为：对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)。由于方法一使用的是乘法操作，这种方法采用的是减法操作，因此这种方法的执行效率比方法一更高。
【答案解析】[考点] 如何判断一个自然数是否是某个数的平方。