1.枚举策略.ppt

分析 这道题的关键点是“如何能够快速正确实现出来” ，事实上这道题 对编码能力的要求要大于对算法本身的要求。由于这道题的数据范 围并不是很大，但需要进行“字符串处理”这种比较麻烦的工作，因 此在比赛时就可以采用效率低一些的枚举算法来换取编码上的简单 推荐的算法分为两步： 1．预处理每个人的每一句话，并把它们分类处理； 2．枚举罪犯和当前星期几，找出所有可能发生的情况。 下面我们来逐步细化一下每一步的算法，对于第一步，我们希望的 是把一些杂乱的不好处理的“字符串信息”转化为相对比较好处理的 信息。为此，我们可以通过把“信息”进行分类的方法使得对于每一 类信息，更加方便的处理（即我们可以用一个或者几个变量来表 示），由题目描述可以发现语句可分为三类： 分析 1．指明i是否是罪犯的语句； 2．指明今天是星期d的语句； 3．没有意义的语句(不符合格式要求)。 我们必须要说明的是任何不符合格式要求的语句都将被划分到第三类中去，这样在处理每个语句的时候就必须要考虑该语句是否符合格式要求，通过以上的处理，我们对于每一个语句用几个变量就可以表示了。 对于第二步的细化，我们在枚举完罪犯和当前星期几之后，就可以比较方便的判断每一句话的真伪了，这样我们再根据每个人所说的话把人进行分类。 1．没说任何一句有意义的话； 2．只说真话； 3．只说假话； 4．既说真话也说假话。 分析 需要注意的是，对于第一类人我们既可以把他当成说真话 的，也可以把他当成说假话的，而如果第四类人存在的话， 那么从他本身就可以推出矛盾了。最后，如果对于罪犯i存 在一个d使得当前情况是可能的，我们就说i就是可能的罪 犯。 [时间效率] O(MP|Day|) （其中Day={Sunday，Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}） 优化 我们可以发现在对罪犯和当前星期几进行“双重枚举”时，进行了很多 重复的操作，于是我们想到，能不能不枚举是当前星期几？这样我们把 这类语句与判断罪犯的语句分离，可以先由判断罪犯的语句中确定一部 分人肯定说真话，一部分人肯定说假话，剩下的一部分人就要根据他所 说的当前星期几的语句来判断了，首先我们假设所有人判断星期的语句 不自相矛盾，这样每个人将在判断这类问题里面至多有一个答案，我们 便可以统计判断当前是星期d的总人数，于是改进后的算法对于每一个可 能的罪犯，先用O(p)的时间处理所有的话，再用O(|Day|)的时间枚举星 期几。这样，改进后算法的复杂度就是O(m(p+|Day|))。那么我们可不可 以再进一步，把算法优化到线性？这里面可以比较明确地告诉大家，是 可以做到的，具体的算法类似于上面的按照语句的种类分离语句，只是 分离得更细，处理得更复杂，在这里就不做赘述，留给大家思考。 浏阳市集里中学 徐晨辉 简 单 枚 举 算 法 简单枚举法 枚举法 所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。一般思路： 对命题建立正确的数学模型； 根据命题确定的数学模型中各变量的变化范围（即可能解的范围）； 利用循环语句、条件判断语句逐步求解或证明； 枚举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。 虽然枚举法本质上属于有哪些信誉好的足球投注网站策略，但是它与回溯法有所不同。因为适用枚 举法求解的问题必须满足两个条件：?????? ⑴可预先确定每个状态的元素个数n； ⑵状态元素a1，a2，…，an的可能值为一个连续的值域。 设 ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)， 即a11≤a1≤a1k，a21≤a2≤a2k， ai1≤ai≤aik，……，an1≤an≤ank for a1←a11 to a1k do fo a2←a21 to a2k do …………………… for ai←ai1 to aik do …………………… for an←an1 to ank do if 状态(a1，…，ai，…，an)满足检验条件 then 输出问题的解； 枚举法的优点： ⑴由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解； ⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。 枚举法的缺点： 枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。 枚举法优缺点 示例 求满足表达式A+B=C的所有整数解，其中A，B，