原标题：CCF CSP-J/S第一轮认证必考知识点：分治算法
分治算法，从字面上的解释是‘分而治之’，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
01
分治算法的实现框架
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
{
if(|P|<=n0) //如果问题P的规模小于n0阈值
{
resolve(P); //解决这个问题
return; //
}
//将P分解为较小的子问题 P1 ,P2 ,…,Pk
for(i= 1;i<=k;i++)
yi=Divide_and_Conquer(Pi) //递归解决Pi
T=MERGE(y1,y2,…,yk) //合并子问题
returnT;
}
02
例题分析
例题：已知有n个整数，存放在数组中，求这n个数的最大值。
解析：利用分治法来求解这个问题，算法分为两步，第一步是分，采用二分法将问题分解成简单的子问题，分解成只有一个或者两个元素的简单问题；第二步是治，将简单的子问题逐步合并，就可以得到问题的解。算法的实现方法如下图8-1所示。
■ 图8-1 分治算法示意图
intmax( inta[], inti, intj)
{
intnum1= 0,num2= 0;
if(i==j) returna[i]; //一个元素直接返回
elseif(i==j -1) returna[i]>=a[j]?a[i]:a[j]; //两个元素返回最大值
else{ //三个元素及其以上则继续分
intmid=(i+j)/ 2;
num1=max(a,i,mid);
num2=max(a,mid,j);
returnnum1>num2?num1:num2;
}
}
分治算法有一个通用的步骤：分解、解决和合并。首先就是将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；第二步，若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；最后将各个子问题的解合并为原问题的解。
03
参考书籍
《CCF CSP第一轮认证一本通》
ISBN：978-7-302-58146-8
作者：丁向民
定价：79元
04
精彩推荐
-
CCF CSP-J/S第一轮认证必考知识点：贪心算法
-
CCF CSP-J/S第一轮认证必考知识点：回溯算法
-
CCF CSP-J/S第一轮认证必考知识点：二值图像的最大连通块
-
CCF CSP-J/S第一轮认证必考知识点：哥德巴赫猜想
-
CCF CSP-J/S第一轮认证考纲详解
-
Python 韩信点兵思政案例（含优惠码）
-
Python ︱爬取天气预报信息（附视频）
-
《机器学习》实验指导书（附实验参考+代码）
-
Python爬虫综合实战 │ 创建云起书院爬虫（附代码）
-
Python爬虫实战 │ Email提醒（附代码）
-
Python深度学习 │一文掌握卷积神经网络 返回搜狐，查看更多
