B班day1上午枚举与搜索教案朱全明

noip 学习资料

枚举与搜索讲稿长沙市雅礼中学 朱全民

noip 学习资料

有关搜索的NOIP试题 有关搜索的 试题 神经网络 神经网络(2003)---宽搜 宽搜 神经网络 侦探推理 侦探推理(2003)---枚举与优化 侦探推理 枚举与优化 传染病控制 传染病控制(2003)---深搜与优化 传染病控制 深搜与优化 虫食算 虫食算(2004)---深搜与优化 虫食算 深搜与优化 火柴棒等式 火柴棒等式(2008)---简单枚举 火柴棒等式 简单枚举 双栈排序 (2008)---二分图的搜索 双栈排序 二分图的搜索 靶形数独 靶形数独(2009)---深搜与优化 靶形数独 深搜与优化

noip 学习资料

简单枚举法所谓枚举，即对可能的解集合一一列举。 所谓枚举，即对可能的解集合一一列举。 解题思路为： 解题思路为： 首先确定可能的解集合 抽象出解包含的参数，确定每个参数的数 抽象出解包含的参数， 据范围 对解的每个参数的数据范围采用循环语句 一一枚举 对每次枚举，根据题意给定的条件判定是 对每次枚举， 否解，是否是最优解。 否解，是否是最优解。

noip 学习资料

火柴棒等式 给你 根火柴棍，你可以拼出多少个形如“A+B=C”的等式？ 给你n根火柴棍，你可以拼出多少个形如“ 的等式？ 根火柴棍 的等式 等式中的A、 、 是用火柴棍拼出的整数 若该数非零， 是用火柴棍拼出的整数( 等式中的 、B、C是用火柴棍拼出的整数(若该数非零， 则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示 )。用火柴棍拼数字 的拼法如图所示： 则最高位不能是 )。用火柴棍拼数字 的拼法如图所示：

注意： 注意： 1. 加号与等号各自需要两根火柴棍 2. 如果 如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、 视为不同的等式( 、 、 , 与 视为不同的等式 C>=0) ) 3. n根火柴棍必须全部用上 根火柴棍必须全部用上

noip 学习资料

分析 1. 2. 3. 4. 5. 0~9的数字所用的火柴数：6,2,5,5,4,5,6,3,7,6 的数字所用的火柴数： 的数字所用的火柴数 对于N<=24,去掉 ，=,实际上数字只有 根火 对于 ，去掉+, ,实际上数字只有20根火 柴。 首先考虑解集合，因为最多为20根火柴组成数字 根火柴组成数字： 首先考虑解集合，因为最多为 根火柴组成数字： 不可能为10个1; 不可能为10个1; 不可能8个 ， 个 ； 不可能 个1,1个4; 不可能为7个 ， 个 或 个 ； 不可能为 个1,2个7或1个0; ….. C不会超过 不会超过1000 不会超过

noip 学习资料

枚举答案 设F(I)表示数为 时的火柴棍数 表示数为I时的火柴棍数 表示数为 FOR A=0 TO 1000 DO IF F(A)<N-4 THEN FOR B=1000-A DO IF F(A)+F(B)+F(A+B)=N-4 THEN 输出； 输出；

noip 学习资料

侦探推理

证词中出现的其他话，都不列入逻辑推理的内容。 证词中出现的其他话，都不列入逻辑推

理的内容。 明明所知道的是，他的同学中有N个人始终说假话， 明明所知道的是，他的同学中有N个人始终说假话，其余的 人始终说真话。 人始终说真话。 现在， 现在 ， 明明需要你帮助他从他同学的话中推断出谁是真正 的凶手，请记住，凶手只有一个！ 的凶手，请记住，凶手只有一个！ 要求： 要求： 判断谁是罪犯？ 判断谁是罪犯？

noip 学习资料

分析 这道题的关键点是“如何能够快速正确实现出来” ,事 这道题的关键点是“如何能够快速正确实现出来” 实上这道题对编码能力的要求要大于对算法本身的要求。 实上这道题对编码能力的要求要大于对算法本身的要求。 由于这道题的数据范围并不是很大，但需要进行“ 由于这道题的数据范围并不是很大，但需要进行“字符串 处理”这种比较麻烦的工作， 处理”这种比较麻烦的工作，因此在比赛时就可以采用效 率低一些的枚举算法来换取编码上的简单。 率低一些的枚举算法来换取编码上的简单。 推荐的算法分为两步： 推荐的算法分为两步：

1.预处理每个人的每一句话，并把它们分类处理； 预处理每个人的每一句话，并把它们分类处理； 2.枚举罪犯和当前星期几，找出所有可能发生的情况。 枚举罪犯和当前星期几，找出所有可能发生的情况。下面我们来逐步细化一下每一步的算法，对于第一步， 下面我们来逐步细化一下每一步的算法，对于第一步，我们 希望的是把一些杂乱的不好处理的“字符串信息” 希望的是把一些杂乱的不好处理的“字符串信息”转化为 相对比较好处理的信息。为此，我们可以通过把“信息” 相对比较好处理的信息。为此，我们可以通过把“信息” 进行分类的方法使得对于每一类信息， 进行分类的方法使得对于每一类信息，更加方便的处理 即我们可以用一个或者几个变量来表示), ),由题目描述 (即我们可以用一个或者几个变量来表示),由题目描述 可以发现语句可分为三类： 可以发现语句可分为三类：

noip 学习资料

分析1.指明i是否是罪犯的语句； 指明i是否是罪犯的语句； 2.指明今天是星期d的语句； 指明今天是星期d的语句； 没有意义的语句(不符合格式要求) 3.没有意义的语句(不符合格式要求)。 我们必须要说明的是任何不符合格式要求的语句都将被划 分到第三类中去， 分到第三类中去，这样在处理每个语句的时候就必须要考 虑该语句是否符合格式要求，通过以上的处理， 虑 …… 此处隐藏：5969字，全部文档内容请下载后查看。喜欢就下载吧 ……