Question

用python二分法求平方根，这个程序为什么错了？

要求：编写程序，输入一个在[0,1]范围内的小数x，用二分法求x的平方根。
我写的程序是这样的：

def main():
x=input('x')
n=0
if x<=1 and x>=0:
guess=0.5
if abs(x-guess**2)<=0.0000001:
print guess
elif guess**2-x>=0.0000001:
guess=(guess+0)/2
else:
guess=(guess+1)/2
return guess
else:
print 'x在0到1之间'
main()

我自己跑了几遍这个程序发现结果经常是0.75，明显不正确，但是又不知道这个程序什么地方出错了？请帮我看一下

Answer 1

首先二分法肯定需要一个“不断”二分的过程， 你的代码里面连一个循环都没有，肯定是不对的吧？

其次按照你的代码的思路，如果当前估算值guess的平法比x大，那就往0那边靠，否则就往1那边靠，这个好像也不对吧？

二分法的实现方法应该是，在区间[left, right]里面找x的开方，令估算值为guess等于区间的中点，如果guess比实际的大，那就把区间缩小一半，令到右端点移动到中点，如果guess比实际的小，也是将区间缩小一半，但是是令左端点移动到中点。这样每次缩小一半的区间，直到区间的长度非常非常小，那就认为区间的两个端点是相等的了，这个时候就得到了答案。

import math

def main():
	x = input('x=')
	n = 0
	if x <= 1 and x >= 0:
		left = 0.
		right = 1.
		while right - left >= 0.0000001:
			guess = (left + right) / 2.
			if guess ** 2 - x >= 0.0000001:
				right = guess
			else:
				left = guess
		#return guess
		print 'sqrt(x) is', left
	else:
		print 'x should be in [0,1]'

if __name__ == '__main__':
	main()

 我按照你的思路又写了另外一种方法：

def second():
	x = input('x=')
	n = 0
	if x <= 1 and x >= 0:
		movelen = (1 + 0) / 4.
		guess = (1 + 0) / 2.
		while abs(guess ** 2 - x) >= 0.0000001:
			if (guess ** 2 - x) >= 0.0000001:
				guess = guess - movelen
			else:
				guess = guess + movelen
			movelen = movelen / 2.
		print 'sqrt(x) is', guess
	else:
		print 'x should be in [0,1]'

追问

谢谢你，但是我还有一点不明白，第一个程序的第1行和第20行的作用是什么？我删掉这两行好像运行也是没问题的？

追答

不好意思，现在才看到。
第一句就是导入一个叫math的模块，本来我是看到你的代码里面用到了abs函数，以为这个函数应该在math模块里面，所以无意识地就加进去了，后来也没留意。
第20句就是针对一个工程，就是一堆py文件来说的，通常一个工程都会有一个起始的文件，也就是整个工程的入口，相当于C++里面的main()函数。第20句的意思就是，如果整个工程以这个文件作为入口的时候，才执行下面的语句，否则就忽略。