第20课 分治算法

学习要点

（1）理解基本算法中的分治算法。

（2）能够用分治算法实现简单的Python程序。

对标内容

理解基本算法中的分治算法，能够用分治算法实现简单的Python程序。

分治算法

情景导入

假设你正在爬楼梯，需要n步才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到顶部？

def climb(n=7):
    if n<= 2:
        return n
    return climb(n-1)+climb(n-2) #等价于斐波那契数列!
print(climb(5))    #8 
print(climb(7))    #21

知识点详解

分治算法的概念

分：将一个复杂的问题分成两个或更多个相同或相似的子问题，再把子问题分成更小的子问题。

治：最后子问题可以简单地直接求解。

合：将所有子问题的解合并起来就是原问题的解。

分治算法的特征

（1）该问题的规模缩小到一定的程度就可以容易地解决。

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优结构性质。

（3）该问题分解出的子问题的解可以合并为该问题的解。

（4）该问题所分解出的各个子间题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题可以满足的，因为问题的计算复杂性一般随着问题规模的增加而增加。

第二条特征是应用分治算法的前提，大多数问题也可以满足，此特征反映了递归思想的应用。

笫三条特征是关键，能否利用分治算法完全取决于问题是否具有这一条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及分治算法的效率，如果各个子问题不是相互独立的，则分治算法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治算法，但一般用动态规划法会更好。

分治算法的例子

例题1 对数组进行快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是通过一遍排序将要排序的数据分割成独立的两部分，其中一部分的所存数据都比另一部分的所有数据都小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，最终使所有数据变成有序序列。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下。

（1）首先设定一个分界值，通过该分界值将序列数据分成左、右两部分。

（2）将大于或等于分界值的数据集中到右边，小于分界值的数据集中到左边。此时，左边各元素的值都小于或等于分界值，而右边各元素的值都大于或等于分界值。

（3）然后，左边和右边的数据可以独立排序。对于左边的数据，又可以取个分界值，将该部分数据再分成左、右两部分，同样在左边放置较小值，右边放置较大值。右边的数据也可以做类似处理。

（4）重复上述过程，可以看出，这是一个递归定义。通过递归将左边排好序，再通过递归将右边排好序。当左、右两部分分别排序完成后，整个序列数据的排序也就完成了。

快速排序的排序步骤：设要排序的数据是Ａ[0]......Ａ[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一遍快速排序。

值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时发生变动。

一遍快速排序的算法是如下。

（1）设置两个变量 i、ｊ，排序开始时，i＝0，ｊ＝N-1。

（2）以第一个元素作为关键数据，将其值赋值给key，即key＝A[0]。

（3）从j开始向前搜索，即由后向前搜索（j-1），找到第一个小于key的值A[j]，将A[j]和A[i]的值互换。

（4）从i开始向后搜索，即由前向后搜索（i+i），找到第一个大于kye的A[i]，将A[i]和A[j]的值互换。

（5）重复第（3）、（4）步，直到i=j；第（3）、（4）步中如果没有找到符合条件的值，即（3）中Ａ[j]]不小于key，（4）中A[i]不大于key，改变i、j的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换时，i、ｊ指针位置不变。另外，i==j这一过程一定正好是i++或j--完成时，此时循环结束。

假设一开始时序列ａ是：５，３，７，６，4，1，0，２，９，10，８。此时，ref＝５，i=0，ｊ＝10，从后往前找，第一个比5小的数是a[7]＝２，因此序列变为：

２，３，７，６，4，1，0，５，９，10，８。

此时i＝0，ｊ＝７，从前往后找，第一个比５大的数是a[2]＝７，因此序列变为：

２，３，５，６，４，1，0，７，９，10，８。

此时ｉ＝２，ｊ＝７，从第７位往前找，第一个比５小的数是a[6]＝０，因此序列变为：

２，３，0，６，４，1，５，７，９，10，８。

此时 i＝２，ｊ＝６，从第２位往后找，第一个比５大的数是ａ[3]＝６，因此序列变为：

２，３，0，５，４，1，６，７，０，10，８。

比时 i＝３，ｊ＝６，从第6位往前找，第一个比５小的数是ａ[5]＝1，因此序列变为：

２，３，0，1，４，５，６，７．０，10，８。

