day1基础算法.ppt

1、基础算法策略,长沙市第一中学 曹利国,第一部分,递推策略,递推的概念与基本思想,给定一个数的序列H0,H1,Hn,若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0in)联系起来，这样的式子就叫做递推关系。,解决递推问题的一般步骤,建立递推关系式 确定边界条件 递推求解,递推的形式,顺推法和倒推法,递推的应用分类,一般递推问题 组合计数类问题 一类博弈问题的求解 动态规划问题的递推关系,递推的应用（一般递推问题）,例题1 : Hanoi塔问题 . Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所

2、示。要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘； (2)圆盘只能在三个柱上存放； (3)在移动过程中，不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？,递推的应用（一般递推问题）,例题1 : Hanoi塔问题 . Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘； (2)圆盘只能在三个柱上存放； (3)在移动过程中，不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？,分析,设hn为

3、n 个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c 柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n=2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。 hn=2hn-1+1 边界条件：h1=1,递推的应用（一般递推问题）,例2：实数数列 一个实数数列共有n项，已知 ai=(ai-1-ai

4、+1)/2+d，(1in) (n60) 键盘输入n，d，a1，an，m，输出am。 输入数据均不需判错。,分析,根据公式ai=(ai-1-ai+1)/2+d 变形得，ai+1=ai-1-2ai+2d，因此该数列的通项公式为：ai=ai-2-2ai-1+2d，已知a1，如果能求出a2，这样就可以根据公式递推求出am ai=ai-2-2ai-1+2d (1) =ai-2-2（ai-3-2ai-2+2d）+2d =-2ai-3+5（ai-4-2ai-3+2d）-2d =5ai-4-12ai-3+8d 一直迭代下去，直到最后，可以建立ai和a1与a2的关系式。,分析,设ai=Pia2+Qid+Ria1

