分治法与二分答案

1、分治法与二分答案常州一中常州一中 秦珂钰秦珂钰分治法问题导入 如果给你一个装有16个硬币的袋子，其中有一个是伪造的，并且那个伪造硬币的重量和真硬币的重量不同。你能不能用最少的比较次数找出这个伪造的硬币？为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。初步想法 常规的解决方法是先将这些硬币分成两个一组，每一次只称一组硬币，如果运气好的话只要称1次就可以找到，最多称8次就可以找出那枚硬币。这种直接寻找的方法存在着相当大的投机性。这种方法适用于硬币数量少的情况，在硬币数量多的情况下就成为一件费时费力又需要运气的事。新的思路 试着改变一下方

2、法：如果我们将一组硬币分成两小组，将原来设计的一次比较两枚硬币变为一次比较两组硬币，我们会发现通过一次比较后，完全可以舍弃全部是真币的一组硬币，选取与原有问题一致的另一半进行下一步的比较，这样问题的规模就明显缩小，而且每一次比较的规模都是成倍减少。方法解读归纳结论根据以上分析，我们可以得到以下的结论：1、参与比较的硬币数量越多，使用该方法来实现就越快，而且投机性大大减少；2、解决方法关键在于能将大问题分割成若干小问题； 3、小问题与原有问题是完全类似的。 通常我们将这种大化小的设计策略通常我们将这种大化小的设计策略称之为分治法，即称之为分治法，即“分而治之分而治之”的意思的意思。 分治法是将一

3、个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。侧重点在于能各个击破。分治法在设计检索、分类算法或某些速算法中很有效的。最常用的分治法是二分法、归并法、快速分类法等。例1：循环比赛 问题描述： 设有N个选手的循环比赛。其中N=2M，要求每名选手要与其他N-1名选手都赛一次。每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。 输入：一行一个数，N，如题意 输出：表格形式的比赛安排表例1：循环比赛样例输入： 样例输出：3 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5

4、6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1例1：循环比赛样例说明：例1：循环比赛样例说明： 让我们以表格的中心为拆分点，将表格分成A、B、C、D四个部分，就很容易看出A=D，B=C。而且这个规律同样适用于各小部分。这样对八个队的赛事排列就逐步减化为对4个队的排列，然后又进一步地减化为2个队的排列，最后就成为1个队的排列。Begin求2M的值 N；将数组A的第一行赋初值； for s:=1 to k do S表示层数 begin n:=n /2； for t:=1 to n do for I:=m+1 to 2*m

5、do for j:=m+1 to 2*m do begin aI,j+(t-1)*m*2 := aI-m,j+(t-1)*m*2-m； a I,j+(t-1)*m*2-m := aI-m, j+(t-1)*M*2 end；m:=m*2endEnd.例1：循环比赛例2：残缺棋盘 问题描述： 残缺棋盘是一个个方格的棋盘，其中恰好有一个方格残缺，现在要求用三格板覆盖棋盘，在此覆盖中两块三格板不能重叠，三格板也不能覆盖在残缺的方格上。 当k=1时各种可能的残缺棋盘如图所示，其中残缺部分用阴影表示。例2：残缺棋盘 问题描述： 残缺棋盘是一个个方格的棋盘，其中恰好有一个方格残缺，现在要求用三格板覆盖棋盘，

6、在此覆盖中两块三格板不能重叠，三格板也不能覆盖在残缺的方格上。 当k=1时各种可能的残缺棋盘如图所示，其中残缺部分用阴影表示。例2：残缺棋盘 问题描述： 三格板的四个不 同方向如图所示 输入：第一行输入棋盘总行数，第二行输入残缺的 格子坐标。 输出：覆盖的矩阵图例2：残缺棋盘 样例输入4 4 1 样例输出 2 2 3 3 2 1 1 3 4 4 1 5 0 4 5 5例2：残缺棋盘 问题分析： 很明显，当K=0时是不需要三格板的，而当K=1时只需要1块三格板就够了。那么关键在于K1时情况就有些复杂了，以K=2时的某一种情况（如图4_5所示）为例，如果我们按一般的搜索来实现也是可行的，但在时间上

