第九讲算法实例-枚举算法

《第九讲算法实例-枚举算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息技术备课组“算法实例”教案算法实例——枚举算法课题：算法实例（两课时）教学目的：复习算法的三种结构掌握枚举算法的特征，学会使用枚举算法来解决日常生活中的问题教学重点、难点：枚举算法的引入教学方法：讲授、启发、讨论相结合；练习法教学媒体：多媒体演示教学过程：教学引言：这是今天的课程内容的第二个内容，我们已经学过了算法的三种结构，我们学过了三种结构：顺序结构，选择结构，循环结构，我们在日常生活中可以用这三种算法结构来解决任何实际问题，但是在日常生活中，需要解决的问题多种多样，我们也不可能有一种统一的方法来解决所有的问题，为了解决各种各样的

2、问题，我们必须学习各种各样的算法设计技巧，也就是所谓的算法的实例，今天我们就要学习算法实例当中的一种算法—枚举算法那么请同学们思考两个问题：1、什么是枚举算法？2、枚举算法有什么特点3、引入今天的课题：引入两个生活中的实例：在一串钥匙中找到所有能开启某扇门锁的钥匙。情景设置：教师给学生展示一串钥匙，并说这些钥匙一共有10把，并且每把钥匙都一模一样，我不知道这10把钥匙中有几把能够打开这把锁询问学生：你可以用什么样的方法在最短的时间内找到所有能开启某扇门锁的钥匙呢？方法：把所有的钥匙都去试一遍，直到找到能够开门的那一把钥匙。学生回答：把一把

3、把钥匙去试，学生一边说，教师一边演示，看看第一把钥匙能够打开锁吗，如果不能打开锁的话，就接着试下一把，找到了能够打开门锁的那一把，就把它取下来，再接着找下一把钥匙，那么剩下的钥匙还要不要再找下去？我们用流程图怎么来表示这个算法呢？分析：我们要从第几把钥匙开始找？学生回答：第一把，然后一共要找几次？找10次，那我们是不是要用一个循环结构来解决这个问题，同时要用到计数器i吧，i的初始值应该是几？（1，从第几把钥匙开始找？从第一把开始找）然后要找几次（循环条件是什么？i<=10）我可以给这串钥匙编个号吧，第一把钥匙就是1号，然后第二把钥匙就是二

4、号，那么我就可以用计数器来表示这些钥匙了吧，然后我一把一把钥匙开始试能否打开这把锁，那么我在循环体里做些什么事情呢？是不是要判断一下这把钥匙能够打开这把锁吗，那我在这个循环结构里是不是要嵌套一个选择结构，判断条件应该怎么写？（这把钥匙是这个锁的钥匙吗？）如果不能打开，我就继续尝试下一把钥匙，（教师演示）如果能够开的话，我就把这把钥匙取下来，同时记录这把钥匙的编号，然后再继续找下一把钥匙，直到10把钥匙都找好为止，在黑板上画出流程图，同时请学生转换成伪代码问题：要不要把所有的钥匙都找一遍？找过的钥匙还要不要再找？那么刚才我们讲的这种算法是不

5、是把找出所有能开锁的钥匙这个问题解决了呢？这种算法就是枚举算法，请同学们概括一下什么是枚举算法，枚举算法有什么特点？提问学生：什么是枚举算法？枚举算法有什么特点？信息技术备课组“算法实例”教案今天我们来讲算法中的枚举算法——当问题的所有可能解的个数不太多时，一一列举出该问题所有可能的解（提问学生：像刚才这道找出所有能够开锁的钥匙的题，它的可能的解是什么？是不是所有的10把钥匙都可能把这把锁打开），并在逐一列举的过程中把每个问题的解通过循环结构代入到问题中进行检验，检验每个可能解是否是问题的真正解，如果是问题的真正解，就采纳它，否则抛弃它。

6、不重复，不遗漏，这类似于我们数学中的带入法，当一个问题用正常方法无法求解时，可以把一些数字直接带入题目中进行检验从而求得答案。由此可见：枚举算法的一般结构是：循环结构中嵌套一个分支判断结构，其中循环结构用以实现逐一列举问题每个可能的解，分支结构用于实现检验，检验每一个解是否是问题真正的解，当然具体的检验条件和列举内容应该根据实际问题来进行设置。课堂练习：1、求15到100中，找出所有是3倍数的自然数.分析：要找出15到100中所有的3倍数，首先这个问题我是不是要用枚举算法来解，我先确定查找的答案的范围，很明显是15到100，假设用a来表示

7、1到1000之内的所有自然数，那么这道题我要用那么循环结构和枚举算法来做，循环结构的4个要素各是什么？1、初始化条件：a=15（我从几开始找？从1开始找，所以计数器的初始值应该是多少？）2、循环条件：a<=100（循环条件是什么？我从15找到几？找到100所以说查找的可能的答案的范围是从1到1000的所有自然数）循环体：把15到1000的所有自然数一个个带进去检验，把15代进去，15是3的倍数吗？？是的，我输出15，不是，下一个数应该是几？（用a怎么表示下一个数？）16是a是3的倍数吗？不是如果a是3的倍数(选择结构内这个检验条件应该怎么

8、写？)，就输出a，然后下一个数怎么表示？（a=a+1）在数学运算中，怎样才能判断一个数是否是3的倍数？如果这个数除以3的余数是0的话，那么就说明这个数是偶数，那么这个数a除以3的取它的余数是否