资源简介

(共15张PPT)
韩信点兵筛选法的实现
浙教版六年级上册
第11课 韩信点兵筛选法的实现
学习内容
1. 筛选法解决问题的一般过程。
2. 筛选法的实现。
探索
完成下表，你能得出符合条件的最小被除数是多少吗？
建构
“韩信点兵”问题的求解，除了枚举算法外，还可以采用筛选法来求解。
一、抽象与建模
韩信点兵过程中，剩下的士兵总数用变量 x 来表示。变量 x 的范围为1000~1100，且需同时满足“x 除 3 余数为 2、x 除 5 余数为 3、x 除 7 余数为 2”三个条件。由此，可建立如下模型：
在 1000~1100 这些数中，分别利用上述三个条件逐一进行筛选，最终剩下来的值就是所求解。即先利用“x 除 3 余数为 2”条件，删除 1000~1100 中不满足该条件的数，筛选满足该条件的数；再利用“x 除 5 余数为 3”条件，删除不满足该条件的数，筛选满足该条件的数；最后利用“x 除 7 余数为 2”条件，将筛选出来的数中不满足该条件的数删除，满足该条件的数筛选出来。
一、抽象与建模
筛选过程示意图如下所示：
二、算法设计
根据上述的抽象与建模，解决韩信点兵的问题可采用筛选算法。具体算
法如下：
（1）用 a 存储 1000~1100 范围内的数；
（2）在 a 中删除不满足“x 除 3 余数为 2”条件的数；
（3）在 a 中删除不满足“x 除 5 余数为 3”条件的数；
（4）在 a 中删除不满足“x 除 7 余数为 2”条件的数；
（5）找出 a 中剩下的数。
三、算法的验证
针对上述算法，利用 Python 语言进行局部验证。例如，显示1000~1100范围内满足“x 除 3 余数为 2”条件的数，对应的程序及运行结果如下所示：
三、算法的验证
想一想
在上述算法中，若对调步骤（2）和步骤（4），对算法的效率有何影响？
练一练
编程实现：在 1000~1100 范围内将满足“x 除 7 余数为 2”条件的数显示出来。
谢谢聆听！
INTERNET OF THINGS
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
兼职招聘：
https://www.21cnjy.com/recruitment/home/admin

展开更多......

收起↑