24 分治算法
分而治之,各个击破
大纲
二分法搜索
方程求根
所谓分治就是分而治之,即将一个较大而复杂的问题,先分解为一些较小而简单的子问题,然后通过对子问题的求解来得到大问题的解。
二分法搜索
有这样一种游戏叫作猜数字,小朋友A要从20以内的数字中选好一个数字,心里面记好,让另一个小朋友B去猜这个数字是多少,B猜一个数字后会问A,A要回应这个猜测是大了还是小了,那么B要怎样做才能最快的猜出这个数字呢?让我们用本课学到的编程知识来模拟这个过程。
# 假设A选择了3,B一开始猜测的是数字10
number_A = 3
number_B = 10
# 定义一个函数来模拟A对于猜测数字的回复
# 如果B猜的数字一样就回复正确,如果较小就回复猜小了,如果较大就回复猜大了
def more_less(a,b):
if a == b:
return "猜对了"
if a>b:
return "猜小了"
if a<b:
return "猜大了"
# 定义一个函数来B如何去改换猜测的数字,如果结果是猜小了就增加1,如果是大了就减少1
def change_number(a,b):
if more_less(a,b) == "猜小了":
b_new = b+1
if more_less(a,b) == "猜大了":
b_new = b-1
return b_new
# 用while循环来模拟这个过程
while True:
# 打印出A一开始记住的数字,以及B猜测的数字
print(number_A,number_B)
# A 来给出猜测的回复
guess_result = more_less(number_A,number_B)
if guess_result == "猜对了":
print(guess_result)
break # 如果猜对了就结束循环
else: # 如果没有猜对,B就需要更换一个猜测数字
number_B = change_number(number_A,number_B)
3 10
3 9
3 8
3 7
3 6
3 5
3 4
3 3
猜对了
可以看到,用这种最简单的更新猜测的方法,B需要8次猜测才能猜到正确的答案,如果A开始选的是1,B开始猜的是20,那么要猜20次才能到正确的答案。那么有没有更快的方法呢?当然是有的,我们可以利用二分法的思路来猜。二分法的思路就是一次排除一半,例如整体数字是20,那么一开始B猜10,结果不论如何,可以排除另外一半的数字,在下一步,如果结果是猜大了,可以直接跳到5,不论结果如何,再排除一半的数字。
number_A = 3
low = 0
high = 20
# number_list用于存放数字列表
number_list = list(range(high+1))
while low <= high:
mid = int((low+high)/2) # 检查中间的元素
number_B = number_list[mid] # 取出中间的数字
print(number_A,number_B)
if more_less(number_A,number_B)=="猜对了":
print("猜对了")
break
if more_less(number_A,number_B)=="猜大了":
high = mid -1
else:
low = mid + 1
3 10
3 4
3 1
3 2
3 3
猜对了
使用这种方法后,只用猜5次就猜对了。
一元三次方程求根
有这样一个一元三次方程:
我们先画出它左边的图形看看
import matplotlib.pyplot as plt
%matplotlib inline
x_list = range(-5,10)
y_list = [x**3 -5*x**2-4*x+20 for x in x_list]
plt.plot(x_list,y_list)
plt.hlines(0,-5,10)

可以看到这个方程有三个根,我们需要编写一个程序来找到这三个根。
def F(x):
return x**3 -5*x**2-4*x+20
for x in range(-500,1000):
x = x/100
x1 = x-0.0005
x2 = x+0.0005
if (F(x1)*F(x2)<0):
print("根等于{x}".format(x=x))
根等于-2.0
根等于2.0
根等于5.0
这种思路仍然是遍历搜索的思路,速度比较慢,更快思路是采用分治法。
for x in range(-5,10):
x1 = x-1
x2 = x+1
if F(x1)*F(x2)<0:
while x2-x1>=0.001:
mid = (x2+x1)/2
if F(x1)*F(mid)<=0:
x2 = mid
else:
x1 = mid
print("根等于{x}".format(x=mid))
根等于-2.0009765625
根等于1.9990234375
根等于4.9990234375
小结:二分法是一种比较巧妙的思路,因为它在每一次迭代时都可以排除手头一半的量,可以有效的节约计算时间,大家还可以用上面的代码去尝试一下其它的数字,例如high设置为1000时候的猜对次数。
Last updated
Was this helpful?