#NOI导刊-基础算法课件.ppt

1、第一部分枚举n枚举：是对一个问题找出所有的可行状态，然后从中找出最优的状态。n枚举的不足：当枚举的状态很多时，所用的时间会非常大，效率比较低。n1、枚举对象的确定n2、枚举方法的选取n3、局部枚举例题1 图像分析n见文档例题2 B_stationn在离著名的国家Berland不远的地方，有一个水下工作站。这个工作站有N层。已知：是第i层装有Wi的水，最多可以容纳Li的水，恐怖分子炸毁第i层的代价是Pi。第i层一旦被炸毁，该层所有的水都将倾泻到第i+1层。如果某一层的水量超过了它的容量(即Li)，那么该层就将自动被毁坏，所有的水也会倾泻到下一层。nPivland的恐怖分子想要用最少的钱毁掉第N层

2、，现在他雇佣你来计算，需要炸毁哪些层。n 输入输入:第一行有一个自然数第一行有一个自然数N(1=n=15000)。接下来。接下来的的N行，每行行，每行3个整数个整数Wi, Li, Pi(0=Wi,Li,Pi=15000)。输出输出:输出需要炸毁的层的编号。输出需要炸毁的层的编号。样例样例Input 样例样例output3 11000 1000 1 20 1000 2 2 10 100 分析n令Si=W1+W2+Wi（特别的S0=0）。n不妨设恐怖分子炸毁的第高层是第p层（第一层是最高层，第N层是最底层）。n因为恐怖分子的目标是毁灭第N层，所以水必须从第p层一直泻下去。如果存在一个i，满足Wp+

3、Wp+1+Wi-1+Wip Si-Sp-1p Qip Qip-1 Qi=Sp-2n因为Sp-2p-1 QiSp-2。n添加p-1。 针对这两种操作，我们可以使用大根堆(Heap)。从大到小枚举p，对于每一个p，执行：Step1. 如果堆的根i满足Qi Sp-2，那么删除根；否则转Step3。Step2. 转Step1。Step3. 添加p-1。每层至多进堆一次、出堆一次，所以总的时间复杂度是O(nlogn)。对于n=15000的范围完全能够胜任了。 例题3：图形周长n给定N（=5000）个矩形，每个矩形均垂直或水平放置，它们可以重叠。求最终被覆盖部分的周长。例题3分析n见文档例题4 数字游戏n