5、，我们来寻求Pi,Qi,Ri的变化规律。 ai=ai-2-2ai-1+2d ai=Pi-2a2+Qi-2d+Ri-2a1-2（Pi-1a2+Qi-1d+Ri-1a1）+2d =(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1 Pi=Pi-2-2Pi-1 Qi=Qi-2-2Qi-1+2 Ri=Ri-2-2Ri-1 显然，P1=0 Q1=0 R1=1 （i=1） P2=1 Q2=0 R2=0（i=2） 将初值P1Q1R1和P2Q2R2代入可以求出PnQnRn an=Pna2+Qnd+Rna1 a2=(an-Qnd+Rna1)/Pn 然后根据公式递推求出am

6、，问题解决。,改进算法,但仔细分析，上述算法有一个明显的缺陷：在求由于在求a2要运用除法，因此会存在实数误差，这个误差在以后递推求am的过程又不断的扩大。在实际中，当m超过30时，求出的am就明显偏离正确值。显然，这种算法虽简单但不可靠。 为了减少误差，我们可设计如下算法： ai=Pia2+Qid+Ria1 =Pi-1a3+Qi-1d+Ri-1a2 =Pi-2a4+Qi-2d+Ri-2a3 =Pi-2+kak+Qi-2+kd+Ri-2+kak-1 an=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1 ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2 根据公式，可以顺推

7、a2、a3、aM。虽然仍然存在实数误差，但由于Pn-k+2递减，因此最后得出的am要比直接利用公式精确得多。,递推的应用（一般递推问题）,例题：贮油点。 一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？ 编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格式如下： No. Distance(k.m.) Oil(litre) 1 2 ,分析,设W

8、ayi第i个贮油点到终点（i=0）的距离； oili第i个贮油点的贮油量； 我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。 从贮油点i向贮油点i+1倒推的方法是：卡车在贮油点i和贮油点i+1间往返若干次。卡车每次返回i+1点时应该正好耗尽500公升汽油，而每次从i+1点出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下，使i点贮足i*500公升汽油的要求（0in-1）。,倒推第一步,第一个贮油点i=1应距终点i=0处500km，且在该点贮藏500公升汽油，这样才能保证卡车能由i=1处到达终点i=0处，这就是说 Way1=500；oil

9、1=500；,倒推第二步,为了在i=1处贮藏500公升汽油，卡车至少从I=2处开两趟满载油的车至i=1处，所以i=2处至少贮有2*500公升汽油，即oil2=500*2=1000；另外，再加上从i=1返回至i=2处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升，即d1,2=500/3km，Way2=Way1+d1,2=Way1+500/3,倒推第三步,为了在I=2处贮藏1000公升汽油，卡车至少从I=3处开三趟满载油的车至I=2处。所以I=3处至少贮有3*500公升汽油，即oil3=500*3=1500。加上I=2至I=3处的二趟返程空车，合计5次。路途耗油亦应500

10、公升，即d23=500/5， Way3=Way2+d2,3=Way2+500/5；,倒推第k步, 为了在i=k处贮藏k*500公升汽油，卡车至少从i=k+1处开k趟满载车至i=k处，即oilk+1=(k+1)*500=oilk+500，加上从i=k返回i=k+1的k-1趟返程空间，合计2k-1次。这2k-1次总耗油量按最省要求为500公升，即dk,k+1=500/(2k-1) Wayk+1=Wayk+dk,k+1=Wayk+500/(2k-1)；,i=n的情形,i=n至始点的距离为1000-Wayn,oiln=500*n。为了在i=n处取得n*500公升汽油，卡车至少从始点开n+1次满载车至I

11、=n，加上从I=n返回始点的n趟返程空车，合计2n+1次，2n+1趟的总耗油量应正好为（1000-Wayn）*(2n+1)，即始点藏油为oiln+(1000-Wayn)*(2n+1)。,递推的应用（组合计数）,Catalan数 定义：一个凸n边形通过不相交于n边形内部的对角线把n边形拆分成若干三角形的不同拆分数。,分析,设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个凸n边形的任意一条边都必然是一个三角形的一条边，边P1 Pn也不例外，再根据“不在同一直线上的三点可以确定一个三角形”，只要在P2，P3，Pn-1点中找一个点Pk(1kn)，与P1、Pn 共同构成一个三角形的三个顶点，就将

12、n边形分成了三个不相交的部分(如图3所示)，我们分别称之为区域、区域、区域，其中区域必定是一个三角形，区域是一个凸k边形，区域是一个凸n-k+1边形。,分析,区域的拆分方案总数是Ck，区域的拆分方案数为Cn-k+1，故包含P1PkPn的n 边形的拆分方案数为CkCn-k+1种，而Pk可以是P2，P3，Pn-1种任一点，根据加法原理，凸n边形的三角拆分方案总数为 ， 同时考虑到计算的方便，约定边界条件C2=1。,分析,=C( 2n , n ) / ( n + 1),具体实现时，若直接用上述公式计算，对数字的精度要求较高。可将其化为递推式,再进行递推计算，并且注意类型的定义要用comp型。,Cat

13、alan数的应用（部分和序列）,n个+1，n个-1构成2n项 a1,a2,a3,a4,a2n其部分和满足a1+a2+.ak (k=1,2,3,.2n)=0的数列个数。,Catalan数的应用（加括号）,序列a1a2.ak的元素顺序保持不变，按不同结合方式插入合法圆括号对的方案数。n=4(a(bc)d)(a(b(cd)(ab)(cd)(ab)c)d)(a(bc)d),一个操作数序列，从1，2，一直到n，栈A的深度大于n。现在可以进行两种操作：1将一个数，从操作数列的头端移至栈的头端（对应栈的push操作）2将一个数，从栈的头端移至输出序列的尾端（对应栈的pop操作）。使用这两种操作，由一个操作数

14、序列就可以得到一系列的输出序列，下表为由1 2 3 生成序列2 3 1 的过程。,Catalan数的应用（栈 NOIp2003）,结合定义我们很容易能发现：如果进栈看成1，出栈看成0，在任何一位上累计的“0”的个数不大于累计的“1”的个数，因为必须在栈里有数的情况下才能向外弹数。,原题转化为n个1和n个0组成一个2n位的二进制数，要求从左到右扫描，“0”的累计数不大于“1”的累计数，求满足条件的数有多少。,任务： 你的程序将对给定的n，计算并输出由操作数序列1，2，n经过操作可能得到的输出序列总数。,分析,n个数，分别为1n，排成一个长度为n的排列。若每一个数的位置都与数的本身不相等，则称这个

15、排列是一个错排。例如，n=3，则错排有2 3 1、3 1 2。编写程序，求n的错排个数。,错排问题（经典问题）,递推的应用（组合计数）,我们设k个元素的错位全排列的个数记做：W(k)。,四个元素的错位排列W(4)我们用穷举法可以找到如下9个： (4，3，2，1)(3，4，1，2)(2，1，4，3)(4，1，2，3)(3，4，2，1)(3，1，4，2)(4，3，1，2)(2，4，1，3)(2，3，4，1),它们有什么规律呢？,分析,通过反复的试验，我们发现事实上有两种方式产生错位排列：,A.将k与(1，2，k1)的某一个数互换，其他k2个数进行错排，这样可以得到(k1)W(k-2)个错位排列。,

16、B.另一部分是将前k1个元素的每一个错位排列（有W(k-1)个）中的每一个数与k互换，这样可以得到剩下的(k1)W(k-1) 个错位排列。,根据加法原理，我们得到求错位排列的递推公式W(k):,W(k) = (k1) * W(k1)+W(k2),分析,例题3：走直线棋问题。有如下所示的一个编号为到的方格： 现由计算机和人进行人机对奕，从到，每次可以走个方格，其中为集=a1,a2, a3,.am中的元素(m=4)，规定谁最先走到第n格为胜，试设计一个人机对奕方案，摸拟整个游戏过程的情况并力求计算机尽量不败。,递推的应用（博弈问题）,题设条件：若谁先走到第N格谁将获胜，例如，假设S=1,2，从第N

17、格往前倒推，则走到第N-1格或第N-2格的一方必败，而走到第N-3格者必定获胜，因此在N，S确定后，棋格中每个方格的胜、负或和态（双方都不能到达第N格）都是可以事先确定的。将目标格置为必胜态，由后往前倒推每一格的胜负状态，规定在自己所处的当前格后，若对方无论走到哪儿都必定失败，则当前格为胜态，若走后有任一格为胜格，则当前格为输态，否则为和态。,分析,设1表示必胜态，-1表示必败态，0表示和态或表示无法到达的棋格。 例如，设N10，S1,2，则可确定其每个棋格的状态如下所示： 而N10，S2,3时，其每格的状态将会如下所示： 有了棋格的状态图后，程序应能判断让谁先走，计算机选择必胜策略或双方和（

18、双方均不能到达目标格）的策略下棋，这样就能保证计算机尽可能不败。,分析,在一个nm的方格中，m为奇数，放置有nm个数 ，如图,方格中间的下方有一人，此人可按照五个方向前进但不能越出方格,见右下图。 人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径，使其数相加之和为最大。输出和的最大值。,递推的应用（动态规划中的递推,例4：方格取数,分析,我们用坐标(x,y)唯一确定一个点，其中(m,n)表示图的右上角，而人的出发点是，受人前进方向的限制，能直接到达点(x,y)的点只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到点(x,y)的路

19、径中和最大的路径必然要从(m/2,0)到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)的几条路径中产生，既然要求最优方案，当然要挑一条和最大的路径，关系式如下： Fx,y= MaxFx+2,y-1 ,Fx+1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1+Numx,y， 其中Numx,y 表示(x,y) 点上的数字。 边界条件为：,动态规划与递推的关系,上题实质上是采用动态规划来求解,那么与递推动态规划之间到底是什么关系呢？ 我们不妨画个图(如下图)。而通常人们理解的递推关系就是一般递推关系，故认为动态规划与递推关系是两个各自独立的个