7、会有很多浪费。不妨先归纳一下放三格板时是否有规律可循： 如果将第一块三格板放在如图所示的位置上时，让区域居中的原来无阴影的小区域都变成有一个阴影，这样四个相等小区域都缺了一角，问题一下子明朗了。function fugai (tr,tc,dr,dc,size:integer )； IF size=1 then 结束 ； Title := title + 1 ； 三格板数目+1 Size := size div 2 ； 区域大小减半 IF 残缺格在上部 then if 残缺格在左部then begin 将右下角设为阴影，填上三格板编号； 分别对四个小区域进行覆盖 EndElse begin 将左

8、下角设为阴影，填上三格板编号； 分别对四个小区域进行覆盖 EndElse if 残缺格在左部then begin 将右上角设为阴影，填上三格板编号； 分别对四个小区域进行覆盖 EndElse begin 将左上角设为阴影，填上三格板编号； 分别对四个小区域进行覆盖 End例2：残缺棋盘例3：数的查找 问题描述： 对于给定的n个元素的数组a1 : n ，要求从中找出第k小的元素。输入：第一行是总数N和K 第二行是N个待比较的元素。输出：第K小的数在数组中的位置。 样例输入 样例输出5 3 1 23 8 91 56 4例3：数的查找 问题分析： 对于一组混乱无序的数来说，要找到第K小的元素通常要经

9、过两步方可实现：第一步：将数进行排序；第二步：确定第K个位置上的数。 传统的排序算法（插入排序法、选择排序法等）大家已经非常熟悉了，但已学过的排序方法无论从速度上，还是从稳定性方面都不是最佳的，因此在实际运用中一般不大用。事实上用归并排序或堆排序的方法来实现排序相对而言是较快较稳的，或者通过避免排序的方法同样也可以有效地提高查找的效率。例3：数的查找 问题分析： 下面是一列由10个元素组成的数组： 7 2 6 8 10 1 6 22 9 4 假设要找出K=3的元素，我们不妨可以这样处理：将7作为一个参照数，将这个元素中比7小的数放在7的左边，比7大或相等的数放在7的右边，这样我们可以得到第一次

