文档介绍：该【枚举与搜索教案公开课一等奖优质课大赛微课获奖课件 】是由【胜利的喜悦】上传分享，文档一共【66】页，该文档可以免费在线阅读，需要了解更多关于【枚举与搜索教案公开课一等奖优质课大赛微课获奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。枚举与搜索讲稿
长沙市雅礼中学 朱全民
第1页
第1页
相关搜索NOIP试题
神经网络()---宽搜
侦探推理()---枚举与优化
传染病控制()---深搜与优化
虫食算()---深搜与优化
火柴棒等式()---简朴枚举
双栈排序 ()---二分图搜索
靶形数独()---深搜与优化
第2页
第2页
简朴枚举法
所谓枚举，即对也许解集合一一列举。
解题思绪为：
首先拟定也许解集合
抽象出解包括参数，拟定每个参数数据范围
对解每个参数数据范围采用循环语句一一枚举
对每次枚举，依据题意给定条件鉴定是否解，是否是最优解。
第3页
第3页
火柴棒等式
给你n根火柴棍，你能够拼出多少个形如“A+B=C”等式？等式中A、B、C是用火柴棍拼出整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9拼法如图所表示：
注意：
1. 加号与等号各自需要两根火柴棍
2. 假如A≠B，则A+B=C与B+A=C视为不同等式（A、B、C>=0）
3. n根火柴棍必须全部用上
第4页
第4页
分析
0~9数字所用火柴数：6,2,5,5,4,5,6,3,7,6
对于N<=24，去掉+，=，事实上数字只有20根火柴。
首先考虑解集合，由于最多为20根火柴构成数字：
不也许为10个1；
不也许8个1，1个4；
不也许为7个1，2个7或1个0；
…..
C不会超出1000
第5页
第5页
枚举答案
设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 输出；
第6页
第6页
侦探推理
证词中出现其它话，都不列入逻辑推理内容。
明明所知道是，他同窗中有N个人始终说假话，其余人始终说真话。
现在，明明需要你帮助他从他同窗话中推断出谁是真正凶手，请记住，凶手只有一个！
要求：
判断谁是罪犯？
第7页
第7页
分析
这道题要点是“如何能够快速正确实现出来” ，事实上这道题对编码能力要求要不小于对算法本身要求。由于这道题数据范围并不是很大，但需要进行“字符串处理”这种比较麻烦工作，因此在比赛时就能够采用效率低一些枚举算法来换取编码上简朴。
推荐算法分为两步：
1．预处理每个人每一句话，并把它们分类处理；
2．枚举罪犯和当前星期几，找出所有也许发生情况。
下面我们来逐步细化一下每一步算法，对于第一步，我们希望是把一些杂乱不好处理“字符串信息”转化为相对比较好处理信息。为此，我们能够通过把“信息”进行分类办法使得对于每一类信息，愈加以便处理（即我们能够用一个或者几种变量来表示），由题目描述能够发觉语句可分为三类：
第8页
第8页
分析
1．指明i是否是罪犯语句；
2．指明今天是星期d语句；
3．没故意义语句(不符合格式要求)。
我们必须要阐明是任何不符合格式要求语句都将被划分到第三类中去，这样在处理每个语句时候就必须要考虑该语句是否符合格式要求，通过以上处理，我们对于每一个语句用几种变量就能够表示了。
对于第二步细化，我们在枚举完罪犯和当前星期几之后，就能够比较以便判断每一句话真伪了，这样我们再依据每个人所说话把人进行分类。
1．没说任何一句故意义话；
2．只说真话；
3．只说假话；
4．既说真话也说假话。
第9页
第9页
分析
需要注意是，对于第一类人我们既能够把他当成说真话，也能够把他当成说假话，而假如第四类人存在话，那么从他本身就能够推出矛盾了。
最后，假如对于罪犯i存在一个d使得当前情况是也许，我们就说i就是也许罪犯。
[时间效率]
O(MP|Day|) （其中Day={Sunday，Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}）
第10页
第10页