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次就猜对了。

一元三次方程求根

有这样一个一元三次方程：

$$X^3 -5X^2 -4X + 20 = 0$$

我们先画出它左边的图形看看

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时候的猜对次数。