資源簡介

(共13張PPT)
第12課 “韓信點兵”同余法的實現(xiàn)
學(xué)習(xí)內(nèi)容
同余法的程序?qū)崿F(xiàn)
同余法解決問題的一般過程
探 索
請?zhí)顚懴卤恚闹姓页鲆?guī)律。
建 構(gòu)
上兩節(jié)課學(xué)習(xí)了用枚舉、篩選的算法來解決“韓信點兵”問題，這節(jié)課學(xué)習(xí)用同余的算法思想來解決韓信點兵”問題。《孫子算經(jīng)》中記載了利用同余思想求解的方法，這種方法被稱為“中國剩余定理”。
小知識
同余這個概念最初是由偉大的德國數(shù)學(xué)家高斯發(fā)現(xiàn)的。同余的定義：兩個整數(shù)，若它們除以同一個整數(shù)，所得的余數(shù)相同，則稱這兩個整數(shù)對于除數(shù)同余。
一、抽象與建模
在韓信點兵中，用變量x來表示剩下的士兵總數(shù)。變量x需同時滿足“x除以3余數(shù)為2、x除以5余數(shù)為3、x除以7余數(shù)為2”三個條件，且x的范圍為1000-1100。由此，可建立如下模型:
根據(jù)同余定義，首先找出同時滿足“x除以3余數(shù)為2、除以5余數(shù)為3、x除以7余數(shù)為2”三個條件的任意一個數(shù)，如233，然后將該數(shù)加減3、5、7的最小公倍數(shù)105的整數(shù)倍，在1000-1100范圍內(nèi)的數(shù)即是所求解。
試一試
233+105得到的數(shù)值（338）被3、5、7除的余數(shù)分別是多少
二、算法設(shè)計
根據(jù)剛才講到的抽象與建模，用同余法解決“韓信點兵”問題時，將同時滿足三個條件的任意一個數(shù)，用變量s表示，如s=233，三個數(shù)的最小公倍數(shù)用變量k表示。通過加（或減）k的整數(shù)倍，使s的值≥1000且≤1100，可以采用循環(huán)結(jié)構(gòu)，根據(jù)條件“s小于1000”來選擇加k或減k的值，可以采用分支結(jié)構(gòu)。算法的流程圖如下:
二、算法設(shè)計
三、算法的驗證
利用Python語言編寫程序如下:
拓 展
《孫子算經(jīng)》中記載了如下算題:今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何
對于這個問題，首先找出能被 5與7整除而被3除余1的數(shù)70，被3與7整除而被 5除余1的數(shù)21，被3與5整除而被7除余1的數(shù)15。如果所求的數(shù)被3除余2，那么取數(shù) 70x 2=140，140是被5與7整除而被3除余2的數(shù)。如果所求數(shù)被 5除余3，那么取數(shù)21x3=63，63 是被3與7整除而被5除余3的數(shù)。如果所求數(shù)被7除余2，那么取數(shù)15x2=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 是滿足要求的一個數(shù)。
練 習(xí)
修改上述算法及程序，將上述“韓信點兵”問題的查找范圍調(diào)整為2500-2600，輸出相應(yīng)結(jié)果。
謝謝！

展開更多......

收起↑