資源簡介

(共20張PPT)
韓信點(diǎn)兵同余法的實(shí)現(xiàn)
浙教版六年級(jí)上冊(cè)
第12課 韓信點(diǎn)兵同余法的實(shí)現(xiàn)
學(xué)習(xí)內(nèi)容
1. 同余法解決問題的一般過程。
2. 同余法的程序?qū)崿F(xiàn)。
探索
完成下表，你發(fā)現(xiàn)了什么現(xiàn)象？能得出什么結(jié)論？
建構(gòu)
“韓信點(diǎn)兵”問題除了通過枚舉、篩選的算法思想來解決外，還可以依據(jù)同余的算法思想來解決。《孫子算經(jīng)》中曾記載著利用同余思想求解的方法，稱之為“中國剩余定理”。
小知識(shí)
數(shù)學(xué)上，兩個(gè)整數(shù)除以同一個(gè)整數(shù)，若余數(shù)相同，則二整數(shù)同余。
小知識(shí)
《孫子算經(jīng)》中也有類似的問題：“今有物，不知其數(shù)，三三數(shù)之剩二， 五五數(shù)之剩三， 七七數(shù)之剩二，問物幾何？”
答曰：“二十三。”
術(shù) 曰：“ 三 三 數(shù) 之 剩 二， 則 置 一 百 四 十； 五 五 數(shù) 之 剩 三， 置六十三；七七數(shù)之剩二，置三十；并之得二百三十三，以二百一十減之，即得。”
該問題與“韓信點(diǎn)兵”類似，其提出的解法被稱為“孫子定理”“物不知數(shù)”“中國剩余定理”等，它是中國古代數(shù)學(xué)家的一項(xiàng)重大創(chuàng)造，在世界數(shù)學(xué)史上也有重要的地位。
一、抽象與建模
在韓信點(diǎn)兵過程中，剩下的士兵總數(shù)用變量 x 來表示。變量 x 的范圍為1000~1100，且需同時(shí)滿足“x 除 3 余數(shù)為 2、x 除 5 余數(shù)為 3、x 除 7 余數(shù)為 2”三個(gè)條件。
請(qǐng)思考模型
一、抽象與建模
建立如下模型：
根據(jù)同余思想，可先找出同時(shí)滿足“x 除 3 余數(shù)為 2、x 除 5 余數(shù)為 3、x除 7 余數(shù)為 2”三個(gè)條件的任意一個(gè)數(shù)，如 233，然后該數(shù)加減 3、5、7 的最小公倍數(shù) 105 的整數(shù)倍，在 1000~1100 范圍內(nèi)的數(shù)即是所求解。
試一試
338（233+105）被3、5、7除的余數(shù)分別是多少？
二、算法設(shè)計(jì)
根據(jù)上述的抽象與建模，解決韓信點(diǎn)兵的問題可采用同余算法。用變量s 表示所取到的同時(shí)滿足三個(gè)條件的任意一個(gè)數(shù)，如 233，變量 k 表示三個(gè)數(shù)的最小公倍數(shù)。通過加或減 k 的整數(shù)倍，使 s 的值大于等于 1000 且小于等于1100，可以采用循環(huán)結(jié)構(gòu)，根據(jù)條件“s 小于 1000”來選擇加 k 或減 k 的值，可以采用分支結(jié)構(gòu)。
二、算法設(shè)計(jì)
算法的流程圖如圖所示。
三、算法的程序?qū)崿F(xiàn)
上述算法用 Python 語言編寫的程序如下：
三、算法的程序?qū)崿F(xiàn)
請(qǐng)輸入以下代碼，并運(yùn)行
拓展
《孫子算經(jīng)》中提到的解法：
首先找出能被 5 與 7 整除而被 3 除余 1 的數(shù) 70，被 3 與 7 整除而被 5 除余 1 的數(shù) 21，被 3 與 5 整除而被 7 除余 1 的數(shù) 15。如果所求的數(shù)被 3 除余2，那么就取數(shù) 70×2 = 140，140 是被 5 與 7 整除而被 3 除余 2 的數(shù)。如果所求數(shù)被 5 除余 3，那么取數(shù) 21×3 = 63，63 是被 3 與 7 整除而被 5 除余 3的數(shù)。如果所求數(shù)被 7 除余 2，那就取數(shù) 15×2 = 30，30 是被 3 與 5 整除而被 7 除余 2 的數(shù)。
拓展
140 + 63 + 30 = 233，由于 63 與 30 都能被 3 整除，所以 233 與 140 這兩數(shù)被 3 除的余數(shù)相同，都是余 2，同理 233 與 63 這兩數(shù)被 5 除的余數(shù)相
同，都是 3，233 與 30 被 7 除的余數(shù)相同，都是 2。所以，233 是滿足要求的一個(gè)數(shù)。
練一練
若將上述問題中的查找范圍調(diào)整為 2500~2600，修改上述算法及程序，并輸出結(jié)果。
謝謝聆聽！
INTERNET OF THINGS
謝謝
21世紀(jì)教育網(wǎng)（www.21cnjy.com)
中小學(xué)教育資源網(wǎng)站
兼職招聘：
https://www.21cnjy.com/recruitment/home/admin

展開更多......

收起↑