中職教育二年級下學(xué)期數(shù)學(xué)《韓信點兵與中國剩余定理》課件

韓信點兵與中國剩余定理韓信點兵的故事

韓信是西漢時期的名將，也是我國著名的軍事家，“漢初三杰”，“兵家四圣”，古代軍事思想“兵權(quán)謀家”的代表人物。關(guān)于他有各種各樣或真或假的傳說，其中就有一個跟數(shù)學(xué)有很密切的關(guān)系。韓信點兵的故事3人一排，多出2人5人一排，多出3人7人一排，多出2人韓信點兵的故事韓信據(jù)此很快說出人數(shù)：1073人。漢軍本來就十分信服韓信大將軍，經(jīng)此之后就更加相信韓信是“天神下凡，神機妙算"，于是士氣大振，鼓聲喧天，在接下來的戰(zhàn)役中漢軍步步緊逼，楚軍亂作一團，大敗而逃。韓信由此名揚天下，被后世譽為“兵仙“，“神帥”。那么韓信是如何快速算出士兵人數(shù)的呢？

我們先把韓信點兵問題轉(zhuǎn)化為數(shù)學(xué)語言：一個數(shù)除以3余2，除以5余３，除以7余２。用“篩法”解決韓信點兵問題

把所有正整數(shù)過第一遍篩子，篩選出“三三數(shù)之剩2”的數(shù)，即“用3除余2”的數(shù)，有2，5，8，11，14，17，20，23，26，29，……

再把這些數(shù)過第二遍篩子，篩選出“五五數(shù)之剩3”的數(shù)，即“用5除余3”的數(shù)，有8，23……

再把這些數(shù)過第三遍篩子，篩選出“七七數(shù)之剩2”的數(shù)，即“用7除余2”的數(shù)，有23……

由此得到23是最的１個解。篩法

把這里的解題方法總結(jié)為“篩法”，篩法就成為一般性方法，還可以用來解決其他類似問題。由于每次篩選后，都還有無窮多個數(shù)，所以解可能不是唯一的，很可能有無窮多個解。至于下一個解是什么，要把……寫出來才知道。實踐發(fā)現(xiàn)這是要費一點功夫的。那有沒有簡單的方法來解決這個問題呢？用“歌謠”解決韓信點兵問題明朝，我國著名的數(shù)學(xué)家程大位在《算法統(tǒng)宗》里以歌謠的方式給出了這個問題的解法。

三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百零五便得之。在歌謠的前三句中，每句給出一組數(shù)，分別是(3,70)，(5,21)，(7,15)。在這三組數(shù)中，每一組的前一個數(shù)就是“韓國點兵”問題中出現(xiàn)的三個除數(shù)3、5、7，那么后一個數(shù)呢？先來看70，這個數(shù)是除以3余1且被5和7整除的最小的數(shù)。類似地，21是除以5余1且被3和7整除的最小的數(shù)，15是除以7余1且被3和5整除的最小的數(shù)。用“歌謠”解決韓信點兵問題現(xiàn)在來看下面這個數(shù)：M=2×70+3×21+2×15我們檢驗一下M除以3、5、7的余數(shù)。注意到M是三個乘積的和，由于70被3除余1，所以第一個乘積2×70被3除余2。而后兩個乘積都能被3整除，因此M被3除余2。再來看M除以5的余數(shù)。由于第一和第三個乘積都被5整除，而第二個乘積被5除余3，所以M被5除余3。類似地可以推出M被7除余2。綜上所述，M被3除余2，被5除余3，被7除余2，正好是故事《韓信點兵》中所提問題的答案。容易算出M的值是233。用“歌謠”解決韓信點兵問題我們利用歌謠的前三句已經(jīng)給出了問題的答案，最后一句“除百零五便得知”有什么作用呢？是不是只為了湊足四句話？非也。上面雖然給出了滿足三個余數(shù)條件的一個數(shù)，但這樣的數(shù)是無窮多的。這些數(shù)有一個特點，即任兩個數(shù)的差都是3、5、7的公倍數(shù)。當(dāng)問題的解不唯一時，數(shù)學(xué)家通常對最小解比較感興趣。歌謠的最后一句話，意思就是用233減去若干個3、5、7的最小公倍數(shù)105，余數(shù)23就是答案。在“韓信點兵”的故事中要求的是大于1000且滿足三個余數(shù)條件的數(shù)，所以要用23加上105的10倍，答案即為1073。

