韓信點兵演算法口訣

① 韓信點兵的計算公式是什麼

相傳韓信才智過人，從不直接清點自己軍隊的人數，只要讓士兵先後以三人一排、五人一排、七人一排地變換隊形，而他每次只掠一眼隊伍的排尾就知道總人數了。輸入3個非負整數a,b,c ，表示每種隊形排尾的人數（a<3,b<5,c<7），輸出總人數的最小值（或報告無解）。已知總人數不小於10，不超過100 。

輸入

輸入3個非負整數a,b,c ，表示每種隊形排尾的人數（a<3,b<5,c<7）。例如,輸入：2 4 5

輸出

輸出總人數的最小值（或報告無解，即輸出Noanswer）。實例，輸出：89

樣例輸入

2 1 6

樣例輸出

41

定理1 如a被n除所得的余數等b被n除所得的余數，c被n除所得的余數等於d被n除所得的余數， 則ac被n除所得的余數等於b d被n除所得的余數。

用同餘式敘述就是：

如a≡b（mod n ），c≡d（mod n ）

則ac≡b d（mod n ） 

定理2 被除數a加上或減去除數b的倍數，再除以b，余數r不變。即

如a ≡ r（mod b ），則a ± b n≡r（mod b ）

例如70≡1（mod 3 ）可得70±10×3≡1（mod 3 ） 

【韓信點兵法口訣的原理】

①能被5,7除盡數是35k,其中k=2，即70除3正好餘1，70a 除3正好余a。

②能被3,7除盡數是21k,其中k=1，即21除5正好餘1，21b 除5正好余b。

③能被3,5除盡數是15k,其中k=1，即15除7正好餘1，15c 除7正好余c。

② 韓信大點兵口訣

民間傳說著一則故事——「韓信點兵」。

秦朝末年，楚漢相爭。一次，韓信將1500名將士與楚王大將李鋒交戰。苦戰一場，楚軍不敵，敗退回營，漢軍也死傷四五百人，於是韓信整頓兵馬也返回大本營。當行至一山坡，忽有後軍來報，說有楚軍騎兵追來。只見遠方塵土飛揚，殺聲震天。漢軍本來已十分疲憊，這時隊伍大嘩。韓信兵馬到坡頂，見來敵不足五百騎，便急速點兵迎敵。他命令士兵3人一排，結果多出2名；接著命令士兵5人一排，結果多出3名；他又命令士兵7人一排，結果又多出2名。韓信馬上向將士們宣布：我軍有1073名勇士，敵人不足五百，我們居高臨下，以眾擊寡，一定能打敗敵人。漢軍本來就信服自己的統帥，這一來更相信韓信是「神仙下凡」、「神機妙算」。於是士氣大振。一時間旌旗搖動，鼓聲喧天，漢軍步步進逼，楚軍亂作一團。交戰不久，楚軍大敗而逃。

首先我們先求5、9、13、17之最小公倍數9945（註：因為5、9、13、17為兩兩互質的整數，故其最小公倍數為這些數的積），然後再加3，得9948（人）。

在一千多年前的《孫子算經》中，有這樣一道算術題：

「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？」按照今天的話來說：一個數除以3餘2，除以5餘3，除以7餘2，求這個數.

這樣的問題，也有人稱為「韓信點兵」.它形成了一類問題，也就是初等數論中解同餘式.這類問題的有解條件和解的方法被稱為「中國剩餘定理」，這是由中國人首先提出的.

① 有一個數，除以3餘2，除以4餘1，問這個數除以12餘幾？

解：除以3餘2的數有：

2， 5， 8， 11，14， 17， 20， 23….

它們除以12的余數是：

2，5，8，11，2，5，8，11，….

除以4餘1的數有：

1， 5， 9， 13， 17， 21， 25， 29，….

它們除以12的余數是：

1， 5， 9， 1， 5， 9，….

一個數除以12的余數是唯一的.上面兩行余數中，只有5是共同的，因此這個數除以12的余數是5.

如果我們把①的問題改變一下，不求被12除的余數，而是求這個數.很明顯，滿足條件的數是很多的，它是 5＋12×整數，

整數可以取0，1，2，…，無窮無盡.事實上，我們首先找出5後，注意到12是3與4的最小公倍數，再加上12的整數倍，就都是滿足條件的數.這樣就是把「除以3餘2，除以4餘1」兩個條件合並成「除以12餘5」一個條件.《孫子算經》提出的問題有三個條件，我們可以先把兩個條件合並成一個.然後再與第三個條件合並，就可找到答案.

②一個數除以3餘2，除以5餘3，除以7餘2，求符合條件的最小數.

解：先列出除以3餘2的數：