此时 i＝３，ｊ＝５，从第３位往后找，直到第6位才有比５大的数（正常区间巳无满足的数），这时，i=j=5，ref成为一条分界线，它之前的数都比它小，之后的数都比它大，对于前、后两部分数，可以采用同样的方法来排序。

实现代码如下：

def quicksort(array, start, end):
    if start >= end:
        return
    mid_data, left, right = array[start], start, end
    while left < right:
        while array[right] >= mid_data and left < right:
            right -= 1
        array[left],array[right] = array[right],array[left]
        while array[left] < mid_data and left < right:
            left += 1
        array[left],array[right] = array[right],array[left]
    quicksort(array, start, left-1)
    quicksort(array, left+1, end)
list1=[5,3,7,6,4,1,0,2,9,10,8]
quicksort(list1,0,len(list1)-1)
print(list1)

其他实现方式：

• 代码1

def quicksort(list,p,r):
    if p<r:
        q=partion(list,p,r)
        quicksort(list,p,q)
        quicksort(list,q+1,r)
def partion(list,p,r):
    i=p-1
    for j in range(p,r):
        if list[j]<=list[r]:
            i+=1
            list[i],list[j]=list[j],list[i]
    list[i+1],list[r]=list[r],list[i+1]
    return i
list1=[5,3,7,6,4,1,0,2,9,10,8]
quicksort(list1,0,len(list1)-1)
print(list1)

• 代码2

#划分分区（非就地划分）
def partition(nums=list):
    pivot = nums[0]                             #挑选枢纽
    lo = [x for x in nums[1:] if x < pivot]     #所有小于pivot的元素
    hi = [x for x in nums[1:] if x >= pivot]    #所有大于等于pivot的元素
    return lo,pivot,hi
#快速排序
def quick_sort(nums=list):
    #被分解的Nums小于1则解决了
    if len(nums) <= 1:
        return nums
    #分解    
    lo,pivot,hi = partition(nums)
    # 递归（树），分治，合并
    return quick_sort(lo) + [pivot] + quick_sort(hi)