20、体。,动态规划与递推的关系,1、一般递推边界条件很明显,动态规划边界条件比较隐蔽,容易被忽视 2、一般递推数学性较强,动态规划数学性相对较弱 3、一般递推一般不划分阶段,动态规划一般有较为明显的阶段,生成树计数（Noi2007）,算法一：行列式的计算 算法二：递推：K=2时，可以证明与Fibonacci数有关，K3时可以枚举所有的联通方案，然后求出其联通方案的递推到另一个方案的系数。 /见年鉴2007的生成树计数。,第二部分,递归策略,递归的概念与基本思想,一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过

21、程或函数直接或者间接调用自己，就被称为递归调用。,递归的概念与基本思想,递归过程是借助于一个递归工作栈来实现的 问题向一极推进，这一过程叫做递推； 而问题逐一解决，最后回到原问题，这一过程叫做回归。 递归的过程正是由递推和回归两个过程组成。,递归的概念与基本思想,用递归算法求 n! 定义：函数 fact( n ) = n! fact( n-1 ) = ( n-1 )! 则有fact( n ) = n fact( n-1 ) 已知fact( 1 ) = 1,44,下面画出了调用和返回的递归示意图,递归的概念与基本思想,递归实现的代价是巨大的栈空间的耗费，那是因为过程每向前递推一次，程序将本层的实

22、在变量（值参和变参）、局部变量构成一个“工作记录”压入工作栈的栈顶，只有退出该层递归时，才将这一工作记录从栈顶弹出释放部分空间。由此可以想到，减少每个“工作记录”的大小便可节省部分空间。例如某些变参可以转换为全局变量，某些值参可以省略以及过程内部的精简。,递归的概念与基本思想,示例：求a1.n的最大者。 有如下过程： Procedure findmax(i:integer;var max:integer); var j:integer; begin max:=ai; if i=n then exit else begin findmax(i+1,j); if jmax then max:=j;

