18 枚举算法逐字稿 高中 · 信息技术 · 人教中图版 · 必修1 数据与计算

122024-01-04 09:54:47

老师

同学们大家好,我是北京师范大学附属实验中学的韩冬兵老师。今天我们来共同学习枚举算法。同学们在前面的课程中学习了三种程序结构,了解析算法的思想,通过找出解决问题的前提条件与结果之间关系的表达式,并计算表达式的值来实现问题的求解。这是中国古代孙子算经中的一道算术题。鸡兔同笼问题,笼子里共有 35 只头, 94 只脚,问鸡兔各有多少只?如果使用解析法解鸡兔同笼问题,可以先找出问题的已知条件与结果之间关系的数学表达式,通过表达式计算来实现问题的求解。那除了解析法,有没有其他的方法能够解鸡兔同笼问题?有同学马上会想到我们在循环结构中学过了的密码破解的例子,我们能不能通过一个一个的去尝试解决这个问题?根据已知条件,我们知道鸡和兔的总数是 35 只脚是 94 只,每只鸡有两只脚,每只兔有 4 只脚。我们是否可以一个列举所有积和兔的可能数量,计算出头和脚的总数量,再判断是否满足鸡兔同笼的条件。假设既有一只兔子有一只,结果不满足。假设既有一只兔子有两只,结果不满足。以此类推,列举出所有可能。

老师

计算机最擅长的就是计算,我们可以编写程序,让计算机逐一尝试,验证输出其中满足条件的鸡兔数量。这就是枚举算法的思想。同学们有没有觉得刚才的算法不太聪明,是不是感觉效率比较低?那根据鸡兔的总数是35,我们可以直接指枚举鸡的数量,再根据鸡兔的关系得出兔子的数量是35,减去鸡的数量。通过这样的优化策略来减少枚举的次数,可以使程序提高执行的效率。使用枚举法解决问题的思路就是依据问题的已知条件确定答案的大致范围,在此范围内一一列举所有可能的情况。比如鸡兔同笼问题中枚举的范围是多少,我们可以列举鸡的数量最少是一只,最多是 34 只。好接下来逐一检验该情况是否满足题目给出的条件,也就是判断条件是否成立。比如这里枚举积的数量,用 35 减去积的数量得到兔子的数量,再根据鸡兔的支数计算出角的数量,判断是否一共是 94 只角。如果满足就是本问题的解。这些解可能不止一个满足就可以输出,再去判断下一种情况是否满足。

老师

第二步,设计算法,一一列举。我们在前面的学习中已经用过很多次了,要用循环结构就可以解决了。逐一检验则需要用到分支结构,验证哪些情况满足问题的条件,如果满足就输出。这是鸡兔同笼问题的流程图。先从 1- 34 依次取数赋值给chicken,接下来将 rabbit 赋值为35,减去chick

查看隐藏内容
《18 枚举算法逐字稿 高中 · 信息技术 · 人教中图版 · 必修1 数据与计算》.doc
将本文下载保存,方便收藏和打印
导出文档
导出文档