资源简介

(共12张PPT)
第11课 “韩信点兵”筛选法的实现
学习内容
筛选法的实现
筛选法解决问题的一般过程
探 索
请思考下表中符合条件的被除数，并得出相应的最小被除数。
建 构
“韩信点兵”问题还可以用筛选法来求解。
一、抽象与建模
“韩信点兵”问题中，用变量x来表示剩下的士兵总数。变量x满足“x除以3余数为2、除以5余数为3、除以7余数为2”三个条件，且其范围是1000-1100。由此，可建立如下模型:
在1000-1100中，利用上述三个条件逐一进行筛选，得到的最终数值就是所求解。也就是说先根据“x除以3余数为2”条件，筛选出满足该条件的数;再根据“x除以5余数为3”条件，在上述所得数中，再筛选出满足该条件的数:最后根据“x除以7余数为2”条件，在第二次筛选后得到的数中，最终筛选出满足该条件的数。
一、抽象与建模
筛选过程如下所示:
第一次筛选:根据“x除以3余数为2”条件
第二次筛选:根据“x除以5余数为3”条件
第三次筛选:根据“x除以7余数为2”条件
二、算法设计
根据刚才讲到的抽象与建模，用筛选法解决“韩信点兵”问题的算法如下:
三、算法的验证
利用Python语言编写程序，对上述算法进行局部验证。比如，输出1000-1100范围内满足条件--除以3余数为2的数值，相应程序及运行结果如下:
三、算法的验证
想一想
如果将在上述算法中的步骤(2)和步骤(4)对调，算法的效率会有什么变化
练 习
利用Python语言编写程序，输出1000-1100范围内满足条件--除以7余数为2的数值。
谢谢！

展开更多......

收起↑