23、 end; end;,递归的概念与基本思想,起始状态就是调用findmax(1,max),而像上述过程中的变参max完全可以省略。将上述方法修改可得下面的算法： Procedure findmax(i:integer); begin if i=n then exit else begin findmax(i+1); if aimax then max:=ai; end; end;,递归的概念与基本思想,起始状态就是调用findmax(1) ，max为全局变量，同时还减少了一个局部变量的使用。尽管这只是一个很简单的例子，在本例中不做精简，程序也还是能通过，但它精简的原则对其它使用递归的程序而言却

24、是同样适用的。特别是在递归过程出现堆栈溢出情况时就应该考虑这一问题。,递归的概念与基本思想,采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。,递归的应用,解决搜索问题 处理递归定义或解决方法为递归方式的问题 实现分治思想 用于输出动态规划的中间过程,递归的应用（搜索树）,树结构是由递归定义的。因此，在解决与树有关的问题时，常常可以采用递归的方法。因为搜索产生的节点成树状结构，所以可以用递归方法解决。这类例

25、子很多，如“N后”问题，哈密顿回路，图的可着色性等等。,递归的应用,例题：钢板分割问题。设有一块正方形的钢板，现需将它分成n个小正方形。例如，当： n=2 不可能有解。 n=3 不可能有解。 n=4 可分成4个小正方形钢板。 n=5 不可能有解。 n=6 即一个大的加五个小的。 n=7 即三个较大的加四个小的。 n=8 即一个大的加七个小的。 问题为任给n，求出分成n个小正方形的方法。,递归的应用,【分析】经过分析就可以得出： （1）按n=4的方法将1个小正方形分成4个，则增加了3个正方形。 （2）以n=6为基础，由（1）可以得出n=9，12，15，。 （3）以n=7为基础，由（1）可以得出n

26、=10，13，16，。 （4）以n=8为基础，由（1）可以得出n=11，14，17，。 由此可以得出如下的递归算法：,递归的应用,procedure devide(i:integer); Begin if n8 then begin 分解成四小块； 对于其中一块devide(n-3) end else case n of 6: 按n=6分割； 7: 按n=7分割； 8: 按n=8分割； end; End;,递归的应用（实现分治思想）,不难发现，在各种时间复杂度为nlogn排序方法中，大都采用了递归的形式。因为无论是分治合并排序，还是堆排序、快速排序，都存在有分治的思想。只要分开处理，就可以采用

27、递归。其实进行分治，也是一个建树的过程。,递归的应用（例题分析）,例题2：剔除多余括号 键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余括号，原表达式中所有变量和运算符相对位置保持不变，并保持原表达式等价。 分析： 首先考虑人处理这个问题的方法，就是依靠符号来判断是否可以去括号。括号的前后，以及括号内的符号，都需要考虑。因此，可以按照人的处理方法，从最外层处理起，一层一层的去掉括号，这便是分治的思想。而由于每次分治的处理过程基本相同，用递归最为合适。,递归的应用（例题分析）,在递归过程中，对于正在处理的表达式s，如果s本身最外层就是多余括号，则去括号，并

28、处理括号内的表达式（递归调用）；否则，可沿该表达式中的最低级运算符p，将其拆为两个表达式，分别进行处理（递归调用），并获得左右两表达式中的最低级运算符c1,c2，通过与p的比较，确定是否应添加括号。 递归的终止条件为：s是变量。,递归的应用（例题分析）,例如，处理表达式(a+b)*f)-(i/j),过程如下： (a+b)*f)-(i/j),- (a+b)*f),* (i/j),/ (a+b)*f),* i/j,/ (a+b),+ f, i, j, a+b,+ a, b, 最后得出结果：(a+b)*f-i/j。,递归的应用（输出动态规划的中间过程）,动态规划对空间要求较高，若要保存中间过程用于输

29、出，则可能要增加一倍的空间需求。此时，如果采用递归输出，就完全不需要浪费这宝贵的空间。,例题：最佳航线问题,你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行，从最西的一个城市出发，单方向从西向东经若干城市到达最后一个城市（必须到达最东的城市），然后在单方向从东向西飞回起点（可途径若干城市）。除起点城市外，任何城市只能访问一次。起点城市被访问两次：出发一次，返回一次。除指定的航线外，不允许乘其他航线，也不允许使用其他交通工具。 求解的问题是：给定城市表列及两城市之间的直通航线，请找出一条旅行航线，在满足上述限制条件下，使访问的城市尽可能多。,例题分析：最佳航线问题,对这

