资源简介

(共13张PPT)
第12课 “韩信点兵”同余法的实现
学习内容
同余法的程序实现
同余法解决问题的一般过程
探 索
请填写下表，并从中找出规律。
建 构
上两节课学习了用枚举、筛选的算法来解决“韩信点兵”问题，这节课学习用同余的算法思想来解决韩信点兵”问题。《孙子算经》中记载了利用同余思想求解的方法，这种方法被称为“中国剩余定理”。
小知识
同余这个概念最初是由伟大的德国数学家高斯发现的。同余的定义：两个整数，若它们除以同一个整数，所得的余数相同，则称这两个整数对于除数同余。
一、抽象与建模
在韩信点兵中，用变量x来表示剩下的士兵总数。变量x需同时满足“x除以3余数为2、x除以5余数为3、x除以7余数为2”三个条件，且x的范围为1000-1100。由此，可建立如下模型:
根据同余定义，首先找出同时满足“x除以3余数为2、除以5余数为3、x除以7余数为2”三个条件的任意一个数，如233，然后将该数加减3、5、7的最小公倍数105的整数倍，在1000-1100范围内的数即是所求解。
试一试
233+105得到的数值（338）被3、5、7除的余数分别是多少
二、算法设计
根据刚才讲到的抽象与建模，用同余法解决“韩信点兵”问题时，将同时满足三个条件的任意一个数，用变量s表示，如s=233，三个数的最小公倍数用变量k表示。通过加（或减）k的整数倍，使s的值≥1000且≤1100，可以采用循环结构，根据条件“s小于1000”来选择加k或减k的值，可以采用分支结构。算法的流程图如下:
二、算法设计
三、算法的验证
利用Python语言编写程序如下:
拓 展
《孙子算经》中记载了如下算题:今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何
对于这个问题，首先找出能被 5与7整除而被3除余1的数70，被3与7整除而被 5除余1的数21，被3与5整除而被7除余1的数15。如果所求的数被3除余2，那么取数 70x 2=140，140是被5与7整除而被3除余2的数。如果所求数被 5除余3，那么取数21x3=63，63 是被3与7整除而被5除余3的数。如果所求数被7除余2，那么取数15x2=30.30是被3与5整除而被7除余2的数。
140+63+30=233，由于63与30都能被3整除，所以233与140这两个数被3除的余数相同，都是余 2。同理，233与63这两个数被5除的余数相同，都是 3;233与30被7除的余数相同，都是2。所以，233 是满足要求的一个数。
练 习
修改上述算法及程序，将上述“韩信点兵”问题的查找范围调整为2500-2600，输出相应结果。
谢谢！

展开更多......

收起↑