CCF CSP-J/S第一轮认证必考知识点:分治算法

原标题:CCF CSP-J/S第一轮认证必考知识点:分治算法

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所示。

CCF CSP-J/S第一轮认证必考知识点:分治算法

图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深度学习 │一文掌握卷积神经网络 返回搜狐,查看更多

文章来自网络转载,版权归原作者所有,如果有侵犯到您的权益,请联系本站删除,谢谢合作!