30、一问题，我们采用了动态规划的方法。 假设城市已按从西到东编号，数组disti,j 表示城市i到城市n,再到城市j的所有可行方案中，最多能够访问的城市数目。逆推关系式为： distn,n=1; disti,j=distj,i; disti,j=max(disti,k)+1; (ji,jk=n,且存在航线kj) 如果要记录中间过程，就必须再开辟一个二维数组，就会导致程序可完成的数据规模降低。而采用递归求出路径后再输出，编程并未增加多少难度，而可处理的数据量却大大增加了。求路径的过程完全按照倒推的方法，利用dist数组得出往返的路线。 。,第三部分,分治策略,分治思想,分治(divide-and-c

31、onquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。其三个步骤如下； 分解(Divide)：将原问题分成一系列子问题。 解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。 合并(combine)；将子问题的结果合并成原问题的解。,分治思想,如果在将规模为n的问题分成k个不同子集合的情况下，能得到k个不同的可分别求解的子问题，其中1k=n，而且在求出了这些子问题的解之后，还可找到适当的方法把它们合并成整个问题的解，那么，具备上述特性的问题可考虑使用分治策略设计求解。这种设

32、计求解的思想就是将整个问题分成若干个小问题后分而治之。,分治思想,分治思想,由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。 要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成K个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n6时，等分定量成两个规模为3的子表L1和L2不是最佳分割。,分治的应用,解决一类求方程的根的问题 解决真假硬币的称量问题 基于NLgN算法效率的排序和查找问题,

33、分治的应用（求方程的根）,例题1： 一元三次方程求解 有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。 提示：记方程f(x)=ax3+bx2+cx+d，若存在2个数x1和x2，且x1x2，f(x1)*f(x2)0，则在(x1，x2)之间一定有一个根。 样例 输入：1 -5 -4 20 输出：-2.00 2.00 5.00,分析,如果精确到小数点后两位，可用简单的

34、枚举法：将x从-100.00 到100.00（步长0.01） 逐一枚举，得到20000个 f(x)，取其值与0最接近的三个f(x)，对应的x即为答案。而题目已改成精度为小数点后4位，枚举算法时间复杂度将达不到要求。 直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值。 具体方法如下：,分析,A、当已知区间(a,b)内有一个根时，用二分法求根，若区间(a,b)内有根，则必有f(a)f(b)b或f(a+b)/2)=0，则可确定根为(a+b)/2并退出过程； (2)若f(a)* f(a+b)/2)0 ，则必然有f(a+b)/2)* f(b)0

35、 ，根在(a+b)/2,b)中，对此区间重复该过程。 执行完毕，就可以得到精确到0.0001的根。,分析,B、求方程的所有三个实根 所有的根的范围都在-100至100之间，且根与根之差的绝对值=1。因此可知：在-100,-99、-99,-98、99，100、100，100这201个区间内，每个区间内至多只能有一个根。即：除区间100，100外，其余区间a,a+1，只有当f(a)=0或f(a)f(a+1)0时，方程在此区间内才有解。若f(a)=0 ，解即为a；若f(a)f(a+1)0 ，则可以利用A中所述的二分法迅速出找出解。 如此可求出方程的所有的解。,分治的应用（求方程的根）,例题2： 输入

36、m，n，p，a，b，求方程f(x)mx+nx-px0在a,b内的根。m，n，p，a，b均为整数，且ab；m，n，p都大于等于1。如果有根，则输出，精确到1E-11；如果无方程根，则输出“NO”。 【样例】 equation.inequation.out 2 3 4 1 21.5071265916E+00 2.9103830457E-11,分析,由于f(x)单调递增函数，对于一个单调递增(或递减)函数，判断在a, b范围内是否有解，解是多少。常用的一种方法叫“迭代法”，也就是“二分法”。先判断f(a)f(b)0，如果满足则说明在a, b范围内有解，否则无解。如果有解再判断x(a+b)/2是不是解

