资源简介

(共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”条件的数，对应的程序及运行结果如下所示：
三
算法的验证
编程实现：在1000-1100范围内将满足“x除以7余数为2”条件显示出来。
x=1000
while x<1101:
if x%7==1:
print(x,end=“ ”)
x=x+1
谢谢聆听，
下节课再见！

展开更多......

收起↑