《第12課“韓信點兵”同余法的實現(xiàn)》參考課件1

第12課“韓信點兵”同余法的實現(xiàn)學習內容同余法的程序實現(xiàn)同余法解決問題的一般過程探

索

請?zhí)顚懴卤恚闹姓页鲆?guī)律。建

構

上兩節(jié)課學習了用枚舉、篩選的算法來解決“韓信點兵”問題，這節(jié)課學習用同余的算法思想來解決韓信點兵”問題?！秾O子算經》中記載了利用同余思想求解的方法，這種方法被稱為“中國剩余定理”。小知識

同余這個概念最初是由偉大的德國數(shù)學家高斯發(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范圍內的數(shù)即是所求解。試一試233+105得到的數(shù)值（338）被3、5、7除的余數(shù)分別是多少?二、算法設計

根據(jù)剛才講到的抽象與建模，用同余法解決“韓信點兵”問題時，將同時滿足三個條件的任意一個數(shù)，用變量s表示，如s=233，三個數(shù)的最小公倍數(shù)用變量k表示。通過加（或減）k的整數(shù)倍，使s的值≥1000且≤1100，可以采用循環(huán)結構，根據(jù)條件“s小于1000”來選擇加k或減k的值，可以采用分支結構。算法的流程圖如下:二、算法設計三、算法的驗證

利用Python語言編寫程序如下:拓

展

《孫子算經》中記載了如下算題:今有物不知其數(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ù)70x2=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ù)。練

習