(
课件网) 第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) 谢谢聆听， 下节课再见！
