Python算法：判断平方数

Alexandra ·

更新时间:2024-11-10

· 875 次阅读

判断平方数 1、问题描述

给定一个正整数num ，判断是否为完全平方数，要求当num为完全平方数时返回True，否则返回False。

2、问题示例

输入num=16，输出True，sqrt(16)=4；输入num=15，输出False，sqrt(15)=3.87。

3、代码实现

# 参数 num 是一个正整数
# 返回值时一个布尔值，如果num是完全平方数就返回True，否则返回False。
class Solution():
	def isPerfectSquare(self, num):
		l = 0 
		r = num
		while (l - r > 1): # 当左值l 与右值r 是非相邻数字时：
			mid = ( l + r ) / 2  # 取中值
			if (mid * mid <= num): # 如果mid的平方数小于或者等于num，表示我们要找的数比这个数大
				l = mid # 缩小范围，为了寻找更大的数
			else: # 如果mid的平方数大于num，表示我们要找的那个数比这个数小
				r = mid # 为了寻找更小的数
		ans = l # 如果存在mid*mid=num，则会将mid赋值给l，所以ans的初始值为l
		if (l * l < num): # 但如果l*l的值小于num，代表我们要找的数可能是r
			ans = r
		return ans * ans == num # 如果找到了平方数，则返回True
if __name__ == '__main__':
	num = 16
	print("initial value: ", num)
	solution = Solution()
	print("result: ", solution.isPerfectSquare(num))

4、运行结果

initial value: 16
result: True

5、分析

本人觉得这个算法可能包含两种思维：1、二分法；2、极限

二分法：取中值的方法可以更快地进行序列查找。极限：作为二分查找的终止条件，当二分法左右两个基数的距离小于1时，题目所需的正整数已经被遍历完毕。
作者：奥特曼丶毕健旗

Python python算法

1024 个赞