37、，如果是则输出解,结束程序，否则我们采用二分法，将范围缩小到a, x)或(x, b，究竟在哪一半区间里有解，则要看是f(a)f(x)0还是f(x)f(b)0。 对于y x，我们需要用换底公式把它换成exp(xln(y),分治的应用(分段处理),例题3： 旅行家的预算 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市 （假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车 油箱的容量C（以升为单位）每升汽油能行驶的距离D2、出发点 每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的 距离Di、每升汽油价格 Pi（ il，2，.N）。 计算结果四舍五 入至小数点后两位。如果无法

38、到达目的地，则输出“No solution”。 样例： INPUT ( D1 C D2 P N) 275.6 11.9 27.4 2.8 2 油站号I 离出发点的距离Di 每升汽油价格 1 102.0 2.9 2 220.0 2.2 OUTPUT 26.95（该数据表示最小费用）,分析,首先找到(从后向前)油价最低的加油站，显然车至该站油箱应为空，这样就可将起点至该站与该站至终点作为两段独立考虑，分别求其最小费用，二者之和即为总费用，这样一直分下去，若某段只有起点与终点两个加油站时无需再分。,分析,如某一段油价最低的加油站即为起点，则如能一次加油即到达该段终点则最好；若不能，则加满油再考虑油箱

39、有油情况下的二分法，考虑起点之外所有的加油站中从后往前油价最低的加油站，若该加油站位于起点加满油后不能到达之处，则到达该站时油箱应该为空，以该站为界将全程分为两个独立段考虑，前半段为有油情况，后半段为无油情况。,第二种情况，若该加油站处于起点加满油后能到达之处，则将该段总路程缩短为该加油站至终点的情况，该加油站在该段路程中最便宜，若从该站加满油仍不能到达终点，则继续分治即可，程序被设计成一个递归函数money，形式参数start表示起点站，形式参数stop表示终点站，形式参数rest表示到达加油站start时汽车油箱余下的油的容量，money函数最终计算出从加油站start到stop区间内的最

40、小费用。,function money (start，stop:longint；rest:real):real； Var k：longint； begin if stop-start=1 then money:=(dstop-dstart)/d2-rest)*pstart else begin k:=minp(start，stop-1)； minp(b，e:longint):longint；在b站到e 站之间从后往前找油价最低的站 if kstart 油价最低的加油站不是起点站 then money:=money(start，k，rest)+money(k，stop，0) else if ds

41、top-dstart=d2*c 在起点加满油能直接到达该段终点 then money:=(dstop-dstart)/d2-rest) * pstart else begin k:=minp(start+1 , stop-1) ; if dk - dstart = d2 * c then 在起点加满油能到达加油站k money:=(c-rest) * pstart + money(k, stop, c-(dk - dstart)/d2) else money := money(start, k, rest) + money( k, stop, O) end end end;,分治的应用(分段处

42、理),例题4：取余运算（mod.exe） 输入b，p，k的值，编程计算bp mod k的值。其中的b，p，k*k为长整型数。 【输入输出样例】 mod.in 2 10 9 mod.out 210 mod 9=7,分析,1、用高精度计算比较烦 2、转而用其他方法求解 （1）取模运算的一个规律：a*b mod k=(a mod k)*(b mod k) mod k （2）运用规律可以把样例数据分解：b19=b2*9+1=b 9b9b，其中的指数9可以继续分解为241，4再分解程220，2120，1011。反过来，我们可以从0出发，通过乘以2再加上1或0推得1，2，4，9，19，然后依次以这些数为指

43、数的自然数除以k的余数。,分析,（3）不难看出，前面乘以2后要加上的1或0就是该数对应二进制数各位上的数字1或0。如，19（10011）2 。求解的过程也就是将二进制数还原为十进制数的过程。 （4）综上所述，该题可采用分治得思想进行递推求解。,分治的应用(分段处理),例题5：求“逆序对”。 给定一整数数组A=(A1,A2,An), 若iAj,则就为一个逆序对。例如数组（3，1，4，5，2）的逆序对有,。问题是，输入n和A数组，统计逆序对数目。 1=n=30000。,分析,原始的解决方案（双重循环） C:=0; For i:=1 to n -1 do for j:=i+1 to n do if

44、aiaj then c:=c+1; 时间复杂度为O(n2),分析,采用二分法求解: 记数列ast,ed的逆序对数目为D(st,ed); mid=(st+ed)/2,则有： D(st,ed)=D(st,mid)+D(mid+1,ed)+F(st.mid,ed). 其中F(st,mid,ed)表示一个数取自Ast,mid,令一个数取自Amid+1,ed的逆序对数目。,分析,若要求计算d值的同时数列A已排序，设I,j指针分别已排序的Ast,med)和A(mid+1,ed)中的一个元素，若满足： Amid+1,Aj-1均小于Ai,但AjAi 则j-mid-1必须计入F，顺序移动I,j指针即可完成合并。

45、,找出伪币,给你一个装有1 6枚硬币的袋子。1 6枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。 为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。,分治的应用(称量问题),方法1,任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。,方法2,将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。,方法3,分析,上述三种方法,分别需要比较15次,8次,4次,那么形成比较次数差异的根本原因在哪里? 方法1:每枚硬币都至少进

46、行了一次比较,而有一枚硬币进行了15次比较 方法2:每一枚硬币只进行了一次比较 方法3:将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半,这样充分地利用了只有1枚伪币的基本性质。,分治的应用（解的合并）,例题6：赛程问题。有n个编号为1到n 的运动员参加某项运动的单循环比赛，即每个运动员要和所有其他运动员进行一次比赛。试为这n个运动员安排一个比赛日程，使得每个运动员每天只进行一场比赛，且整个比赛在n-1天内结束。输入运动员人数n（n=10000），输出一个n阶方阵A1.N,0.N-1，当J0时，AI,J表示第I名运动员在第J天的比赛对手。,由于N个运动员要进行单循环比赛，且在N-1天