4、见文档例题5 排列问题n见文档第二部分例题1 kodn给定26个英文字母中的前k(max then max:=j; 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; 递归的概念与

5、基本思想递归的概念与基本思想起始状态就是调用起始状态就是调用findmax(1) ，max为全局为全局变量，同时还减少了一个局部变量的使用。尽管变量，同时还减少了一个局部变量的使用。尽管这只是一个很简单的例子，在本例中不做精简，这只是一个很简单的例子，在本例中不做精简，程序也还是能通过，但它精简的原则对其它使用程序也还是能通过，但它精简的原则对其它使用递归的程序而言却是同样适用的。特别是在递归递归的程序而言却是同样适用的。特别是在递归过程出现堆栈溢出情况时就应该考虑这一问题。过程出现堆栈溢出情况时就应该考虑这一问题。递归的概念与基本思想递归的概念与基本思想n采用递归方法编写的问题解决程序具有结

6、构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。递归的应用递归的应用n解决搜索问题n处理递归定义或解决方法为递归方式的问题n实现分治思想n用于输出动态规划的中间过程递归的应用（搜索树）递归的应用（搜索树）n树结构是由递归定义的。因此，在解决与树有关的问题时，常常可以采用递归的方法。因为搜索产生的节点成树状结构，所以可以用递归方法解决。这类例子很多，如“N后”问题，哈密顿回路，图的可着色性等等。递归的应用递归的应用例题：钢板分割问题。设有一块

7、正方形的钢板，例题：钢板分割问题。设有一块正方形的钢板，现需将它分成现需将它分成n个小正方形。例如，当：个小正方形。例如，当：n=2 不可能有解。不可能有解。 n=3 不可能有解。不可能有解。n=4 可分成可分成4个小正方形钢板。个小正方形钢板。 n=5 不可能有解。不可能有解。n=6 即一个大的加五个小的。即一个大的加五个小的。n=7 即三个较大的加四个小的。即三个较大的加四个小的。n=8 即一个大的加七个小的。即一个大的加七个小的。问题为任给问题为任给n，求出分成，求出分成n个小正方形的方法。个小正方形的方法。 递归的应用递归的应用【分析】经过分析就可以得出：【分析】经过分析就可以得出：（

8、1）按）按n=4的方法将的方法将1个小正方形分成个小正方形分成4个，则个，则增加了增加了3个正方形。个正方形。（2）以）以n=6为基础，由（为基础，由（1）可以得出）可以得出n=9，12，15，。（3）以）以n=7为基础，由（为基础，由（1）可以得出）可以得出n=10，13，16，。（4）以）以n=8为基础，由（为基础，由（1）可以得出）可以得出n=11，14，17，。由此可以得出如下的递归算法：由此可以得出如下的递归算法：递归的应用递归的应用procedure devide(i:integer);Begin if n8 then begin 分解成四小块； 对于其中一块devide(n-3)

9、 end else case n of 6: 按n=6分割； 7: 按n=7分割； 8: 按n=8分割； end;End;递归的应用（实现分治思想）递归的应用（实现分治思想） 不难发现，在各种时间复杂度为nlogn排序方法中，大都采用了递归的形式。因为无论是分治合并排序，还是堆排序、快速排序，都存在有分治的思想。只要分开处理，就可以采用递归。其实进行分治，也是一个建树的过程。递归的应用（例题分析）递归的应用（例题分析）例题例题2：剔除多余括号：剔除多余括号 键盘输入一个含有括号的四则运算表达式键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，可能含有多余的括号，编程整

10、理该表达式，去掉所有多余括号，原表达式中所有变量和运去掉所有多余括号，原表达式中所有变量和运算符相对位置保持不变，并保持原表达式等价算符相对位置保持不变，并保持原表达式等价。分析：分析： 首先考虑人处理这个问题的方法，就是依首先考虑人处理这个问题的方法，就是依靠符号来判断是否可以去括号。括号的前后，靠符号来判断是否可以去括号。括号的前后，以及括号内的符号，都需要考虑。因此，可以以及括号内的符号，都需要考虑。因此，可以按照人的处理方法，从最外层处理起，一层一按照人的处理方法，从最外层处理起，一层一层的去掉括号，这便是分治的思想。而由于每层的去掉括号，这便是分治的思想。而由于每次分治的处理过程基本

11、相同，用递归最为合适次分治的处理过程基本相同，用递归最为合适。递归的应用（例题分析）递归的应用（例题分析） 在递归过程中，对于正在处理的表达式s，如果s本身最外层就是多余括号，则去括号，并处理括号内的表达式（递归调用）；否则，可沿该表达式中的最低级运算符p，将其拆为两个表达式，分别进行处理（递归调用），并获得左右两表达式中的最低级运算符c1,c2，通过与p的比较，确定是否应添加括号。 递归的终止条件为：s是变量。递归的应用（例题分析）递归的应用（例题分析）n例如，处理表达式(a+b)*f)-(i/j),过程如下：n (a+b)*f)-(i/j),-n (a+b)*f),* (i/j),/n n

12、 (a+b)*f),* i/j,/n n (a+b),+ f, i, j, n n a+b,+n a, b, nn最后得出结果：(a+b)*f-i/j。递归的应用（输出动态规划的中间过程）递归的应用（输出动态规划的中间过程） 动态规划对空间要求较高，若要保存中间过程用于输出，则可能要增加一倍的空间需求。此时，如果采用递归输出，就完全不需要浪费这宝贵的空间。例题：最佳航线问题 你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行，从最西的一个城市出发，单方向从西向东经若干城市到达最后一个城市（必须到达最东的城市），然后在单方向从东向西飞回起点（可途径若干城市）。除起点城市外

13、，任何城市只能访问一次。起点城市被访问两次：出发一次，返回一次。除指定的航线外，不允许乘其他航线，也不允许使用其他交通工具。 求解的问题是：给定城市表列及两城市之间的直通航线，请找出一条旅行航线，在满足上述限制条件下，使访问的城市尽可能多。例题分析：最佳航线问题对这一问题，我们采用了动态规划的方法。 假设城市已按从西到东编号，数组disti,j 表示城市i到城市n,再到城市j的所有可行方案中，最多能够访问的城市数目。逆推关系式为：ndistn,n=1;ndisti,j=distj,i;ndisti,j=max(disti,k)+1; (ji,jk=n,且存在航线kj)n 如果要记录中间过程，就必须再开辟一个二维数组，就会导致程序可完成的数据规模降低。而采用递归求出路径后再输出，编程并未增加多少难度，而可处理的数据量却大大增加了。求路径的过程完全按照倒推的方法，利用dist数组得出往返的路线。