资源简介

(共20张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（233+105）被3、5、7除的余数分别是多少？
二、算法设计
根据上述的抽象与建模，解决韩信点兵的问题可采用同余算法。用变量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，那么就取数 70×2 = 140，140 是被 5 与 7 整除而被 3 除余 2 的数。如果所求数被 5 除余 3，那么取数 21×3 = 63，63 是被 3 与 7 整除而被 5 除余 3的数。如果所求数被 7 除余 2，那就取数 15×2 = 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，修改上述算法及程序，并输出结果。
谢谢聆听！
INTERNET OF THINGS
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
兼职招聘：
https://www.21cnjy.com/recruitment/home/admin

展开更多......

收起↑