cc动态规划与递推教程.ppt

计 算 机 常 用 算 法 安吉实验初中 陈国锋 7、动态规划 1、穷举法（枚举法） 2、递归法 3、回溯法 4、模拟法 5、分治法 6、贪心法 枚举法穷举法 枚举法（通常也称为穷举法）是指在一个有穷的可能的解 的集合中，枚举出集合中的每一个元素，用题目给定的约束条 件去判断其是否符合条件，若满足条件，则该元素即为整个问 题的解；否则就不是问题的解。枚举的思想往往是最容易想到 的一种解题策略，枚举法从本质上说是一种搜索的算法，但适 用枚举法解题必须满足下列条件： 1）可预先确定解元素的个数n,且问题的规模不是特别大； 2）对于每个解变量A1，A2，。An的可能值必须为 一个连续的值域。 枚举法的算法流程：设ai1为解变量Ai的最小值；aik 为解变量的最大值；其中1 i n. A1 a11,a12,a1K A2 a21,A22,A2K Ai ai1,Ai2,AiK An an1,An2,AnK 我们称解变量为枚举变量。例如某问题的枚举变量有 三个： A1， A2， A3。 A11，2， A22，3，4， A3 5，6，7 则问题的可能解为（ A1 ，A2， A3 ） （1，2，5），（1，2，6），（1，2，7），（1，3，5）， （1，3，6），（1，3，7），（1，4，5），（1，4，6）， （1，4，7），（2，2，5），（2，2，6），（2，2，7）， （2，3，5），（2，3，6），（2，3，7），（2，4，5）， （2，4，6），（2，4，7） 在上述18个可能解的集合中，满足问题给定的检验条件的解元素 即为问题的解。 枚举法的优化方法： 1）减少枚举的变量，在使用枚举法之前，先考虑一下解元素之 间的关联，将一些非枚举不可的解元素列为枚举变量，其他元 素通过计算得出解元素的可能值。 例1、巧妙填数。 将19这9个数字填入到9个空格中。每一横行的三个数字 组成一个三位数。如果要使第二行的三个三位数是第一行 的2倍，第三行的三位数是第一行的三倍，应怎样填数。如 图 192 384 576 2）减少枚举变量的值域 3）分解约束条件，将拆分的约束条件嵌套在相应的循环体间。 本题目有9个格子，要求填数，如果不考虑问题给出的条件， 共有9！=362880种方案，在这些方案中符合条件的即为解。因 此可以用枚举法。 但仔细分析问题，显然第一行的数不会超过400，实际上只要确 定第一行的数就可以根据条件算出其他两行的数了。这样仅需 枚举400次。 例2、有四个学生，上地理课时提出我国四大淡水湖的排序如下 ： 甲：洞庭湖最大，洪泽湖最小，鄱阳湖第三； 乙：洪泽湖最大，洞庭湖最小，鄱阳湖第二，太湖第三； 丙：洪泽湖最小，洞庭湖第三； 丁：鄱阳湖最大，太湖最小，洪泽湖第二，洞庭湖第三；对于 各个湖泊应处的地位，每个人只说对了一个。根据以上情况， 编程序判断各个湖泊应处的地位。 算法分析：本题是一个逻辑判断题，一般的逻辑判断题都采 用枚举法进行解决。四个湖的大小分别可以有4！=24种排列可 能，因为24比较小，因此我们对每种情况进行枚举，然后根据 给定的条件判断哪些符合问题的要求。 源程序 例3、最佳游览路线。 某旅游区的街道成网格状。其中东西向的街道都是旅游街，南 北向的街道都是林阴道。由于游客众多，旅游街被规定为单行 道，游客在旅游街上只能从西向东走，在林阴道上则既可从南 向北走，也可以从北向南走。 阿龙想到这个旅游街游玩，他的好友阿福给了他一些建议，用 分值表示所有旅游街相邻两个路口之见的街道值得游览的程度 ，分值是从-100到100的整数，所有林阴道不打分。所有分值不 可能全是负分。如图： -50-4736-30-23 17-19-34-13-8 -42-3-4334-45 北 南 东西 输入数据：输入文件是input.txt.文件的第一行是两个整数m和n, 之间用一个空格隔开，m表示有多少条旅游街（1m100 ） ，n 表示有多少条林阴道（1n20001 ）。接下来的m行依次 给出了由北向南每条旅游街的分值信息。每行有n-1个整数，依 次表示了自西向东旅游街每一小段的分值。同一行相邻两个数 之间用一个空格隔开。 输出数据：输出文件是output.txt。文件只有一行，是一个整数 ，表示你的程序找到的最佳游览线路的总分值。 Input.txtOutput.txt 3 6 -50 47 36 30 23 17 19 34 13 8 -42 3 43 34 -45 84 Lij为第I条旅游街上自西向东第j段的分值（1im,1jn-1 ）。例 如样例中L12=17，L23=-34，L34=34。 我们将网格状的旅游区街道以林阴道为界分为n-1个段，每一段由 m条旅游街的对应成段，即第j段成为L1j，L2j，。Lmj（ 1jn-1 ）。由于浏览方向规定横向自西向东，纵向即可沿林阴道 由南向北，也可由北向南，而横行的街段有分值，纵行无分值， 因此最佳游览路现必须具备如下三个特证： 1）来自若干个连续的段，每一个段中取一个分值； 2）每一个分值是所在段中最大的； 3）起点段和终点段任意，但途经段的分值和最大。 设Li为第i个段中的分值最大的段。即Li=maxL1i，L2i，。， Lmi（1in-1 ）。例如对于样例数据： L1=max（-50，17，-42）=17； L2=max（-47，-19，-3）=-3； L3=max（36，-34，-43）=36； L4=max（-30，-13，34）=34； L5=max（-23，-8，-45）=-8； 我们把段设为顶点，所在段的最大分值设为顶点的权，各顶点按 自西向东的顺序相连，组成一条游览路线。显然，如果确定西端 为起点，东端为终点，则这条游览路线的总分值最大。 问题是某些段的最大分值可能是负值，而最优游览路线的起点和终 点任意，在这种情况下，上述游览路线就不是最佳了。因此，我们 只能枚举这条游览路线的所有可能的子路线，从中找出一条子路线 ii+1j(1 ibest then best:=sum; end; 显然，n在120001之间，时间复杂 度比较高。于是，我们必须对这个 算法进行优化。仍然从顶点1开始枚 举最优路线。若当前子路线延伸至 顶点时我们发现总分值sum 0,则应 放弃当前的子路线。因为无论Li+1为 何值，当前子路线延伸至顶点i+1后 的总分值不会大于Li+1 。因此应该 从顶点i+1开始重新考虑新的子路线 。 优化后的算法： best:=0;sum:=0; for i:=1 to n-1 do begin sum:=sum+Li; If sumbest then best:=sum; if sum0; 1, n=0。 program factorial; var n:integer; t:longint; function fac(n:integer):longint; begin if n=0 then fac:=1 else fac:=n*fac(n-1) end; Begin write(n=);readln(n); t:=fac(n); writeln(n!=,t); End. 例2、斐波那契数列0，1，1，2，3，5，8，13，21，34，55， ,从第三项开始，每一项是前两项的和，其递归定义式为： F（n）= 0, n=0; 1, n=1; F（n-1）+f（n-2）, n 2 。 求此数列第n项。 参考程序： var n:integer; function fib(n:integer):integer; begin if n=0 then fib=0 else if n=1 then fib:=1 else fib:=fib(n-2)+fib(n-1); end; begin writeln(input n=); readln(n); if n3。 离散事件的递归 例1、简单的背包问题。设有一个背包，可以防如入的重量为s 。现有n件物品，重量分别为t1,t2,t3,ti,tn,ti(1 i n),均为正 整数。从n件物品中挑选若干件，使得放入背包的重量之和正 好为s. 算法分析：用snap(s,n)代表这一问题。 1）先取最后一个物品tn放入背包中，若tn =s,正好放入包中 ，问题解决，输出结果（n,tn） 2)若tn 1） ，那么问题可以转化为从剩下的n-1件物品中选取若干件， 使得它们的重量和等于包里剩下的可放入重量(s- tn) ,即 snap(s- tn,n-1);而选中的tn还要看后续的问题snap(s-tn,n-1)是 否有解，无解的话说明先取的tn不合适，就要放弃tn,在剩 余物品中重新开始挑选，即有snap(s,n) snap(s,n-1)。 3）若tns，则不能放入包中，还得继续挑选；若还剩物品 （即n1），那么问题转化为从剩余n-1件物品中选取若干 个，使得她们的重量和等于s，即snap(s,n) snap(s,n-1)。 在2）、3）中就出现了递归定义，而1）是有解时递归结 束的条件；如果无解时，只有当2）、3）中所剩的物品不 够的话问题就不能继续执行，这也是递归结束的条件。 回溯法 回溯是重要的算法之一，有一些问题，要求找到一组解，或 要求找到一个满足某些限制的最优解。对于解决这样的问题， 可以通过使用彻底的搜索方法来解决。然而，彻底搜索的运算 量很大，有时大到计算机承受不了的程度。彻底的搜索，要进 行大量的比较，大量的舍弃，以大量的运算，大量的时间为代 价。因此，用穷举法解某些实际问题是不现实的，回溯算法为 我们提供了一个好方法，使用回溯法可以大大减少实际的搜索 。例如，迷宫问题，八皇后问题，骑士周游世界问题。 算法思想： 通过对问题的分析，找出一个解决问题的线索，然后沿着这个 线索往前试探，若试探成功，就得到解，若试探失败，就逐步 往回退，换别的路线再往前试探。实际上是广度与深度搜索结 合的搜索，深度搜索过程中碰到条件不满足，则退回上一层， 在每一层上也进行全面的搜索。 关键：找到回溯的条件。 求解八皇后问题： 在n*n个方块排成n行n列的棋盘上，如果两个皇后位于同一行、 同一列或同一对角线上，则称它们互相攻击。现在要求找出使 棋盘上n个皇后互不攻击布局。 列号：（8，2，4，1，7，5，3，6） 分析： 为了找出互不攻击的布局，需要对 n*n个方案进行检查，将有攻击的布 局剔除掉。这是一种例举法。但这种 方法对于较大的n，其工作量会急剧 的增大，而逐一例举是没有必要的。 算法：由于在第一行上的皇后在第一列，则第二行上的皇后就不可 能在第一列。首先将每一行上安置一个皇后，并假设第i个皇后在 第i行上，用一个一维数组queen1n用于记录安放皇后的过程中随 时记录第i行上的皇后所在的列号。由此可知，在这种情况下，实 际上已经剔除了两个皇后在同一行的可能性。因此，在安置每一行 上的皇后时，只需考虑每两个皇后不能在同一列或同一对角线上的 可能性。 从第一行（即i=1）开始布局。 设前i-1行上的皇后已布局好，即它们互不攻击。现考虑安排 第i行上皇后位置，使之与前i-1行上的皇后也互不攻击。为了实现 这一点，可以从第i行皇后的当前位置开始向右搜索。 引进集合a,b,c分别表示各列、各条右对角线和各条左对角线 上是否放置了皇后。在同一右对角线上，i-j是常量。在同一左对角 线上，i+j是常量。第i行第j列上放皇后在第i-j条右对角线和第i+j条 左对角线上。能放皇后时为真，不能放皇后时为假。数组queen存 放各行皇后所在的列号。 骑士周游问题 骑士周游问题。给定一个n*n的方阵，共有n2个区域，有一个国际象棋的马置于一 个区域上，要求找到一条路径，使马按国际象棋的规则，从开始区域出发，不重复地 把n2个区域都恰好经过一次。 分析1：由于马按“日”字走，马从本区域起一步最多能达到八个区域。设马所在区 域坐标为（i,j）,则下一步能达到的8个位置的坐标如下： (i-2,j-1) （3） (i-2,j+1) （2） (i-1,j-2) （4） (i-1,j+2) （1） （i,j） (j+1,j-2) （5） (i+1,j+2) （8） (i+2,j-1) （6） (i+2,j-1) （7） 分析2： 马从初始位置（i,j）开始，按8个方向（从（1）（8） 走，如下一位置在方阵中而且未到过，则马跳到该位置，继续 走；如果8个方向的位置都不能落脚，则退一步，上一步为当前 步，再按下一个方向继续试跳。 算法： Procedure 过程名； Begin 准备初值； repeat while 选择范围不超过边界且工作未完成 do begin 分析条件；保证不满足条件不进行 if 成功 then 进栈；由第选择开始进入下一层次（往下走） else 本层更换选择；横向走 end ; if 工作未完成 then 退栈；原来的上一层更换为下一选择，回溯，上层横向走 until 全部工作完成； 输出； end ; 随机数的介绍 在自然界和日常生活中,许多现象具有不确定的性质,有些问题 甚至很难建立数学模型,或者很难用计算机建立递推,递归,枚举,回溯 法等算法.在这种情况下,一般采用模拟策略.在对实际问题中的随机 现象进行数学模拟时,利用计算机产生的随机数是必不可少的,由于 用计算机产生的随机数总是受字长的限制,其随机的意义要比实际问 题中真实的随机变量稍差,因此,通常将计算机产生的随机数称为伪 随机数. TURBO.PASCAL的系统中有两个产生伪随机数的单元: Randomize过程伪随机数发生器初始化, Random(range)函数产生一个范围在0 x0 do begin if k=b then begin x:=random(2);b:=1+x; if n-b0 then 若剩余棋子数为3的整数倍,则调整每次 抓的棋数 else x:=random(2);a:=1+x; if n-a=2*k+1） ，甲每次取a颗, （N,k,a均为随机数），乙怎样取赢的可能性最大 ？设甲为计算机产生的随机数，乙为由你编的计算机程序。 猜数游戏： 人和计算机做猜数游戏。人默想一个四位数，由计算机来猜。 计算机将所猜的数显示到屏幕上，并问两个问题： （1）有几个数字猜对了？（2）猜对的数字中有几个位置也对？ 人通过键盘来回答这两个问题。计算机一次又一次地猜，直到猜 对为止。比如我们默想的一个数是5122，假定计算机第一次猜1166 ，然后问你： （1）有几个数字猜对了？1（2）猜对的数字中有几个位置也对？1 假定计算机第二次猜1287 （1）有几个数字猜对了？2（2）猜对的数字中有几个位置也对？0 假定计算机第三次猜5122 （1）有几个数字猜对了？4（2）猜对的数字中有几个位置也对？4 计算机显示最后猜中的数，并报告共猜了几次？ 问题1：编程实现这样一个猜数的游戏程序。屏幕显示格式为 ： 第二行显示计算机所猜的四位数。 第三行提问猜对的数字个数，用“Number:” 第四行提问位置对的数字个数，用“Position:” 第五行显示当前已猜的步数，用“Step xx”. 注：其中末尾数字由键盘输入。最后给出结束信息，其他由编 程者自定。 问题2 ：仍是这样一个游戏，但要求计算机既是猜数者，又要模 拟默想这个数的人（要猜的数由键盘输入）。屏幕显示格式为 ： 第一行显示人所默想的数，用“xxxx”. 第二行至第五行同问题1，只不过末尾数字不再由键盘输入，而 是计算机判断后自动显示。 问题3： 从文本文件guess.dat中读入20个四位数，一个接一个让计 算机猜，统计猜中所需的总步数。 算法分析：1、计算机随机产生一个猜数 设m-当前的猜数集合。 var m:array19000 of integer; t:integer; m的长度； 初始时m=1000，1001，9999 t=9000 每一次猜数时，从m1mt中随机取出一个四位数，该数即为计算机的一个猜 数。若m集合为空（t=0）时还未猜中，则游戏以失败告终。计算机产生猜数的过 程如下： function get_next :integer; begin if t4，则计算机将now与m 集合中的每一个四位数一一比较，将m中与now的相同数字个 数为t1且相同数字中位置对应的数字个数为t2的所有四位数 mi(1t1) or (test2(key,now)t; 形成m的一个子集，m1mt(1t1) or (test2(key,now)t; End;delete 算法流程：问题（1）的算法。 for I:=1 to 9000 do mi:=I+999; t:=9000; randomize; Repeat n:=get_next; if n=-1 then begin 打印猜数失败西信息；halt; end;then Put(n,now) 打印计算机产生的猜数now； 输入猜对的数字个数t1和猜对数字中位置也对的数字个数t2; Delete(now); Until(t1=4) and (t2=4); 问题2的算法。 设 step猜中一个数的不数。 step:=0; m集合初始化； 读默想数key； Repeat n:=get_next;put(n,now); t1:=test1(key,now);t2:=test2(key,now); 输出t1和t2; Step:=step+1; Delete(now); Until(t1=4) and (t2=4); 问题3的算法：设total猜中二十个数的总步数 Total:=0; For k:=0 to 19 do begin 执行问题2的算法； Total:total+step; End;for 输出猜中20个数所需的总步数total; 题目1: 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系 统。但是这种拦截系统有一个缺陷：虽然它的第一发炮弹 能够到达任意的高度，但是以后每一发炮弹都不能高于前 一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该 系统还在试用阶段。所以一套系统有可能不能拦截所有的 导弹。 输入导弹依次飞来的高度（雷达给出的高度不大于 30000的正整数）。计算要拦截所有的 导弹最少需配备多 少套这种导弹拦截系统。 输入： 导弹数n和n颗导弹依次飞来的高度（1导弹的的高度)； Lp:=导弹的的高度。这样，可以使得被一套系统拦截的导弹数尽 可能增多。 4.依次类推，直至分析了n枚导弹的高度为止。 此时得出的k便为应配备的最少系统数。 K:=1;L1:=导弹1的高度； Fo