10、数组的调整： 4 2 6 6 1 7 10 22 9 8 由此可知：比7小的数有5个，那么7应该是该数组中第6个小的元素。题目要求K=3，那么我们就应该将数的搜索范围缩小到7的左边，以4为参照数，确定4的实际位置为：1 2 4 6 6 由此可知：4应该是第3个小的元素，正是题目所要找的数。Procedure Select ( left , right , k：integer )；Begin 根据left 和right的值求出数列的总个数n； 排除掉K不允许出现的情况：(kn) or (ktemp then select(temp+left，right,ktemp) 从数列的右半边找 else

11、select(right,temp+left2,k)； 从数列的左半边找 End；例3：数的查找function template ( right , left :integer )：integer；var temp ，I ， j ：integer ；begin I:=right； J:=left； while ( ji ) do begin while ( a I =a I ) do I :=I+1； temp := a I ； a I := a j ； a j :=temp； end；template := j ；end；例3：数的查找 问题分析： 从代码中可以看中，这种方法和我们最常调用

12、的一种排序方法快排的程序段很像。其实本题的思想与快排类似，只是运行次数不一定会达到排序所要求的，在时间效率上提高了很多。 调用快速排序：复杂度 O(n*logn) 把快速排序优化，递归时只向包含第 k 大数的方向递归，复杂度O(n) 详见 快速排序及求第K大数.txt例3：数的查找例4：归并排序 问题描述： 对一组无序的整数用归并法进行排序。输入：第一行为数列的总个数 第二行为待排序的数列。输出：排序后的数列。 样例输入 样例输出8 2 3 4 5 6 7 8 10 10 4 6 3 8 2 5 7 问题分析： 例4：归并排序例5：取余运算 问题描述： 输入b，p，k的值，求bp mod k的

13、值。 其中b，p，k*k为长整形数。 输入输出样例： mod.in 2 10 9 mod.out 210 mod 9=7 问题分析： 本题主要的难点在于数据规模很大（b，p是长整型数），对于bp显然不能死算，时间复杂度和编程复杂度都很大。 下面先介绍一个原理：A*B mod K=（A mod K）*（B mod K ）mod K。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢？显然对于任何一个自然数P，有P=2 * P div 2 + P mod 2，如19=2* 19 div 2 + 19 mod 2=2*9+1，利用上述原理就可以把B的1

14、9次方除以K的余数转换为求B的9次方除以K的余数，即B19=B2*9+1=B*B9*B9，进一步分解下去就不难求得整个问题的解。 例5：取余运算 问题分析： 这是一个典型的分治问题，具体实现的时候是用递推的方法来处理的，如P=19，有19=2*9+1，9=2*4+1，4=2*2+0，2=2*1+0，1=2*0+1，反过来，我们可以从0出发，通过乘以2再加上一个0或1而推出1，2，4，9，19，这样就逐步得到了原来的指数，进而递推出以B为底，依次以这些数为指数的自然数除以K的余数。不难看出这里每一次乘以2后要加的数就是19对应的二进制数的各位数字，即1，0，0，1，1，19=（10011）2，求

15、解的过程也就是将二进制数还原为十进制数的过程。 例5：取余运算例6：MASON 问题描述： 形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。 任务：从文件中输入P（1000P3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）。例6：MASON输入：整数P（1000P3100000）。输出：第一行：十进制高精度数2P-1的位数； 第2-11行：十进制高精度数2P-1的最后500位数字 （每行输出50位，共输出10行

16、，不足500位时高位补0）； 不必验证2P-1与P是否为素数。mason.in1279mason.out38600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248

17、323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087 例6：MASON 问题分析： 本题的解题方法很多，其中分治也是一种巧妙的方法。首先可以想

18、到，2n=(2(n div 2)2*2(n mod 2)，即：如果要计算2n，就要先算出2(n div 2)，然后用高精度乘法算它的平方，如果n是奇数还要再乘以2，写成递归公式就是f(n)=(f(n div 2)2 * 2(n mod 2)。当然，递归是要有边界值的，当n=0时，f(n)=1。还要补充一点，该数的长度是可以用公式计算的，所以在做高精度乘法时，只要取最后500位运算就行了。例7：剔除多余括号 问题描述： 输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价。注意：输入a+b时不

19、能输出b+a。表达式以字符串输入，长度不超过。 输入不要判错。所有变量为单个小写字母。 不要求对表达式化简。 输入：原表达式输出：经过处理的表达式样例输入(a*b)+c/d a*b+c/d样例输出a*b+c/d a*b +c/d 例7：剔除多余括号例7：剔除多余括号 问题分析： 例如，剔除表达式（a+b）*f）-（i/j）中多余的括号。依据上述算法进行整理的过程如下： 最后，自底向上得整理结果：(a+b)*f-i/j分治法是程序设计中常见的解决方法，其特点主要有以下两个：（1）对大问题的解决可以分解成对若干小问题的解决；（2）每个小问题出现的情况又与大问题出现的情况是一致的。在算法实现中，我们

20、通常采用递归来实现。当然有的问题在分析时用的是递归的思路，在具体实现时只用递推的方法，这样做的目的是简化运行步骤，提高运行效率。分治法在每一层递归上都要有三个步骤：（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； （2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； （3）合并：将各个子问题的解合并为原问题的解。二分答案无处不在的二分思想 生活中，不同类型的事物间具有一些区别特征，这些区别特征总是以只具有“是/否”、“有/无”等两种对立属性的“二元偶分组”形式存在，因为这样可以最方便最快捷地确定出一个元素。 就例如猜数游戏。想一个数字由你来猜

21、，告诉你你的猜测是大了还是小了。 这样一来，我们就可以不断的缩小答案区间，减少枚举的规模，最终得到答案。二分思想应用的举例 猜数字 单调函数找零点 快速排序 找第K大数 二分查找 二分查找 有序数列中寻找某一个数 每一次查找的时间复杂度为logN二分答案 顾名思义，即利用二分枚举，判断这个值是否满足要求，不断逼近答案，最终得到答案。 适合使用二分答案的题目必须满足以下特征： 1、候选答案必须在一个明确的区间内； 2、候选答案必须是离散的（如果答案是连续的，那么在一定的精度范围内可以转化为离散问题）； 3、候选答案在区间内某种属性依次排列，各个类别不能混杂（即满足单调性）。二分答案 在解决二分答

22、案的题目时，通常需要分析出答案的单调性和有界性，并且需要设计出正确高效的验证算法。 由于题目的千变万化，贪心、动态规划、模拟、图论等都有可能成为验证算法。 因此，在近年的各类比赛中，二分答案的题目常常出现。例1：求方程的根问题描述： 输入m，n，p，a，b，求方程f(x)=mx+nx-px=0在a，b内的根。m，n，p，a，b均为整数，且ab；m，n，p都大于等于1。如果有根则输出精确到1E-11；如果无根则输出“NO”。样例：equation.in3 4 1 2equation.out1.5071265916E+00 根x2.9103830457E-11 f(x)例1：求方程的根 问题分析：

23、 首先这是一个单调函数，对于一个单调递增（或递减）函数，如图所示，判断在a,b范围内是否有解，解是多少。方法有多种，常用的一种方法叫“迭代法”，也就是“二分法”。先判断f(a)*f(b)0，如果满足则说明在a,b范围内有解，否则无解。如果有解再判断x=(a+b)/2是不是解，如果是则输出解结束程序，否则我们采用二分法，将范围缩小到a,x或(x,b)，究竟在哪一半区间里有解，则要看是f(a)*f(x)0还是f(x)*f(b)0then begin writeln(NO); close(output); halt end这说明在a,b区间中无解。else repeat x:=(a+b)/2; fa

24、:=f(m,n,p,a);求a的函数 fx:=f(m,n,p,x);求b的函数 if fa*fx0 then b:=x 在a,x内有解 else a:=x; 在x,b内有解 until (abs(b-a)zero); writeln(a+b)/2); writeln(f(m,n,p,(a+b)/2);输出解例2：晒衣服问题描述： 洗完衣服后，你就要弄干衣服。衣服在自然条件下用1个单位的时间可以晒干A点湿度。现在买了1台烘衣机，使用烘衣机可以 让你用1个单位的时间使1件衣服除开自然晒干的A点湿度外，还可烘干B点湿度，但在1个单位的时间内只能对1件衣服使用。 N件衣服因为种种原因而不一样湿，现在告诉你每件衣服的湿 度，要你求出弄干所有衣服的最少时间（湿度为0为干）。输入格式： 第一行N，A，B； 接下来N行，每行一个数，表示衣服的湿度； 1 = 湿度,A,B = 500000,1 = N = 500000。输出格式： 一行一个整数，表示最少时间。例2：晒衣服输入样例： 3 2 1 1 2 3输出样例： 1样例解析： 第1个单位时间内，用机器处理第3件衣服，此外， 所有衣服自然晒干2。例2：晒衣服方法1：贪心：用烘衣机尽量去处理湿度最大的衣服。方法2：二分答案 设weti为第i件衣服的湿度，当前答案的范围是： L,R。一开始答案范围是1,500000。 先二分一个