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

韓信點(diǎn)兵與中國剩余定理韓信點(diǎn)兵的故事

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

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

把所有正整數(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是最的１個(gè)解。篩法

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

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

程大位通過構(gòu)造三個(gè)特殊的數(shù)70,21,15，解決了一般的以3、5、7為除數(shù)的余數(shù)問題——為構(gòu)造被3除余a、被5除余b、被7除余c的數(shù)，只需計(jì)算N=a×70+b×21+c×15N必定滿足所有余數(shù)條件，而滿足條件的最小數(shù)則是N減去若干個(gè)105后的數(shù)。單因子構(gòu)件湊成法如果直接套用程大位的歌謠公式，只能限于解決除數(shù)為3、5、7的余數(shù)問題。當(dāng)除數(shù)換成其他數(shù)時(shí)，在解法中需要做相應(yīng)的調(diào)整。例如，當(dāng)三個(gè)除數(shù)分別為3、7、11時(shí)，我們首先要構(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ù)，只需再用這個(gè)數(shù)減去若干個(gè)3、7、11的最小公倍數(shù)231即可。試一試：一個(gè)數(shù)被3除余2，被7除余4，被11除余5，那這個(gè)數(shù)最小是多少？Ｎ＝2×154+4×99+5×210＝1754，1754-231×7=137單因子構(gòu)件湊成法

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

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

例如，要求被2，3，5，7除的余數(shù)分別為a,b,c,d的數(shù)，我們只需相應(yīng)構(gòu)造四個(gè)數(shù)。第一個(gè)數(shù)是3,5,7的公倍數(shù)且被2除余1，容易求得是105。第二個(gè)數(shù)是2,5,7的公倍數(shù)且被3除余1，是70。第三個(gè)數(shù)是2,3,7的公倍數(shù)且被5除余1，是126。第四個(gè)數(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)》，所以上面的算法在中國被稱為“孫子定理”。美國計(jì)算機(jī)科學(xué)的泰斗高德納在其著作《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》中也專門介紹了這個(gè)算法?！皩O子定理”的重要意義，遠(yuǎn)遠(yuǎn)不止是對(duì)一類余數(shù)問題給出了統(tǒng)一的算法。在余數(shù)問題中除數(shù)可能有三個(gè)、四個(gè)甚至更多，余數(shù)的值也有很多變化。而“孫子定理”只需要求解幾個(gè)余數(shù)很特殊的問題的解，就能把一般問題的解完全表示出來，即用“特解”表示出“通解”。這樣的思想在近代數(shù)學(xué)很多重要分支的發(fā)展中都被廣泛使用。中國剩余定理

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

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

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