47、内要结束全部比赛，经过分析，当且仅当N为2的整次幂时，问题才有解，当然解是不唯一的。这样可以将运动员分成两组： 1,2,N2 和 N21,N22,N。给第一组运动员安排一个比赛日程，得到一个N2阶的方阵A1；同时给第二组的运动员安排一个比赛日程，同样会得到一个N2阶的一个方阵A2。考虑到比赛的性质，设定第I个运动员在某一天的比赛对手为第K个运动员，则第K个运动员在同一天的比赛对手必然是第I个运动员，即若有AI,J=K，则AK，J=I。因此原问题的解(一个N阶方阵)可以由分解后的两个子问题的解，合并起来。同时每一个子问题又可以按照上述的二分法分解下去，直至每个组中仅有2个运动员时为止。,proc

48、edure arrangment(K,N:integer); 从K号运动员起的共N员运动员单循环比赛日程表的过程 begin if n=2 then 处理只有2名运动员的情况，递归终止条件 begin AK,0:=K;AK,1:=K+1; AK+1,0:=K+1; AK+1,1:=K; end else begin arrangment(K,N div 2); arrangment(K + N div 2,N div 2); 递归分解原问题与求解子问题 for I:=K to K +(N div 2) 1 do 合并子问题的解,构造原问题的解AI,J for J:=(N div 2) to N

49、-1 do AI,J:=AI+(N div 2),J-(N div 2); for I:=K+(N div 2) to K +N 1 do for J:=(N div 2) to N-1 do AI,J:=AI-(N div 2),J-(N div 2); end; end;,第三部分,贪心方法,贪心方法的基本思想,贪心是一种解题策略，也是一种解题思想 使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优 利用贪心策略解题，需要解决两个问题： 该题是否适合于用贪心策略求解 如何选择贪心标准，以得到问题的最优解,适用于贪心策略求解的问题的特点,适用于

50、贪心策略求解的问题必须具有最优子结构的性质，但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法动态规划（例如“0-1背包问题”与“部分背包问题”）,贪心方法的应用,例题1：节点网络。 现有一个N！个节点的网络，每个节点的编号都是编号（A1A2A3AN）序列的一个置换。对于任意两个节点S和T，如果T的编号是由S编号的首位与除首位外的编号中任一位交换所得 ，则S和T之间有一条边，求从给定节点S走到节点（A1A2A3AN）所需经过的最少边数。其中，n100。,贪心方法的应用,例如n=3的情况：,贪心方法的应用,【分析】从题意表面上看，本题是一个求最短路径

51、的问题，但题设中的N100，也就是说图中最多有100！个节点，采用二维关系的图结构根本无法存贮这众多的状态。通过问题的本质分析，可以将问题转化为一个序列的最优转化问题。,贪心方法的应用,采用贪心策略： 每次让一个节点归位或为下一步工作做准备。 其具体步骤为： 若序列中第一个点为Ax (x1)，则将第一个点和第x个点交换。这便完成了让一个点归位的工作； 若第一个是A1，则任找一个编号与位置不相符的点，并与之交换。这样下一步便可让交换到1号位置的点归位。,贪心方法的应用,一共经过4步完成。,下面看一个n=4，初始序列为(A3A4A1A2)的推演过程：,贪心方法的应用,例题2：d-规则问题。 对任意

52、给定的m(mN+)和n(nN+)，满足m1，使得KaP，则修改P为：P=P-y|y=sa,sN+ ，并称该d规则具有分值a。现要求编制一个程序，对输入的m,n值，构造相应的初始集合P，对P每应用一次d规则就累加其相应的分值，求能得到最大累加分值的d规则序列，输出每次使用d规则时的分值和集合p的变化过程。,贪心方法的应用,【分析】 初看这一问题，很容易想到用贪心策略来求解，即选择集合中最大的可以删除的数开始删起，直到不能再删除为止，而且通过一些简单的例子来验证，这一贪心标准似乎也是正确的，例如，当m=3，n=10时，集合P3,10，运用上述“贪心标准”可以得到这一问题的正确的最优解d=54312

53、，即其d-规则过程如下： 1. a=5 P=3,4,6,7,8,9d=5 2. a=4 P=3,6,7,9d=5+4=9 3. a=3 p=7 d=5+4+3=12,贪心方法的应用,但是，如果再仔细地分析一个例子，当m=3，n18时，如果还是使用上述“贪心标准”，则得到问题的d-规则总分为d=35，其d-规则序列为（9,8,7,6,5），而实际上可以得到最大d-规则总分为d38，其对应的d-规则序列为（9,8,7,6,3,5）。 为什么会出现这样的反例呢？这是因为，问题中要使得d-规则总分d值越大，不光是要求每一个d分值越大越好，也要求取得的d分值越多越好。 因此，本题不能采用纯粹的贪心策略求

