第12课 “韩信点兵”同余法的实现（课件）六年级上册信息技术浙教版.pptVIP

第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语言编写程序如下: *