lis = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(quick_sort(lis)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

例题２

给定一个顺序表，编写一个求出其最大值的分治算法。

#基本子算法（内置算法）
#虽然也可以处理大数组，这里用于解决分治问题规模小于2时候
def get_max(nums=list):
    return max(nums)
#分治法 
def solve(nums):
    n = len(nums)
    if n <= 2:    #分治问题规模小于2时解决
        return get_max(nums)
    # 分解（子问题规模为 n/2）
    left_list, right_list = nums[:n//2], nums[n//2:]    
    # 递归（树），分治
    left_max, right_max = solve(left_list), solve(right_list)  
    # 合并
    return get_max([left_max, right_max])
# 测试数据
alist = [12,2,23,45,67,3,2,4,45,63,24,23]
# 求最大值
print(solve(alist))  # 67

思考

（1）在Python中随机产生一个1~1000的整数，使用分治算法中的二分查找法猜测这个数的位置，最大需要猜几次？（ ）

A. 7 B. 8 C. 9 D. 10

答案：Ｄ

解析：分治算法的设计思想是将一个难以直接解诀的大问题，分割成一些规模较小的相同间题，以便各个击破，分而治之。对于一个规模为口的问题，若该则直接解决，否则就将其分解为 问题可以容易地解诀（比如说规模口较小）。则直接解决，否则就将其分解为规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。其中，二分查找法的思想说来比较简单，就是利用上下限不停地缩小查找的界限，当缩小到一定范围内时，就可以解决了。算法的时间复杂度一般为１０８１２，因此查找Ｉ０次所能够冠盖的数的范围已达到ＩＯ２Ａ。

理解体现分治算法的二分查找法的原理。

（2）二分查找法是利用_实现的。

答案：分治算法

易错点

（1）在理解递归算法的基础上理解分治算法。

（2）“分”、“治”的概念必须理解。

模拟考题

考题1 单选题

以下函数是将一个整数划分为若干个正整数相加的例子，如，4 =4，1＋3＝４，1＋1＋２＝４，２＋２＝４，1＋1＋1＋1＝ 4共５种，则迁if条件里应补充的选项为（）。

def function(b,a):    #b为待划分的整数，ａ为正整数加数的个数上限
    if(_____):
        return 1
    elif a==b and b>1:
        return function(b,b-1)+1
    elif b<a:
        return function(b,b)
    elif b>a:
        return function(b,a-1) + function(b-a,a)

A. a==1 or b==1 B. a==0 or b==1 C. a==1 or b==0 D. a==1 and b==1

答案：Ａ

考题２ 单选题

一个袋子里有128枚硬币，其中一枚是假币，并且假币和真币外观一模一样，仅凭肉眼无法区分，仅知道假币比真币轻一些，我们现在借助天平来查找假币，最多称几次可以找到假币？

A. 5 B. 6 C. 7 D. 8

答案：Ｃ

解析：将n枚硬币分成两等份，然后放到天平的两端，则假币在较轻的那将较轻的那一端的硬币再分成两等份，再放到天平的两端进行比较，假是在较轻的那一端；直到最后只剩下两枚硬币了，分别放到天平的两端，轻的那一枚就是假币。当然，最后也可能剩下３枚硬币，我们可以从这３枚硬币中任意拿出来一枚，然后将剩下的两枚放到天平的两端，如果天平是平的，则说明拿出来的那枚硬币就是假币；如果天平不是平的，则轻的那一端是假币。

所以，128枚硬币可以这样分解：128 → 64 → 32 → 16 → 8 → 4 → 2 → 1，即最多称７次可以找到假币。

考题3 判断题

使用分治算法分解的子问题是相互独立的、无关联的，子问题的解可以合并为原问题的解。

答案：正确

解析：分治算法的基本思想是将一个规模为口的间题分解为飞个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

分治算法单元测试题

模拟考题

一、单选题(共15题，每题5分，共75分)

1、应用分治算法的前提是？（ ）

A. 问题的可分性和解的可归并性

B. 问题的复杂性和解的简单性

C. 问题的可分性和解的存在性

D. 问题的复杂性和解的可归并性

2、下面哪种算法使用了分治的方法？（ ）

A. 插入排序

B. 快速排序

C. 选择排序

D. 冒泡排序

3、在解决问题过程中，常用的“二分法”是一种什么算法？（ ）

A. 分治

B. 递归

C. 推理

D. 递推

4、分治,"分而治之"。从字面上理解就是分---治，把大的问题分成小问题，解决一个一个小问题，之后把问题的答案合并起来，就得到大问题的结果。历史上也有很多故事属于分治思想，以下属于分治思想的是？（ ）

A. 三国时，曹操带兵长途行军，士兵们都很口喝，曹操便说：“前面就是一大片梅林，结了许多梅子，又甜又酸，可以解渴。” 士兵们听了，嘴里都流口水，一时也就不渴了。

B. 战国时期，秦国通过远交近攻的策略，逐个击破，最后统一六国。

C. 汉末刘备三次到诸葛亮住的茅屋去邀请他出来帮助自己打天下，最后诸葛亮才答应出来。

D. 三个臭皮匠顶个诸葛亮是一个文化术语。指的是三个副将的智慧能顶一个诸葛亮

5、以下不可以使用分治法求解的是？（ ）

A. 棋盘覆盖问题

B. 选择问题

C. 归并排序

D. 0/1背包问题

6、使用分治算法的基本步骤是？（ ）

A. 分解、解决、合并

B. 分解、解决

C. 合并、解决

D. 合并、解决、分解

7、下列程序是分治算法的典型应用，其运行结果是？（ ）

def dividAndConquer(arr,left,right): 
    if (right == left + 1) or (right == left):     
        return max(arr[left],arr[right])     
    mid = int((left + right) / 2)    
    leftMax = dividAndConquer(arr,left,mid)    
    rightMax = dividAndConquer(arr,mid,right)    
    return max(leftMax,rightMax) 
arr1 = [8, 1, 14, 19, 5] 
print(dividAndConquer(arr1,0,4))

A. 1

B. 19

C. 8

D. 5

8、以下常见算法中，体现分治思想的是?

A. 解析算法

B. 枚举算法

C. 冒泡排序

D. 对分查找

9、下列有关分治算法思想的描述不正确的是？（ ）

A. 将问题分解成的子问题具有相同的模式

B. 当问题足够小时，可以直接求解

C. 可以将子问题的结果合并成原问题的解

D. 将问题分解出的各个子问题相互包含，相互之间可以有公共子问题

10、下列问题使用分治算法思想的是？（ ）

A. 求100以内的素数

B. 求100个整数之和

C. 求斐波那契数列第n项

D. 快速排序算法对n个数排序

11、在1-20之间玩猜数字的游戏时，如果采用二分法的策略，并且给‘大了’或‘小了’的提示，最差的情况下多少次就可以猜中？（　）

A. 5

B. 10

C. 15

D. 20

12、下列选项中，哪一项不是分治算法的特征？（　）

A. 问题的规模缩小到一定程度就可以容易解决。

B. 该问题分解出的子问题的解可以合并为该问题的解。

C. 各个子问题必须分解到不能分解为止

D. 该问题具有最优子结构性质

13、下列排序算法中利用了分治算法思想的是？（　）

A. 冒泡排序

B. 插入排序

C. 选择排序

D. 快速排序

14、关于分治算法特征的描述中，错误的是？（　）

A. 当问题的规模缩小到一定的程度就可以容易地解决；

B. 问题可以分解为若干个规模较小的相同问题；

C. 该问题所分解出的各个子问题是可以相互独立，也可以相互交叉；

D. 该问题分解出的子问题的解可以合并为该问题的解

15、用分治法查找列表中是否存在指定的数字。给定的列表已升序排序。请补全程序代码？（ ）

#在列表cards中查找数字x，返回下标值，若未找到，返回-1
def serch(cards=list,x=int):
    a=0             #定义左端点下标   
    b=len(cards)-1  #定义右端点下标    
    #逐级分割查找范围，缩小查找规模    
    while a<=b:    
        m=(a+b)//2       #定义中点下标 
        if x==cards[m]:  #x刚好等于中点值   
            return m    
        elif      ①     : #x<中点值，说明x位于左段位置   
            b=m-1        #重新定义右端点    
        else:    
            a=m+1        #重新定义左端点   
    return -1            #未找到，返回-1
#主程序
#在列表d中查找用户输入的数字r
d=[1,6,16,24,44,46,79,80,81,82,87,102,134,151,156,188,196,202,212,226,228,248,272,274,286,306,321,351,363]
print(d)    #显示一下列表d
r=int(input("请输入要查找的数字:"))
y=serch(d,r)  #调用子函数，d，r是实参
if y>=0:
    print("已找到",r,"，它是列表中第",y+1,"个数字")
else:
    print("未找到",r)

A. x<cards[m-1]

B. x<cards[m]

C. x>cards[m-1]

D. x>cards[m]

二、判断题(共5题，每题5分，共25分)

16、对于一个复杂问题，如果所分解出的各个子问题之间相互不独立，则不适合使用分治算法

​ 正确 错误

17、将一个复杂的问题分解成若干个规模较小的子问题后，能不能利用分解出的子问题的解合并得到原问题的解是最关键的特征，它决定了是否可以使用分治算法。

​ 正确 错误

18、使用分治算法求解，子问题不能重复。

​ 正确 错误

19、分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。（ ）

​ 正确 错误
20、某同学用天平称量的过程如下：先放置100克砝码，砝码偏重；再将砝码改为50克，砝码偏轻；又将砝码改为75克……通过这种策略，该同学很快完成物品称重工作，这体现了分治思想。（　）

​ 正确 错误

答案

一、单选题 1、A 2、B 3、A 4、B 5、D 6、A 7、B 8、D

9、D

试题解析：将问题分解出的各个子问题是相互独立的，即子问题之间不包含公共子子问题

10、D

试题解析：快速排序算法使用了分治算法。因此选D。

11、A

试题解析：最多5次就可以确定一个整数

12、C

试题解析：子问题分解到什么程度需要视具体问题而定，并不一定要分解到不能分解为止。其余三个选项都是分治算法的特征

13、D

试题解析：快速排序利用了分治算法思想

14、C

试题解析：该问题所分解出的各个子问题是相互独立，即该问题具有最优子结构性质

15、B

试题解析：x<cards[m]每次从中间分隔，这个实际上是二分法。分治法查找可以大规模减少比对次数，但是，原数据必须排序。

二、判断题

16、正确 17、正确 18、正确

19、正确

试题解析：分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。

20、正确

试题解析：该同学称量的过程体现了分治思想