2， 5， 8， 11， 14， 17， 20， 23， 26，…，

再列出除以5餘3的數：

3， 8， 13， 18， 23， 28，….

這兩列數中，首先出現的公共數是8.3與5的最小公倍數是15.兩個條件合並成一個就是8＋15×整數，列出這一串數是8， 23， 38，…，再列出除以7餘2的數 2， 9， 16， 23， 30，…，

就得出符合題目條件的最小數是23.

事實上，我們已把題目中三個條件合並成一個：被105除餘23.

那麼韓信點的兵在1000-1500之間，應該是105×10+23=1073人

中國有一本數學古書「孫子算經」也有類似的問題：「今有物，不知其數，三三數之，剩二，五五數之，剩三，七七數之，剩二，問物幾何？」

答曰：「二十三」

術曰：「三三數之剩二，置一百四十，五五數之剩三，置六十三，七七數之剩二，置三十，並之，得二百三十三，以二百一十減之，即得。凡三三數之剩一，則置七十，五五數之剩一，則置二十一，七七數之剩一，則置十五，即得。」

孫子算經的作者及確實著作年代均不可考，不過根據考證，著作年代不會在晉朝之後，以這個考證來說上面這種問題的解法，中國人發現得比西方早，所以這個問題的推廣及其解法，被稱為中國剩餘定理。中國剩餘定理（Chinese Remainder Theorem）在近代抽象代數學中佔有一席非常重要的地位。

簡單扼要總結:
1.算兩兩數之間的能整除數
2.算三個數的能整除數
3.用1中的三個整除數之和減去2中的整除數之差(有時候是倍數)
4計算結果即可

③ 韓信點兵的計算公式是什麼

古代時候有個《孫子算經》有幾句乘法口訣：三人同行七十稀， 五樹梅花廿一枝， 七子團圓正半月， 除百零五便得知。 意思是 3人一數剩下余數*70。5人一數剩下余數*21。七人一數剩下余數*15。然後+105.加到你感覺對啦就知道了。因為已知死了四五百了。

所以演算法是這樣的：2*70+4*21+6*15=314人

314+105+105+105+105+105+105+105=1049人。

④ 誰知到那個韓信點兵的計算公式，關於余數的好像是算總

韓信亂點兵口訣：三人同行七十稀，五束梅花二十一，妻子團圓整半月，除百零五便得知。
適用范圍是已知總數除以3、5、7後的余數，並且要知道總數的取值范圍。然後用除以3的余數乘以70，5的余數乘以21，7的余數乘以15，最後把這三個數的和加起來根據數值范圍減（或者加）若干個105（3、5、7的最小公倍數）求解。
比如：100以內的一個數，除以3餘2，除以5餘3，除以7餘4，則2x70=140，3x21=63，4x15=60，140+63+60=263，263-105=158，158-105=53。

⑤ "韓信點兵"怎麼個點法

分類: 文化/藝術 >> 文學 >> 小說
問題描述:

據說韓信點兵是非常科學的,可我卻不清楚有誰在嗎?

解析:

韓信點兵

作者：jianhao

漢高祖劉邦曾問大將韓信：「你看我能帶多少兵？」韓信斜了劉邦一眼說：「你頂多能帶十萬兵吧！」漢高祖心中有三分不悅，心想：你竟敢小看我！「那你呢？」韓信傲氣十足地說：「我呀，當然是多多益善啰！」劉邦心中又添了三分不高興，勉強說：「將軍如此大才，我很佩服。現在，我有一個小小的問題向將軍請教，憑將軍的大才，答起來一定不費吹灰之力的。」韓信滿不在乎地說：「可以可以。」劉邦狡黠地一笑，傳令叫來一小隊士兵隔牆站隊，劉邦發令：「每三人站成一排。」隊站好後，小隊長進來報告：「最後一排只有二人。」「劉邦又傳令：「每五人站成一排。」小隊長報告：「最後一排只有三人。」劉邦再傳令：「每七人站成一排。」小隊長報告：「最後一排只有二人。」劉邦轉臉問韓信：「敢問將軍，這隊士兵有多少人？」韓信脫口而出：「二十三人。」劉邦大驚，心中的不快已增至十分，心想：「此人本事太大，我得想法找個岔子把他殺掉，免生後患。」一面則佯裝笑臉誇了幾句，並問：「你是怎樣算的？」韓信說：「臣幼得黃石公傳授《孫子算經》，這孫子乃鬼穀子的弟子，算經中載有此題之演算法，口訣是：

三人同行七十稀，

五樹梅花開一枝，

七子團圓正月半，

除百零五便得知。」

劉邦出的這道題，可用現代語言這樣表述：

「一個正整數，被3除時餘2，被5除時餘3，被7除時餘2，如果這數不超過100，求這個數。」

