算法实例枚举-萧山三中.ppt

* 枚举算法：就是按问题本身的性质，一一列举该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，如是，就采纳这个解，否则就抛弃它． 100个和尚吃100个馒头。大和尚一人吃3个，小和尚3人吃一个。求大、小和尚各多少个？” “一份单据中被涂抹的数字的推算”。有一张单据上有一个5位数的编号，其百位数和十位数处已经变得模糊不清，但是知道这个5位数是37或67的倍数，现在设计一个算法，找出所有满足这些条件的5位数，并统计个数。 解题步骤： １、分析问题　 枚举所有问题的可能解，范围应该是25006、25016、25026…25996，在这儿学生最有可能出现枚举太多可能的问题，会认为范围是从25006~25996之间的所有自然数， ２、确定方法 　　采用循环结构， ３、用流程图表示算法 (如果把j=100会有什么结果） 分析问题：枚举所有问题的可能解，范围应该是25006、25016、25026…25996，在这儿学生最有可能出现枚举太多可能的问题，会认为范围是从25006~25996之间的所有自然数，采用循环结构，画出程序流程框图。 使用自然语言或者流程图描述，通过自主学习、4人小组合作交流、完成问题分析。 同类迁移： “包装问题”。包装600个变形金刚，要求是 （1）包装的规格分别是：小盒可装2个，中盒可装5个，大盒可装8个；（2）每种规格的盒数都不能为0；设计一个算法输出所有可能的包装方案以及方案个数。 实践体验：直角三角形边长问题的算法。书籍直角三角形三条边a，b，c长度都是整数，其中一条直角边的长度是已知正整数a，斜边c的长度不超过某一正整数maxc，要求设计一个算法，输出满足上述条件的所有直角三角形本条边的长度。 大约在一千五百年前，大数学家孙子在《孙子算经》中记载了这样的一道题：“今有雏兔同笼，上有三十五头，下有九十四足，问雏兔各几何？”这四句的意思就是：有若干只鸡和兔在同一个笼子里，从上面数，有三十五个头；从下面数，有九十四只脚。求笼中各有几只鸡和兔？同学们，你会解答这个问题吗？你知道孙子是如何解答这个“鸡兔同笼”问题的？ 孙子巧解“鸡兔同笼” *