NOIP基础算法-贪心和分治pascal

《NOIP基础算法-贪心和分治pascal》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP基础算法——分治与贪心巴蜀中学黄新军第五部分分治策略一、分治思想分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。二、分治法的适用条件能使用分治法解决的问题，它们一般具备以下几个特征：①该问题可以分解成若干相互独立、规模较小的相同子问题；②子问题缩小到一定的程度就能轻易得到解；③子问题的解合并后，能得到原问题的解；分治法在信息学竞赛中应用非常广泛，使用分治策略能生成一些常用的算法和数据结构，如快排、最优二叉树、线段树等；

2、还可以直接使用分治策略，解决一些规模很大、无法直接下手的问题。三、分治的三步骤①分解：将要解决的问题分解成若干个规模较小的同类子问题；②解决：当子问题划分得足够小时，求解出子问题的解。③合并：将子问题的解逐层合并成原问题的解。分治算法设计过程图由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成K个规模尽可能相等的子问题，但也有例

3、外，如求表的最大最小元问题的算法，当n＝6时，等分定量成两个规模为3的子表L1和L2不是最佳分割。一般来讲，都是2分为主。四、分治的框架结构procedureDIVIDE()beginif(问题不可分)then//解决begin直接求解；返回问题的解；endelsebegin对原问题进行分治；//分解递归对每一个分治的部分求解;归并整个问题，得出全问题的解;//合并endend;五、分治的典型应用1、求最大值和最小值2、非线性方程求根3、二分查找4、归并排序5、快速幂6、求解线性递推关系7、棋盘覆盖问题8、循环日程表问题9、寻找最近点对1、求最大值和最小值例题1

4、：给n个实数，求它们之中最大值和最小值，要求比较次数尽量小。分析：假设数据个数为n,存放在数组a[1..n]中。可以直接进行比较：minn:=a[1];maxx:=a[1];fori:=2tondoifa[i]>maxxthenmaxx:=a[i];elseifa[i]

5、把n个数均分为两半。即：划分点为d=(r1+r2)/2，两个区间为[r1,d]和[d+1,r2]。递归求解：求左半的最小值min1和最大值max1以及右半最小值min2和最大值max2。合并：所有数的最大值为maxx，最小值为minn。procedurepd(r1,r2:integer;varmaxx,minn:integer)beginvarmax1,min1,max2,min2,d:integer;ifr1=r2thenbeginmaxx:=x[r1];minn:=x[r1];endelseifr2=r1+1thenbeginifx[r2]>x[r1]the

6、nbeginmaxx:=x[r2];minn:=x[r1];endelsebeginmaxx:=x[r1];minn:=x[r2];endendelsebegind:=(r1+r2)/2;pd(r1,d,max1,min1);pd(d+1,r2,max2,min2);ifmax1>max2thenmaxx:=max1;elsemaxx:=max2;ifmin1

7、中各项的系数(a,b,c,d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。【文件输入】输入仅一行，有四个数，依次为a、b、c、d【文件输出】输出也只有一行，即三个根(从小到大输出)【样例输入】1-5-420【样例输入】-2.002.005.00分析如果精确到小数点后两位，可用简单枚举法：将x从-100.00到100.00（步长0.01）逐一枚举，得到20000个f(x)，取其值与0最接近的三个f(x)，对应的x即为答案。而

8、题目已改成精度为小数点后