程大位通過構(gòu)造三個特殊的數(shù)70,21,15，解決了一般的以3、5、7為除數(shù)的余數(shù)問題——為構(gòu)造被3除余a、被5除余b、被7除余c的數(shù)，只需計算N=a×70+b×21+c×15N必定滿足所有余數(shù)條件，而滿足條件的最小數(shù)則是N減去若干個105后的數(shù)。單因子構(gòu)件湊成法如果直接套用程大位的歌謠公式，只能限于解決除數(shù)為3、5、7的余數(shù)問題。當(dāng)除數(shù)換成其他數(shù)時，在解法中需要做相應(yīng)的調(diào)整。例如，當(dāng)三個除數(shù)分別為3、7、11時，我們首先要構(gòu)造被3除余1且被7、11整除的數(shù)。列出7和11的公倍數(shù)77,154,231,……，其中被3除余1的最小的數(shù)是154。其次求被7除余1且被3、11整除的數(shù)，最小的是99。最后求被11除余1且被3、7整除的數(shù)，最小的是210。于是，被3除余a、被7除余b、被11除余c的數(shù)就是

Ｎ＝a×154+b×99+c×210如果要找滿足所有余數(shù)條件的最小的數(shù)，只需再用這個數(shù)減去若干個3、7、11的最小公倍數(shù)231即可。試一試：一個數(shù)被3除余2，被7除余4，被11除余5，那這個數(shù)最小是多少？Ｎ＝2×154+4×99+5×210＝1754，1754-231×7=137單因子構(gòu)件湊成法

在上面的算法流程中，唯一需要變化調(diào)整的是三個具有特殊余數(shù)的數(shù)。當(dāng)除數(shù)為(3，5，7)時，它們是(70，21，15)；當(dāng)除數(shù)為(3，7，11)時，它們是(154，99，210)。無論除數(shù)是什么，第一個數(shù)關(guān)于三個除數(shù)的余數(shù)為1，0，0，第二個數(shù)關(guān)于三個除數(shù)的余數(shù)為0，1，0，第三個數(shù)關(guān)于三個除數(shù)的余數(shù)為0，0，1。

同學(xué)，你通過觀察，會發(fā)現(xiàn)這個兩個問題在數(shù)學(xué)思想上兩者根本就是一回事。如果理解清楚了這個思想，就很容易明白如果問題中涉及四個、五個甚至更多余數(shù)條件，這個算法仍然適用。

例如，要求被2，3，5，7除的余數(shù)分別為a,b,c,d的數(shù)，我們只需相應(yīng)構(gòu)造四個數(shù)。第一個數(shù)是3,5,7的公倍數(shù)且被2除余1，容易求得是105。第二個數(shù)是2,5,7的公倍數(shù)且被3除余1，是70。第三個數(shù)是2,3,7的公倍數(shù)且被5除余1，是126。第四個數(shù)是2,3,5的公倍數(shù)且被7除余1，是120。所以a×105+b×70+c×126+d×120。除以2,3,5,7的余數(shù)恰好分別是a，b，c，d。孫子定理

由于余數(shù)問題最早出自《孫子算經(jīng)》，所以上面的算法在中國被稱為“孫子定理”。美國計算機科學(xué)的泰斗高德納在其著作《計算機程序設(shè)計藝術(shù)》中也專門介紹了這個算法?！皩O子定理”的重要意義，遠(yuǎn)遠(yuǎn)不止是對一類余數(shù)問題給出了統(tǒng)一的算法。在余數(shù)問題中除數(shù)可能有三個、四個甚至更多，余數(shù)的值也有很多變化。而“孫子定理”只需要求解幾個余數(shù)很特殊的問題的解，就能把一般問題的解完全表示出來，即用“特解”表示出“通解”。這樣的思想在近代數(shù)學(xué)很多重要分支的發(fā)展中都被廣泛使用。中國剩余定理

不過“孫子定理”在解決余數(shù)問題時還是留了個小尾巴——如何求“特解”？雖然來自實際應(yīng)用的余數(shù)問題通常只涉及三四個余數(shù)，特解很容易找到，但數(shù)學(xué)家解決問題都追求一般性，他們想解決的不僅是包含三四個除數(shù)的余數(shù)問題，也不是三四十個除數(shù)，而是任意多個除數(shù)。

1247年南宋的數(shù)學(xué)家秦九韶把《孫子算經(jīng)》中“物不知數(shù)”一題的方法推廣到一般的情況，稱為“大衍求一術(shù)”，在《數(shù)書九章》中發(fā)表。這個結(jié)論在歐洲要到十八世紀(jì)才由數(shù)學(xué)家高斯和歐拉發(fā)現(xiàn)。所以世界公認(rèn)這個定理是中國人最早發(fā)現(xiàn)的，特別稱之為“中國剩余定理”。中國剩余定理

中國剩余定理不僅有光輝的歷史意義，直到現(xiàn)在還是一個非常重