《孫子算經》中給出這類問題的解法：「三三數之剩二，則置一百四十；五五數之剩三，置六十三；七七數之剩二，置三十；並之得二百三十三，以二百一十減之，即得。凡三三數之剩一，則置七十；五五數之剩一，則置二十一；七七數之剩一，則置十五，一百六以上，以一百五減之，即得。」用現代語言說明這個解法就是：

首先找出能被5與7整除而被3除餘1的數70，被3與7整除而被5除餘1的數21，被3與5整除而被7除餘1的數15。

所求數被3除餘2，則取數70×2＝140，140是被5與7整除而被3除餘2的數。

所求數被5除餘3，則取數21×3＝63，63是被3與7整除而被5除餘3的數。

所求數被7除餘2，則取數15×2=30，30是被3與5整除而被7除餘2的數。

又，140＋63＋30=233，由於63與30都能被3整除，故233與140這兩數被3除的余數相同，都是餘2，同理233與63這兩數被5除的余數相同，都是3，233與30被7除的余數相同，都是2。所以233是滿足題目要求的一個數。

而3、5、7的最小公倍數是105，故233加減105的整數倍後被3、5、7除的余數不會變，從而所得的數都能滿足題目的要求。由於所求僅是一小隊士兵的人數，這意味著人數不超過100，所以用233減去105的2倍得23即是所求。

這個演算法在我國有許多名稱，如「韓信點兵」，「鬼谷算」，「隔牆算」，「剪管術」，「神奇妙算」等等，題目與解法都載於我國古代重要的數學著作《孫子算經》中。一般認為這是三國或晉時的著作，比劉邦生活的年代要晚近五百年，演算法口訣詩則載於明朝程大位的《演算法統宗》，詩中數字隱含的口訣前面已經解釋了。宋朝的數學家秦九韶把這個問題推廣，並把解法稱之為「大衍求一術」，這個解法傳到西方後，被稱為「孫子定理」或「中國剩餘定理」。而韓信，則終於被劉邦的妻子呂後誅殺於未央宮。

請你試一試，用剛才的方法解下面這題：

一個數在200與400之間，它被3除餘2，被7除餘3，被8除餘5，求該數。

（解：112×2＋120×3＋105×5＋168k，取k＝-5得該數為269。）

什麼叫做「韓信點兵」？

韓信點兵是一個有趣的猜數游戲。如果你隨便拿一把蠶豆（數目約在100粒左右），先3粒3粒地數，直到不滿3粒時，把余數記下來；第二次再5粒5粒地數，最後把余數記下來；第三次是7粒一數，把余數記下來。然後根據每次的余數，就可以知道你原來拿了多少粒蠶豆了。不信的話，你還可以實地試驗一下。例如，假如3粒一數餘1粒，5粒一數餘2粒，7粒一數餘2粒，那麼，原有蠶豆有多少粒呢？

這類題目看起來是很難計算的，可是我國有時候卻流傳著一種演算法，綜的名稱也很多，宋朝周密叫它「鬼谷算」，又名「隔牆算」；楊輝叫它「剪管術」；而比較通行的名稱是「韓信點兵」。最初記述這類演算法的是一本名叫《孫子算經》的書，後來在宋朝經過數學家秦九韶的推廣，又發現了一種演算法，叫做「大衍求一術」。這在數學史上是極有名的問題，外國人一般把它稱為「中國剩餘定理」。至於它的演算法，在《孫子算經》上就已經有了說明，而且後來還流傳著這么一道歌訣：

三人同行七十稀，

五樹梅花廿一枝，

七子團圓正半月，

除百零五便得知。

這就是韓信點兵的計算方法，它的意思是：凡是用3個一數剩下的余數，將它用70去乘（因為70是5與7的倍數，而又是以3去除餘1的數）；5個一數剩下的余數，將它用21去乘（因為21是3與7的倍數，又是以5去除餘1的數）；7個一數剩下的余數，將它用15去乘（因為15是3與5的倍數，又是以7去除餘1的數），將這些數加起來，若超過105，就減掉105，如果剩下來的數目還是比105大，就再減去105，直到得數比105小為止。這樣，所得的數就是原來的數了。根據這個道理，你可以很容易地把前面的五個題目列成算式：

1×70＋2×21＋2×15－105

＝142－105

＝37

因此，你可以知道，原來這一堆蠶豆有37粒。

1900年，德國大數學家大衛·希爾伯特歸納了當時世界上尚未解決的最困難的23個難題。後來，其中的第十問題在70年代被解決了，這是近代數學的五個重大成就。據證明人說，在解決問題的過程中，他是受到了「中國剩餘定理」的啟發的。