文档介绍：该【NOIP基础算法贪心和分治pascal公开课获奖课件赛课一等奖课件 】是由【业精于勤】上传分享，文档一共【98】页，该文档可以免费在线阅读，需要了解更多关于【NOIP基础算法贪心和分治pascal公开课获奖课件赛课一等奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。NOIP基础算法——分治与贪心
巴蜀中学 黄新军
第五部分 分治方略
一、分治思想
分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题提成n个规模较小而构造与原问题相似的子问题；然后递归地解这些子问题，最终合并其成果就得到原问题的解。
二、分治法的合用条件
能使用分治法处理的问题，它们一般具有如下几种特征：
①该问题可以分解成若干互相独立、规模较小的相似子问题；
②子问题缩小到一定的程度就能轻易得到解；
③子问题的解合并后，能得到原问题的解；
分治法在信息学竞赛中应用非常广泛，使用分治方略能生成某些常用的算法和数据构造，如快排、最优二叉树、线段树等；还可以直接使用分治方略，处理某些规模很大、无法直接下手的问题。
三、分治的三环节
①分解：将要处理的问题分解成若干个规模较小的同类子问题；
②处理：当子问题划分得足够小时，求解出子问题的解。
③合并：将子问题的解逐层合并成原问题的解。
分治算法设计过程图
由分治法所得到的子问题与原问题具有相似的类型。假如得到的子问题相对来说还太大，则可反复使用分治方略将这些子问题提成更小的同类型子问题，直至产生出不用深入细分就可求解的子问题。分治求解可用一种递归过程来表达。
要使分治算法效率高，关键在于怎样分割？一般地，出于一种平衡原则，总是把大问题提成K个规模尽量相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n＝6时，等分定量成两个规模为3的子表L1和L2不是最佳分割。一般来讲，都是2分为主。
四、分治的框架构造
procedure DIVIDE()
begin
if(问题不可分)then//处理
begin
直接求解；
返回问题的解；
end
else begin
对原问题进行分治；//分解
递归对每一种分治的部分求解;
归并整个问题，得出全问题的解;//合并
end
end;
五、分治的经典应用
1、求最大值和最小值
2、非线性方程求根
3、二分查找
4、归并排序
5、迅速幂
6、求解线性递推关系
7、棋盘覆盖问题
8、循环曰程表问题
9、寻找近来点对
1、求最大值和最小值
例题1：给n个实数，求它们之中最大值和最小值，规定比较次数尽量小。
分析：假设数据个数为n,寄存在数组a[1..n]中。可以直接进行比较：
minn:=a[1];maxx:=a[1];
for i:=2 to n do
if a[i]>maxx then maxx:=a[i];
else if a[i]<minn then minn:=a[i];
使用这一算法，比较次数为2(n-1)。若n=10,则比较18次。