从一个基本方法谈起.ppt

《从一个基本方法谈起.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、从一个基本方法谈起北京大学姚金宇为什么讲这个问题对搜索和动态规划算法的一种引入方式对解题方法的深入认识“电脑”和“人脑”的特点和区别具体应用“回到起点”和“变换角度”不断优化先看一个问题——称硬币Sally有12枚硬币，其中包括11枚真币和1枚假币。假币的特点是其重量与其他硬币不同——可能更轻也可能更重，麻烦的是Sally并不知道假币比真币轻还是重。她向朋友借来了一架天平，每次可以在天平两边同时放上相同数量的硬币，天平就会显示孰轻孰重。如果天平平衡，当然就表示天平上的所有硬币都是真币。可是Sally的朋友很苛刻地希望她在三次称量就可以得出结果。*题外思考：这可能吗？*关于称硬币问题的一般

2、解法参看2003年何林的国家集训队论文。例1称硬币问题聪明的Sally很快得出了一套方案。你的任务是根据每一次称量的结果，求出哪一枚硬币是假币，以及它比真币轻还是重。数据保证可以得到唯一结果。例如：输入ABCDEFGHevenABCIEFJKupABIJEFGHeven输出Kiscounterfeitcoinanditislight.第一种思路考虑每一次称量的结果：Even参与称量的所有硬币都是真币Up:没有参与称量的所有硬币都是真币天平左边的硬币标记为“轻”（因为如果它是假币，只可能比真币轻）天平右边的硬币标记为“重”Down没有参与称量的所有硬币都是真币天平左边的硬币标记为“重”天平

3、右边的硬币标记为“轻”如果最后某个硬币同时标记为“轻”和“重”，则它是真币。根据最终标记可以出结论第二种思路前提：数据保证有唯一解算法：逐一试探法枚举假币的编号以及它比真币轻还是重逐一的判断在这种情况下每次称量是否满足能满足所有的称量结果的枚举即是答案。枚举法方法：逐一判断所有可能的方案是否为问题的解前提：计算机高速处理数据的能力对于较复杂的问题来说，枚举往往需要逆向思考和与其它方法的结合。关于枚举的对象：例2超长数字串数字串S：12345678910111213141516171819202122……任意给一个有限长度的数字串S1，它在S中出现了无穷多次。求它在S中最先出现的位置。例2

4、分析第一种解法枚举S1出现的位置，直至能与之完全匹配为止第二种解法：枚举S1的切片，以之为一个整数，向前和向后扩展成为一个串，再判断与S1是否匹配8192192018181920对于答案的枚举对于不方便直接求解的问题，我们往往可以考虑枚举答案，然后判断可行性。需要借助于二分法、三分法时间复杂度与答案的规模相关例3电缆Wonderland居民决定举行一届地区性的程序设计大赛。共有n个参赛者，对于每个参赛者，组委会会用一根长度一定的网线将他的计算机与中心连接，使得他们到网络中心的距离相等。现在有m根长度不等的网线（长度精确到厘米），每根长度分别是L1,L2,……,Lm。现在可以将他们以厘米的

5、精度切割。请你确定为了得到n根等长网线，每根网线的最大可能长度。数据范围：m<=1000，n,max{L}<=106假设每根网线的长度为x，则一共可以得到可以看出，f(x)是单调递减的函数。我们的目的就是找到最大的x使得f(x)>=n例3电缆例3电缆对于这个问题，我们可以采用二分法。主算法框架如下：Funccalc(s,t):Longint;ifs=tthenreturns//二分边界elsebeginx[(s+t)/2]iff(x)>=nthenreturncalc(x,t)elsereturncalc(s,x-1);endifEndFunc例3电缆由于单根网线长度的范围是[1，ma

6、x{L}]，所以calc(1,max{L})的值即为所求。每次计算f(x)的复杂度为O(m)所以总的时间复杂度是O(mlog2(max{L}))例4JackAndJillJack和Jill互相都不喜欢对方，他们请你帮他们安排上学的路线，使得在途中任何时刻，他们之间的最短距离最长。给你的是一个n*n的格子地图，从一个格子移动到相邻的格子花费1个单位时间。所谓的途中任何时刻的距离，是指每次移动之后他们俩所在格子的中心点的距离。Jack和Jill同时从各自家中出发，前往各自学校，而且中途不能休息。地图上有一些不可到达点。当然，Jack的家和学校对于Jill来说是不可到达点，Jill的家和学校对

7、Jack来说也是不可到达的.n<=30，结果保留两位小数。例4JackAndJill图例‘H’——Jack的家‘S’——Jack的学校‘h’——Jill的家‘s’——Jill的学校‘*’——公共的不可到达点‘.’——空地N=10ans=6.71.............H.......**...s....**........**........**........**........**..........S..h..*......