一、分治思想
例1、找伪币 [问题描述] 给你一个装有16个硬币的袋子，16个硬币中有一 个是伪造的，并且那个伪造的硬币比真的硬币要轻一 些。 你的任务是找出这个伪造的硬币。 为了帮助你完成这一任务，将提供一台可用来比 较两组硬币重量的仪器，利用这台仪器，可以知道两 组硬币的重量是否相同。
一、分治思想
[问题分析] 方法1： 先比较硬币1与硬币2的重量，假如硬币1比硬币2 轻，则硬币1是伪造的，假如硬币2比硬币1轻，则硬币 2是伪造的，假如两硬币重量相等，则说明1和2都不是 伪造的，则再继续比较硬币3和硬币4，…… 按照这种方式，可以最多通过8次比较来判断伪币 的存在并找出这一伪币。
一、分治思想
[问题分析] 方法2： 利用二分的思想。 先把16个硬币的情况看成一个大问题。 第一步，把这一大问题分成两个小问题,随机选择8 个硬币作为第一组称为A组，剩下的8个硬币作为第二 组称为B组。 第二步，判断伪币在A组还是在B组中，如果在A 组中，则再把A组中的8个硬币随机分成2组，每组4个 再去比较，…… 这样,只要(必须)4次比较一定能找出伪币。
一、分治思想
[问题分析] 方法3： 利用三分的思想。 把16个硬币分成3组（A组5个、B组5个、C组6 个），称一次判断出伪币在A、B、C哪一组中，假如 在C组中，则再把C组中的6个分成3组（2个、2个、2 个），称一次判断出在哪一组，然后再称1次就能找出 伪币，这样，只要2-3次比较便能找出伪币。
小结： 一是解题思想和方法的多样性，要善于比较和创新； 二是有些算法在最优和最差情况下的复杂度区别巨 大，往往依赖于输入数据或者处理的先后顺序，而有些 算法的复杂度则是比较稳定的，这一点要注意分析。
一、分治思想
例2、循环比赛日程表 [问题描述] 设有n个选手的循环比赛(n=2^m)，要求每名选手要 与其他n-1名选手都赛一次。每名选手每天比赛一次，循 环赛共进行n-1天，要求每天没有选手轮空。 以上是8名选手时的循环比赛表，表中第一行为8位 选手的编号，下面7行依次是每位选手每天的对手。
一、分治思想
[问题分析] 从8位选手的循环比赛表中可以看出，这是一个具有对称性的 方阵。可以把方阵一分为四来看，左上角的4*4的方阵就是前四位 选手的循环比赛表，而右上角的4*4的方阵就是后4位选手的循环 比赛表，它们在本质上是一样的，都是4个选手的循环比赛表，所 不同的只是选手编号而已，将左上角中方阵的所有元素加上4就能 得到右上角的方阵。下方的两个方阵表示前4位选手和后4位选手 进行交叉循环比赛的情况，同样具有对称性，将右上角方阵复制 到左下
角即得到1,2,3,4四位选手和5,6,7,8四位选手的循环比赛表， 根据对称性，右下角的方阵则与左上角的方阵相同。这样，8名选 手的循环比赛表可以由4名选手的循环比赛表根据对称性生成。同 样地, 4名选手的循环比赛表可以由2名选手的循环比赛表根据对称 性生成，而2名选手的循环比赛表可以说是已知的。所以，分治的 思想很明确，把一个规模为n的构造问题分成了4个规模为n/2的构 造问题，然后用这些较小问题的解构造出整个问题的解。
一、分治思想
一、分治思想
[问题分析] 程序实现时用数组matchlist记录n名选手的循环比赛表, 整个 循环比赛表从最初的1*1方阵按上述规则生成出2*2 的方阵, 再生 成出4*4 的方阵,„„直到生成出整个循环比赛表为止。变量half 表示当前方阵的大小,也是要生成的下一个方阵的大小的一半。
[参考程序] const maxn=32;maxm=5; var i,j,k,m,n,half:integer; matchlist:array [1..maxn,1..maxn] of integer; Begin readln(m); n:=1; for i:=1 to m do n:=n*2; k:=1; matchlist[1,1]:=1; half:=1;
一、分治思想
while k
一、分治思想
[总结] 从前面两个例子的分析与解决，我们发现，分治思想是将 一个难以直接解决的大问题，分解成k个规模较小的相互独立的、 相同（或类似）的子问题，以便各个击破，分而治之的策略。 最常见的就是二分法（k=2），而且根据平衡子问题的思想 一般把问题分解成两个规模相等的子问题（也可以把一个规模 为n的问题分解成一个规模为n-1的子问题和一个规模为1的元问 题等等），经典问题如二分查找、快速排序等。 分治法是程序设计中常见的考虑和处理问题的方法，主要 有以下两个特点： （1）对大问题的解决可以分解成对若干小问题的解决； （2）每个小问题的情况又与大问题的情况基本一致。
二、递归算法初步
基于以上的分治思想，分治法在每一步实现上都要 有3个步骤： （1）分解：将原问题分解为若干个规模较小、相互 独立、与原问题形式相同的子问题； （2）解决：若子问题规模较小而且容易被解决则直 接解决，否则递归地解决各个子问题； （3）合并：将各个子问题的解合并为原问题的解。 所以，分治法一般采用“递归算法”解决（递归子 程序），直接实现依赖于“系统栈”，这一点在深度优 先搜索部分应该已经作了详细介绍。
二、递归算法初步
递归算法一般适用在三个
场合： （1）数据的定义形式是递归的，如求N阶乘问题； （2）数据之间的逻辑关系(数据结构)是递归的，如树、 图等的定义和操作； （3）某些问题的解法是不断重复执行一种操作，只是 问题规模由大化小，直至某个基本操作就结束，如汉诺 塔问题。
二、递归算法初步
例3、二分查找(折半查找) [问题描述] 给定n和n个严格递增的整数，查找其中有没有x这个数。
[问题分析] procedure search(l,r:longint); begin 二分查找的前提是：数据是有序的 if l>r then writeln('no') else if x=a[(l+r) div 2] then begin writeln('yes in:',(l+r) div 2);halt;end else if x
二、递归算法初步
例4、快速排序 [问题描述] 随机产生n个整数，从小到大排序后输出他们。
[问题分析] 我们已经学习过很多O(n^2)的排序算法，如插入排序、选 择排序、冒泡排序等。而快速排序才是OI比赛中普遍使用的方法， 其时间复杂度为O(nlog2n)。 快速排序采用最朴素的“划分”思想将数据分类，就像分牌 的时候大数分一堆，小数分一堆，这样大问题就转化成了形式相 同但是规模较小的问题，在这儿，我们将所有的数划分成左边一 堆与右边一堆，左边的恒小于等于某个数，右边的恒大于等于某 个数，这样再对左右递归操作。 经过实践检验，这个数选取a[n div 2]是比较合理的。
二、递归算法初步
对于代码的实现，我们可以选用一头一尾两个指针： procedure qsort(l,r:longint) beign x=a[(l+r) div 2]; 其中： repeat while (a[i]x) do dec(j); while (a[j]>x) do dec(j); 这两句的意思： if (ij; 一下解决问题。 if l
快速排序什么情况下，效率最差？时间复杂度为多少？ 每次划分选取的基准恰好都是当前序列中的最小(或最大) 值，划分的结果是A[low..i-1]为空区间或A[i+1..high]是空区间， 且非空区间长度达到最大值。
这种情况下，必须进行n-1趟快速排序，第i趟的区间长度
为n-i+1，总的比较次数达到最大值：n(n-1)/2，复杂度O(n2)。
所以，基准的选择决定了快速排序算法的性能。经常采用
选取low和high之间一个随机位置作为基准的方式改善性能。 从而克服最坏情况下的构造数据，保证算法效率的稳定性。
几个考试题目： 1、对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为 A．1，2，3 B．9，5
，2，3 C．9，5，3 D．9，4，2，3 。
2、下列序列中， 是执行第一趟快速排序后得到的序列(排序的关键字 类型是字符串)。 A.[da,ax,eb,de,bb] ff [ha,gc] B.[cd,eb,ax,da] ff [ha,gc,bb] C.[gc,ax,eb,cd,bb] ff [da,ha] D.[ax,bb,cd,da] ff [eb,gc,ha]
3、下列排序算法中， 算法可能会出现下面情况：初始数据有序时， 花费的时间反而最多。 A．堆排序 B.冒泡排序 C．快速排序 D．SHELL排序 4、下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其 时间性能受数据初始特性影响的是 。 A.直接插入排序 B.快速排序 C.直接选择排序 D.堆排序 答案：D、A、C、B
二、递归算法初步
例5、快速排序的应用：求一个数组中第k大的数。
[算法分析] 算法1： 对N个元素进行排序，输出第k个位置上的数，时间复杂度 为O(Nlog2N)； 算法2： 我们采用一种基于快速排序算法的思想，先选取一个数x将 数组重新排序，使得左边的数都比x小右边的数都比x大，那么， 我们如果要找第k大的数，若左区间的总含量比k大那么继续在 左区间中寻找（因为右区间对第k大的数是没有影响的），若k 在右区间中，问题就划归（若记在左区间中有t个数）成在右区 间中寻找第k-t大的数，问题得以减小范围递归求解。 代码如下：
二、递归算法初步
procedure find(l,r,k:longint) beign x=a[(l+r) div 2]; repeat while (a[i]x) do dec(j); if (ij; if k=j then exit(a[j]); if kj then find(i,r,k-j); end;
三、递归算法分析
1、递归算法的缺点 首先，直接递归存在着大量“冗余”计算，往往会 造成程序的效率很低。谁试过用朴素的“递归函数”计 算Fibonacci数列的第50项吗，要多久？ 其次，如果递归的边界条件设置不当，经常造成死 循环或者内存(系统栈)溢出的窘境，导致递归深度有限。 最后提醒，一般在递归子程序中不要定义局部数组， 为什么？ 2、递归算法的优化 （1）递归转化为递推：学会用递归的思想去分析问题， 用递推的方法解决问题。
三、递归算法分析
例6、偶数个3 [问题描述] 在所有的N位数中(0
为偶数 的个数，则有如下边界条件：a[1]=1，b[1]=8。 递归公式为： a[i]=a[i-1]*9+b[i-1]，b[i]=b[i-1]*9+a[i-1]。
三、递归算法分析
然后，我们采用递推的方法逐步构造来实现，程序代码如下： var a,b:array[0..1000]of longint; i,n:longint; begin a[1]:=8; b[1]:=1; readln(n); for i:=2 to n do begin a[i]:=(9*a[i-1]+b[i-1])mod 12345; b[i]:=(9*b[i-1]+a[i-1])mod 12345; // (A+B) mod K = ((A mod K) + (B mod K)) mod K end; writeln(a[n]); end.
三、递归算法分析
2、递归算法的优化 （1）递归转化为递推：学会用递归的思想去分析问题， 用递推的方法解决问题。
（2）采用记忆化：设置一个记忆数组，避免盲目递归， 减少冗余计算。 例7、求Fibonacci数列的第1000项，因为太大，所以 只要输出 f(1000) mod 9997的值即可。
三、递归算法分析
const max=1000; var a:array[1..max] of integer; {记忆数组} function f(n:integer):integer; {记忆化} begin if a[n]0 then f:=a[n] {查表} else if n=1 then begin a[1]:=1;f:=1;end else if n=2 then begin a[2]:=1;f:=1;end else begin a[n]:=(f(n-1)+f(n-2)) mod 9997; {记忆} f:=a[n]; end; end; begin fillchar(a,sizeof(a),0); writeln(f(1000)); readln; end.
三、递归算法分析
2、递归算法的优化 （1）递归转化为递推：学会用递归的思想去分析问题， 用递推的方法解决问题。
（2）采用记忆化：设置一个记忆数组，避免盲目递归， 减少冗余计算。 （3）转化为非递归：方法多样，有时需要定义一个手 工栈，用来保存和恢复递归过程中的现场，从而模拟递 归调用。这种做法的缺点是减低了程序的可读性。
例8、以下是用递归法把一个十进制正整数转换成八进 制的程序，请用非递归实现。
三、递归算法分析
var m:longint； procedure tran(n:longint)； var k:longint； begin k:=n mod 8； if n div 80 then tran(n div 8)； write(k); {倒序输出，两个语句的顺序不能倒} end； top:=0; begin while n0 do begin readln(m)； top:=top+1; write(m，'=(')； stack[top]:=n mod 8; tran(m)； n:=n div 8; writeln(')8')； end; end. 逐个元素出栈
四、分治思想与递归算法的应用举例
递归分治的思想应用非常广泛，不仅可以用来计算、 计数，而且还可以用来枚举，即把所有具有某种特性的 对象完全枚举出来(递归搜索)，而关键是如何从输入参 数与输出结果之间的对应关系中归纳出递归公式和边界 条件。
四、分治思想与递归算法的应用举例
例9、取余运算（mod，作业1） [问题描述] 输入b，p，k的值，求bp mod k的值。其中b，p， k*k为长整型数。 [输入输出样例] mod.in 2 10 9 mod.out 2^10 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 的19次方除以K的余数转换为求B的9次方除以K的余数，即 B19=B2*9+1=B*B9*B9，再进一步分解下去就不难求得整个问题的 解。
四、分治思想与递归算法的应用举例
这是一个典型的分治问题，具体实现的时候是用递推的方法 来处理的，如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， 求解的过程也就是将二进制数还原为十进制数的过程。 具体实现请看下面的程序，程序中用数组binary存放P对应 的二进制数，总位数为len，binary[1]存放最底位。变量rest记录 每一步求得的余数。
四、分治思想与递归算法的应用举例
readln(b,p,k); {输入三个数} len:=0; temp:=p; while temp0 do {存放p的二进制转换} begin len:=len+1; binary[len]:=temp mod 2; temp:=temp div 2 end; rest:=1; for i:=len downto 1 do {用二分法实现b^p mod k} begin temp:=rest*rest mod k; if binary[i]=1 then rest:=b mod k * temp mod k {奇数就多乘b} else rest:=temp {否则就是rest*rest} end; writeln(b,'^',p,' mod ',k,' = ',rest); {输出b^p mod k}
四、分治思想与递归算法的应用举例
例10、小车问题（car） [问题描述] 甲、乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆小车， 可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样， 且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。 [问题输入] 仅一行三个数，分别表示AB两地的距离s，人的步行速度a，车的速度b。 [问题输出] 两人同时到达B地需要的最短时间，保留小数点后面两位。 [输入输出样例] car.in 120 5 25 car.out 9.60
四、分治思想与递归算法的应用举例
[问题分析] 最佳方案为：甲先乘车到达K处后下车步行，小车再回头接 已走到C处的乙，在D处相遇后，乙再乘车赶往B，最后甲、乙一 起到达B地。如下图所示，这时所用的时间最短。这样问题就转 换成了求K处的位置，我们用二分法，不断尝试，直到满足同时 到达的时间精度。
四、分治思想与递归算法的应用举例
算法框架如下： 1、输入s，a，b； 2、c0:=0
；c1:=s；c:=(c0+c1)/2； 3、求出此时甲乙两人分别到达终点的时间t1，t2； 4、如果t1
四、分治思想与递归算法的应用举例
例11、集合的划分 [问题描述] 设S是一个具有n个元素的集合，S＝｛a1，a2，……，an｝， 现将S划分成k个满足下列条件的子集合S1，S2，……，Sk ，且 满足： 1．Si ≠ φ 2．Si ∩ Sj ＝ φ (1≤i，j≤k i≠j) 3．S1 ∪ S2 ∪ S3 ∪ …… ∪ Sk ＝ S 则称S1，S2，…… ，Sk是集合S的一个划分。 它相当于把S集合中的n个元素a1，a2，……，an放入k个无 标号的盒子中，使得没有一个盒子为空。 请你编程计算划分数S(n，k)，0＜k≤n＜30。 样例输入：23 7 样例输出：[**************]5
四、分治思想与递归算法的应用举例
[问题分析] 先举个例子，设S＝｛1，2，3，4｝，k＝3，不难得出S有6 种不同的划分方案，即划分数S(4，3)=6，具体方案为： ｛1，2｝∪｛3｝∪｛4｝ ｛1，3｝∪｛2｝∪｛4｝ ｛1，4｝∪｛2｝∪｛3｝ ｛2，3｝∪｛1｝∪｛4｝ ｛2，4｝∪｛1｝∪｛3｝ ｛3，4｝∪｛1｝∪｛2｝ 考虑一般情况，对于任意的含有n个元素a1，a2，……，an 的集合S，放入k个无标号的盒子中去，划分数为S(n，k)，我们 很难凭直觉和经验计算划分数和枚举划分的所有方案，必须归纳 出问题的本质。
四、分治思想与递归算法的应用举例
对于任一个元素an，则必然出现以下两种情况： 1、｛an｝是k个子集中的一个，于是我们只要把a1，a2， ……，an-1划分为k－1子集，便解决了本题，这种情况下的划分 数共有S(n－1，k－1)个； 2、｛an｝不是k个子集中的一个，则an必与其它的元素构成 一个子集。则问题相当于先把a1，a2，……，an-1划分成k个子集， 这种情况下划分数共有S(n－1，k)个；然后再把元素an加入到k 个子集中的任一个中去，共有k种加入方式，这样对于an的每一 种加入方式，都可以使集合划分为k个子集，因此根据乘法原理， 划分数共有k * S(n－1，k)个。 综合以上两种情况，应用加法原理，得出n个元素的集合划 分为k个子集的划分数为： S(n，k)＝S(n－1，k－1) + k * S(n－1，k) (n>k，k>0)
四、分治思想与递归算法的应用举例
下面，我们来确定这个递归公式的边界条件。 首先，不能把n个元素不放进任何一个集合中去，即k=0时， S(n，k)＝0； 其次，也不可
能在不允许空盒的情况下，把n个元素放进多 于n的k个集合中去，即k＞n时，S(n，k)＝0； 再者，把n个元素放进一个集合或把n个元素放进n个集合， 方案数显然都是1，即k=1或k=n时，S(n,k)=1。
[问题拓展] 如果是求n个元素a1,a2,„„,an放入k个有标号的盒子中去， 每个盒子至少一个，划分数是多少？
解答：在原问题上对k个盒子进行全排列，所以答案为：k!*S(n,k)
四、分治思想与递归算法的应用举例
例12、地毯填补问题（blank，作业2） [问题描述] 相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个 四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简 单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站 立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。 公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有 四种选择(如下图)：
并且每一方格只能用一层地毯，迷宫的大小为2的k次方见方 的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你 使用的是计算机，所以实现时间为1秒。
四、分治思想与递归算法的应用举例
[输入] 输入文件共2行。 第一行：k，即给定被填补迷宫的大小为2k（0
blank.out 551 224 114 143 412 441 273 154 183 363 481 722 514 632 812 841 771 661 583 852 881
四、分治思想与递归算法的应用举例
[问题分析] 拿到这个问题后，便有一种递归重复的感觉。首先对最简单 的情况(即k=1)进行分析：公主只会在4个方格中的一个： 左上角：则使用3号毯子补，毯子拐角坐标位于（2，2）； {下面就简称为毯子坐标} 左下角：则使用2号毯子补，毯子拐角坐标位于（1，2）； 右上角：则使用1号毯子补，毯子拐角坐标位于（2，1） 右下角：则使用4号毯子补，毯子拐角坐标位于（1，1）；
其实这样不能说明什 么问题，但是继续讨论就 会有收获，即讨论k=2的 情况（如下图）：
四、分治思想与递归算法的应用举例
我们假设公主所在的位置用实心圆表示，即上图中的（1，4）， 那么我们就可以把1号毯子放在（2，3）处，这样就将（1，3） 至（2，4）的k=1见方全部覆盖（#表示地毯）。接下来就是3个 k=1的见方继续填满，这样问题就归结为k=1的情况了，但是有 一点不同的是：没有“公
主”了，每一个k=1的小见方都会留下 一个空白（即上图中的空心圆），那么空白就有：1*3=3个，组 合后便又是一个地毯形状。 好了，现在有感觉了吧，我们用分治法来解决它！对于任意 k>1的宫殿，均可以将其化分为4个k/2大小的宫殿，先看一下公 主站的位置是属于哪一块，因为根据公主所在的位置，我们可以 确定中间位置所放的毯子类型，再递归处理公主所站的那一块， 直到出现边界条件k=1的情况，然后在公主边上铺上一块合适的 地毯，递归结束。 由于要递归到每一格，复杂度就是面积，就是O(22*k *k)。
Thanks for listening Questions are welcome