當前位置:編程學習大全網 - 熱門推薦 - 韓信點兵的數學原理

韓信點兵的數學原理

秦王暗點兵問題和韓信亂點兵問題,都是後人對物不知其數問題的壹種故事化。

物不知其數問題出自壹千六百年前我國古代數學名著《孫子算經》。原題為:"今有物不知其數,三三數之二,五五數之三,七七數之二,問物幾何?"

這道題的意思是:有壹批物品,不知道有幾件。如果三件三件地數,就會剩下兩件;如果五件五件地數,就會剩下三件;如果七件七件地數,也會剩下兩件。問:這批物品***有多少件?

變成壹個純粹的數學問題就是:有壹個數,用3除余2,用5除余3,用7除余2。求這個數。

這個問題很簡單:用3除余2,用7除也余2,所以用3與7的最小公倍數21除也余2,而用21除余2的數我們首先就會想到23;23恰好被5除余3,所以23就是本題的壹個答案。

這個問題之所以簡單,是由於有被3除和被7除余數相同這個特殊性。如果沒有這個特殊性,問題就不那麽簡單了,也更有趣得多。

我們換壹個例子;韓信點壹隊士兵的人數,三人壹組余兩人,五人壹組余三人,七人壹組余四人。問:這隊士兵至少有多少人?

這個題目是要求出壹個正數,使之用3除余2,用5除余3,用7除余4,而且希望所求出的數盡可能地小。

如果壹位同學從來沒有接觸過這類問題,也能利用試驗加分析的辦法壹步壹步地增加條件推出答案。

例如我們從用3除余2這個條件開始。滿足這個條件的數是3n+2,其中n是非負整數。

要使3n+2還能滿足用5除余3的條件,可以把n分別用1,2,3,…代入來試。當n=1時,3n+2=5,5除以5不用余3,不合題意;當n=2時,3n+2=8,8除以5正好余3,可見8這個數同時滿足用3除余2和用5除余3這兩個條件。

最後壹個條件是用7除余4。8不滿足這個條件。我們要在8的基礎上得到壹個數,使之同時滿足三個條件。

為此,我們想到,可以使新數等於8與3和5的壹個倍數的和。因為8加上3與5的任何整數倍所得之和除以3仍然余2,除以5仍然余3。於是我們讓新數為8+15m,分別把m=1,2,…代進去試驗。當試到m=3時,得到8+15m=53,53除以7恰好余4,因而53合乎題目要求。

我國古代學者早就研究過這個問題。例如我國明朝數學家程大位在他著的《算法統宗》(1593年)中就用四句很通俗的口訣暗示了此題的解法:

三人同行七十稀,

五樹梅花甘壹枝,

七子團圓正半月,

除百零五便得知。

"正半月"暗指15。"除百零五"的原意是,當所得的數比105大時,就105、105地往下減,使之小於105;這相當於用105去除,求出余數。

這四句口訣暗示的意思是:當除數分別是3、5、7時,用70乘以用3除的余數,用21乘以用5除的余數,用15乘以用7除的余數,然後把這三個乘積相加。加得的結果如果比105大,就除以105,所得的余數就是滿足題目要求的最小正整數解。

按這四句口訣暗示的方法計算韓信點的這隊士兵的人數可得:

70×2+21×3+15×4=263,

263=2×105+53,

所以,這隊士兵至少有53人。

在這種方法裏,我們看到:70、21、15這三個數很重要,稍加研究,可以發現它們的特點是:

70是5與7的倍數,而用3除余1;

21是3與7的倍數,而用5除余1;

15是3與5的倍數,而用7除余1。

因而

70×2是5與7的倍數,用3除余2;

21×3是3與7的倍數,用5除余3;

15×4是3與5的倍數,用7除余4。

如果壹個數除以a余數為b,那麽給這個數加上a的壹個倍數以後再除以a,余數仍然是b。所以,把70×2、21×3與15×4都加起來所得的結果能同時滿足"用3除余2、用5除余3、用7除余4"的要求。壹般地,

70m+21n+15k (1≤m<3, 1≤n<5,1≤k<7)

能同時滿足"用3除余m 、用5除余n 、用7除余k"的要求。除以105取余數,是為了求合乎題意的最小正整數解。

我們已經知道了70、21、15這三個數的性質和用處,那麽,是怎麽把它們找到的呢?要是換了壹個題目,三個除數不再是3、5、7,應該怎樣去求出類似的有用的數呢?

為了求出是5與7的倍數而用3除余1的數,我們看看5與7的最小公倍數是否合乎要求。5與7的最小公倍數是5×7=35,35除以3余2,35的2倍除以3余2,35的2倍除以3就能余1了,於是我們得到了"三人同行七十稀"。

為了求出是3與7的倍數而用5除余1的數,我們看看3與7的最小公倍數是否合乎要求。3與7的最小公倍數是3×7=21,21除以5恰好余1,於是我們得到了"五樹梅花甘壹枝"。

為了求出是3與5的倍數而用7除余1的數,我們看看3與5的最小公倍數是否合乎要求。3與5的最小公倍數是3×5=15,15除以7恰好余1,因而我們得到了"七子團圓正半月"。

3、5、7的最小公倍數是105,所以"除百零五便得知"。

例如:試求壹數,使之用4除余3,用5除余2,用7除余5。

解:我們先求是5與7的倍數而用4除余1的數;5與7的最小公倍數是5×7=35,35除以4余3,3×3除以4余1,因而35×3=105除以4余1,105是5與7的倍數而用4除余1的數。

我們再求4與7的倍數而用5除余1的數;4與7的最小公倍數是4×7=28,28除以5余3,3×7除以5余1,因而28×7=196除余5余1,所以196是4與7的倍數而用5除余1的數。

最後求的是4與5的倍數而用7除余1的數:4與5的最小公倍數是4×5=20,20除以7余6,6×6除以7余1,因而20×6=120除以7余1,所以120是4與5的倍數而用7除余1的數。

利用105、196、120這三個數可以求出符合題目要求的解:

105×3+196×2+120×5=1307。

由於4、5、7的最小公倍數是4×5×7=140,1307大於140,所以1307不是合乎題目要求的最小的解。用1037除以140得到的余數是47,47是合乎題目的最小的正整數解。

壹般地,

105m+196n+120k (1≤m<4,1≤n<5,1≤k<7)

是用4除余m,用5除余n,用7除余k的數(105m+196n+120k)除以140所得的余數是滿足上面三個條件的最小的正數。

上面我們是為了寫出105m+196n+120k這個壹般表達式才求出了105這個特征數。如果只是為了解答我們這個具體的例題,由於5×7=35既是5與7的倍數除以4又余3,就不必求出105再乘以3了。

35+196×2+120×5=1027

就是符合題意的數。

1027=7×140+47,

由此也可以得出符合題意的最小正整數解47。

《算法統宗》中把在以3、5、7為除數"物不知其數"問題中起重要作用的70、21、15這幾個特征數用幾句口訣表達出來了,我們也可以把在以4、5、7為除數的問題中起重要作用的105、196、120這幾個特征數編為口訣。留給讀者自己去編吧。

凡是三個除數兩兩互質的情況,都可以用上面的方法求解。

上面的方法所依據的理論,在中國稱之為孫子定理,國外的書籍稱之為中國剩余定理。

  • 上一篇:白羊座男生的性格特征
  • 下一篇:諾基亞c5-03裏面的quickoffice到底是什麽用的啊
  • copyright 2024編程學習大全網