基于Python的二分法求平方根

基于Python的二分法求平方根

一个程序最核心的就是思想,换个词就是说是“思路”。解决这个问题的思路就是二分法逼近:
对于一个大于0的数,它的平方根是实数,而对于一个小于0的数开平方之后是一个纯虚数,其模等于该数的绝对值开平方。而在正数的这一边对于大于1 的数常用的二分法求平方根的思路是——

	输入:x
	输出:√x
	步骤:
			①low = 0;high = x;
			②guess = (low + high) / 2
			③如果guess² == x,则输出guess,程序结束;
			④如果guess² < x,则low = guess,继续执行步骤②
			⑤如果guess² > x,则high = guess,继续执行步骤②

基于以上思路,我们可以选择用条件语句来完成上述③④⑤步:

				    if guess ** 2 < x:
		                low = guess
		                
		            else:
		                high = guess
		                
		            guess = (low + high) / 2

对于guess,由于奇数的存在使得它必须允许小数的存在,因此我们这里为求精确取float型,因而为了方便我们将x的数据类型也定义为浮点型:

x = float(input("请输入一个需要开方的数,且保留2位小数:\n x = "))

这样我们就能便于比较guess²和x的大小关系,常用的比较两个数大小关系的方法就是作差,比较其结果与0的大小关系,为保证精度和准确性,我们用如下代码来控制要不要继续分:

				abs(guess ** 2 - x) > 0.0001

我们在取x==100对程序进行验证,结果如下:
这里写图片描述
根据以上结果对于大于1的数用二分法求解平方根的代码已经实现了。在这里感谢中国mooc网哈尔滨工业大学车万翔老师的授课。
但对于一个在0到1之间的数,我们知道0到1之间的任何一个数平方后的结果都小于原值(0,1除外),因此如果要沿用上面的程序达不到“逼近”的作用,反而扩大了,因此我对程序①②步作了以下改动:

					if x > 0 and x < 1:
					    high = 1.0
					    low = 0
					    guess = (low + high) / 2

这样,我们第一次取guess = 0.5,如果0.5² > x,我们下一次就在00.5之间取,反之在0.51之间取,直到取到符合循环停止条件的结果。举例验证:
这里写图片描述
到此为止已经解决了所有非负数平方根的求解,当然对于0和1:

				 if x == 1.0 and x == 0.0:
				         guess = x

现在要考虑负数的情况,思路是:

	①取一个负数记为x_org;
	②将 (-x_org)赋给x;
	③x为正,带入前面的运算计算;
	④输出结果后面加个字符“j”,程序结束。

相关代码如下:

						if x_org < 0:
						    x = - x_org
						else:
						    x = x_org
			elif x_org == -1.0:
			    print("所求数的平方根为:guess = j" )
			else:
			    print("所求数的平方根为:guess = %.1fj" % (guess))

程序验证:
这里写图片描述
基于此,用Python编写的二分法求平方根的问题已经完全解决了。这也是我编写的第二个基础的程序,还是蛮有收获,增添了我学习python的兴趣。希望这种兴趣能够只增不减。

重点来了:话不多说,直接上代码

	#!/usr/bin/python3
	
	# 利用二分法求解平方根
	
	x_org = float(input("请输入一个需要开方的数,且保留2位小数:\n x = "))
	
	# 判定x_org的正负,负数取反
	if x_org < 0:
	    x = - x_org
	else:
	    x = x_org
	# 变量的初始化
	## 程序第①步
	low = 0.0 
	high = x
	## 程序第②步
	guess = (low + high) / 2
	
	if x > 0 and x < 1:
	    high = 1.0
	    low = 0
	    guess = (low + high) / 2
	
	
	# 二分法求解平方根
	if x >= 0:
	    while abs(guess ** 2 - x) > 0.0001:
	        if x > 1.0:# 大于1 的数
	             if guess ** 2 < x:
	                 low = guess # 如果guess² < x,则low = guess,
	             else:
	                 high = guess # 如果guess² > x,则high = guess,
	             guess = (low + high) / 2 # 继续执行
	
	        if x == 1.0 and x == 0.0:# 0 和1 的求解
	             guess = x
	
	        else:
	            if guess ** 2 < x: # 在0-1之间的数
	                low = guess
	            else:
	                high = guess
	            guess = (low + high) / 2
	
	# 结果输出
	if x_org >= 0:## 非负数输出
	    print("所求数的平方根为:guess = %.1f"%(guess))
	## 负数输出
	elif x_org == -1.0:
	    print("所求数的平方根为:guess = j" )
	else:
	    print("所求数的平方根为:guess = %.3fj" % (guess))

总结

对于0~1之间小数平方根的求解我还有另外一种思路,只是我尝试了一下不知为何陷入死循环,我把这种思路简单说一下:
对于一个0~1之间的小数,我可以人为输入它的小数位数,比如0.09的小数位数是2,我们就将这个数扩大100倍,变成9,成为一个大于1的数,再利用二分法求平方根,得到结果为3,再将3缩小√100倍,得到0.3,进而得到结果。相关程序代码如下:

		if x > 0 and x < 1:
		    n = int(input("请输入被开方的小数位数:\n n = "))
		    count = 10**n
		    x = x * count
		    high = x
		    guess = (low + high) / 2
		    count_high = count
		    count_low = 0
		    count_guess = (count_low + count_high) / 2
		
		    while abs(count_guess ** 2 - count) > 0.0001:
		             if count_guess ** 2 < count:
		                 count_low = count_guess
		             else:
		                 count_high = count_guess
		             count_guess = (count_low + count_high) / 2
			if guess ** 2 < x:
			                low = guess
			            else:
			                high = guess
			            guess = (low + high) / (2*count_guess)
			            

谢谢大家阅读,如果你觉得有用,麻烦点个赞哟!


版权声明:本文为BIGtou_1314原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。