54、解。,贪心方法的应用,【改进】 将原算法基础上进行改进。下面给出新的算法： 建立集合P=m.n 从n div 2到m每数构造一个集合ci，包含该数在P中的所有倍数（不包括i本身） 从n div 2起找到第一个元素个数最少但又不为空的集合ci 在d分值中加上i 把i及ci集合从P集中删除，更新所有构造集合的元素 检查所有构造集合，若还有非空集合，则继续3步骤，否则打印、结束,贪心方法的应用,下面看m=3, n=18时的推演过程： 初始P=3.18 找到i=9, ci=18, P=3.8,10.17 找到i=8, ci=16, P=3.7,10.15,17 找到i=7, ci=14, P=3.6,

55、10.13,15,17 找到i=6, ci=12, P=3.5,10,11,13,15,17 找到i=3, ci=15, P=4,5,10,11,13,17 找到i=5, ci=10, P=4,11,13,17 到此所有构造集合全部为空，d=9+8+7+6+3+5=38,贪心方法的应用,讨论： 能否证明此贪心策略是正确的？ 能否找到其他更好的算法？,贪心方法的应用,例题3：射击竞赛 射击的目标是一个由RC(2RC1000)个小方格组成的矩形网格。每一列恰有2个白色的小方格和R-2个黑色的小方格。行从顶至底编号为1R，列从左至右编号为1C。射击者可射击C次。 在连续的C次射击中，若每列恰好有一个

56、白色的方格被射中，且不存在无白色方格被射中的行，这样的射击才是正确的。 如果存在正确的射击方法，则要求找到它。,贪心方法的应用,射击的选择有2C种，符合要求的却很少。要解决问题，还需从正确的射击方法的特征入手。,贪心方法的应用,【方法一】网络流算法 我们将表示列的点编号为1到C，表示行的点编号为C+1到C+R，如果一个白色方格处在第i行第j列，那么从点j向点C+i连一条弧，弧的容量为1。再增设一个源点S，从点S往点1到C间各连一条弧，弧的容量为1，又设一个汇点T，从点C+1到点C+R向汇点T连一条弧，弧的容量为1，那么从源点S到汇点T求最大流，求出的最大流量即为最多可以射击到的行数。各条流的路

57、线则描述了具体的射击方案。 可以看出，如果用网络流求出的最大流量比R小，则问题无解，否则我们可以先根据网络流的结果求出该二分图的具体匹配方案。,贪心方法的应用,红色的连线流量为1 蓝色的连线流量为0 选择的射击格即为： (1,3), (2,1), (3,2), (4,4),贪心方法的应用,网络流算法经过优化，时间复杂度可以达到O(C(n+4C+4R) 上述网络流算法虽然可以通过全部数据，但编程复杂度很高，而且极易出错，一不小心就会因为一个小错误影响整个程序。,贪心方法的应用,【方法二】贪心方法 统计所有行包含的白格数 从还没有射击格的行中选出一个白格数最少的 检查所选的行 若所选行的白格数为0

58、，则输出无解； 否则从所选行的白格中任选一个作为射击格，并将与该格同列的另一个白格所处行的白格数减1 返回到第2步，直到所有的行都有射击格。 若还有列没有选射击格，则在该列任选一白格作为射击格即可,贪心方法的应用,上面的贪心方法非常高效： 时间复杂度为O(RC)，如果在程序中使用堆优化，时间复杂度将降为O(Rlog2C)。空间复杂度是线性的，而且非常容易实现。 现在关键的问题就是如何证明它的正确性？,贪心方法的应用,【证明】 用hi表示第i行的白格数。如果最开始的时候： minhi=0: 第i行已经没有办法找到可作为射击格的白格，那么问题只能无解。 minhi=1: 那么第i行的这一个白格必须要作为射击格，否则将因第i行没有射击格而造成问题无解。 minhi2: 那么在这一行任选一个白格，顶多只会造成剩余行中有一行h值为1，再处理那一行，最多也只会再造成剩余行中有一行h值为1，如此往复，将保持h值为1的行数不超过1行，最后最坏的情况也是造成最后一行的h值为1，继续下去所有行就都已选取了射击格了。 因此，如果原问题有解，该贪心方法一定能找到一种正确的方案。 由此可以证明，此贪心方法是正确的。,贪心方法的应用,例题4：Transversal 有一个(2n+1)(2n+1)的矩阵，每个单元格中有符号“+”或“-”。 定义一种取反操作