资源简介

(共16张PPT)
第12课
“韩信点兵”同余法的实现
主要内容：
1.同余法解决问题的一般过程。
2.同余法的实现。
完成下表，你发现了什么现象？能得出什么结论？
“韩信点兵”问题除了通过枚举、筛选的算法思想来解决外，还可以根据同余的算法思想来解决。《孙子算经》中曾记载着利用同余思想求解的方法，这种方法被称为“中国剩余定理”。
一
抽象与建模
在韩信点兵过程中，剩下的士兵总数用变量X来表示。变量X的范围为1000-1100，且需同时满足“X除以3余数为2、X除以5余数为3、X除以7余数为2”三个条件。由此可以建立如下模型：
根据同余思想，可先找出同时满足“X除以3余数为2、X除以5余数为3、X除以7余数为2”三个条件的任意一个数，如233，然后将该数加减3、5、7的最小公倍数105的整数倍，在1000-1100范围内的数即是所求解。
一
抽象与建模
338÷3=112...2 338÷5=67...3 338÷7=48...2
二
算法设计
根据上述的抽象与建模，用同余算法解决“韩信点兵”问题时，用变量s表示所取到的同时满足三个条件的任意一个数，如233，用变量k表示三个数的最小公倍数。通过加或减k的整数倍，使s的值大于等于1000且小于等于1100，可以采用循环结构，根据条件“s小于1000”来选择加k或减k的值，可以采用分支结构。算法的流程图如下：
二
算法设计
三
算法的程序实现
上述算法用Python语言编写的程序如下：
《孙子算经》中记载了如下算题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
对于这个问题，首先找出能被与整除而被除余的数70，被3与7整除而被5除余1的数21，被3与5整除而被7除余1的数15.如果所求的数被3除余2，那么取数70×2=140,140是被与7整除而被3除余2的数。如果所求数被5除余3，那么取数21×3=63,63是被3与7整除而被5除余3的数。如果所求数被7除余2，那么取数15×2=30,30是被3与5整除而被7除余2的数。
140+60+30=233，由于63与30都能被3整除，所以233与140这两个数被3除的余数相同，都是余2。同理，233与63这两个数被5除的余数相同，都是3；233与30被7除的余数相同，都是2。所以，233是满足要求的一个数。
若将上述“韩信点兵”问题的查找范围调整为2500-2600，修改上述算法及程序，并输出结果。
s=233
k=3*5*7
while s<2500 or s>2600:
if s<2500:
s=s+k
else:
s=s-k
print(“剩余的士兵数为：”,s)
谢谢聆听，
下节课再见！

展开更多......

收起↑