韓信點(diǎn)兵怎么通關(guān)不了(韓信點(diǎn)兵快速解法)
1. 韓信點(diǎn)兵快速解法
物不知數(shù)
韓信點(diǎn)兵問題最早出自《孫子算經(jīng)》?！秾O子算經(jīng)》是中國古代非常重要的數(shù)學(xué)著作，因數(shù)學(xué)家 孫子 貢獻(xiàn)最大而得名（關(guān)于孫子的資料不可考），大約成書于東晉十六國時期，現(xiàn)存最早為北宋刻本，全書分三卷：《卷上》、《卷中》、《卷下》，主要講述 度量規(guī)定 和 算籌運(yùn)算 以及基于 它們的 數(shù)學(xué)應(yīng)為問題，韓信點(diǎn)兵為 《卷下》第二十六題 ”物不知數(shù)“，原文如下：
今有物，不知其數(shù)。三、三數(shù)之，剩二；五、五數(shù)之，剩三；七、七數(shù)之，剩二。問物幾何？
答曰：二十三。
術(shù)曰：“三、三數(shù)之，剩二”，置一百四十；“五、五數(shù)之，剩三”，置六十三；“七、七數(shù)之，剩二”，置三十。并之，得二百三十三。以二百一十減之，即得。凡三、三數(shù)之，剩一，則置七十；五，五數(shù)之，剩一，則置二十一；七、七數(shù)之，剩一，則置十五。一百六以上，以一百五減之，即得。
題目翻譯成現(xiàn)今的數(shù)學(xué)語言如下：
有一個正整數(shù) x，知 x 除以 3 余 2、除以 5 余數(shù) 3、除以 7 余數(shù) 2， 求 x 的最小值。
這等價于求解《初等數(shù)論》中的 一次同余方程組：
《孫子算經(jīng)》給出的解法如下：
尋中最小正整數(shù) x? ， 滿足： x? 被 5 和 7 整除 并且 除以 3 余 1，即，5|x?, 7|x? 并且 x? mod 3 = 1 ②
x? 被 5 和 7 整除，就意味著 被 5×7 = 35 整除，即， 35 | x?，于是，令 x? = 35n（n ≥ 1）：
當(dāng) n = 1 時 x? = 35，35 mod 3 = 2 不滿足 ② 舍棄；
當(dāng) n = 2 時 x? = 70，70 mod 3 = 1 剛好滿足 ②，Bingo~~~。
由于 x? ≡ 1 (mod 3)，故 2x? ≡ 2 (mod 3)，于是 得到 2x? = 140，它滿足：除以 3 余 2 并且 被 5 和 7 整除。
同理，
求得滿足：可被 3 和 7 整除 并且 除以 5 余 1 的最小正整數(shù) x? = 21，從而得到，同樣可被 3 和 7 整除 但 除以 5 余 3 的 3x? = 63；
求得滿足：可被 3 和 5 整除 并且 除以 7 余 1 的最小正整數(shù) x? = 15，從而得到，同樣可被 3 和 5 整除 但 除以 7 余 2 的 2x? = 30；
將上面的 結(jié)果 相加 得到： x’ = 2x? + 3x? + 2x? = 140 + 63 + 30 = 233，則 容易驗(yàn)證 x‘ 是 同余方程組 (1) 的一個解 ，但是 x’ 不是 最小整數(shù)解 x。很容易可以發(fā)現(xiàn) x' 減去 一個 同時 被 3、5 和 7 整除 并且 不大于 x' 的 整數(shù)，結(jié)果依然 是 (1) 的解，由于，同時 3、5 和 7 整除，就 意味著 被 3×5×7 = 105 整除，于是得出：
x = x' (mod 105)
進(jìn)而，有如下算法：
令 x = x'；
如果 x > 105（原文為 106 = x? + x? + x? ） 則 令 x = x - 105，否則 x 為 最終答案；
具體過程如下：
x = x' = 233
[x = 233 > 105]： x = x - 105 = 233 - 105 = 128
[x = 128 > 105]： x = x - 105 = 128 - 105 = 23
[ x = 23 < 105]：OK！
這樣就得到了最終答案：x = 23。
將整個求解過程寫成算式就是：
x = 2×70 + 3×21 + 2×15 - 2×(3×5×7) = 23
為了方便記憶，發(fā)明 珠算 和 卷尺 的明朝數(shù)學(xué)家 程大位，在其所著的 《算法統(tǒng)宗》 中，將 《孫子算經(jīng)》的算法編成 "孫子歌訣" 如下：
三人同行七十稀，
五樹梅花廿一枝，
七子團(tuán)圓正半月，
除百零五便得知。
注：正半月就是十五天，除是除去（減去）之意。
韓信點(diǎn)兵
韓信點(diǎn)兵 泛指 ”物不知數(shù)“ 此類 一次同余方程組 求解問題。南宋著名數(shù)學(xué)家 秦九韶 對 《孫子算經(jīng)》中的算法 進(jìn)行了深入研究，將其擴(kuò)展為『大衍總數(shù)術(shù)』，徹底解決了 韓信點(diǎn)兵問題，這就是 《初等數(shù)論》中的 中國剩余定理（也稱 孫子定理）：
設(shè) m?, m?, ..., m_n 是 兩兩互素 的 正整數(shù)，那么對于任意整數(shù) a?, a?, ..., a_n 組成的 一次同余方程組：
在同余意義下，必有唯一解：
其中：
驗(yàn)證：易知，
再結(jié)合 (3'')，由 (3') 可以推出：
這就說明 (3') 的確 是 (3) 的解。
注：這里只是給出了定理的驗(yàn)證，并沒有嚴(yán)格證明 同余意義下的唯一性。證明 中國剩余定理，有多種方法大家有興趣可以參考《初等數(shù)論》。
秦九韶 分別稱 M、M? 、 M??1 為 衍母、衍數(shù)、乘率，這里的關(guān)鍵是求 乘率 M??1 ，方法如下：
令， r 是 M? 除以 m? 的余數(shù)，即，
于是：
進(jìn)而：
然后，讓 m? 和 r 輾轉(zhuǎn)相除，得到：
到 r_k = 1 終止。如果 向下進(jìn)行一步就是：
前面再加上 (4) ，整個過程 就是 歐幾里得輾轉(zhuǎn)相除法，因此 r_k 為 M? 和 m? 的 最大公約數(shù)，而 m?, m?, ..., m_n 是 兩兩互素，于是有： r_k = (M?, m?) = 1 ，這樣就證明了 最后 總可以 終止于 1 的正確性。
接著，定義兩個數(shù)列：
有：
即，
假設(shè)，
則：
這樣歸納的證明了 (7) 成立。
當(dāng) k 為偶數(shù)時 有：
于是：
比較 (5) 得到：
當(dāng) k 為奇數(shù)時，則 k + 1 是偶數(shù)，這就要算到 (6) ，對 (6) 稍作變形：
于是，令，
并重新令：
則有：
這樣我們就將 輾轉(zhuǎn)相除 又延長了一步 到 k + 1，這時 k + 1 是偶數(shù)，則同理上面 情況 可得到：
因?yàn)榇怂惴ㄗ詈罂倳K止于 1，所以 被 秦九韶 稱為『大衍求一術(shù)』，前綴 “大衍” 來自于《易經(jīng) · 系辭》：“大衍之?dāng)?shù)五十，... ...”。
當(dāng)然，中國剩余定理 要求 m?, m?, ..., m_n 必須兩兩 互素，對于那些 不滿足這個條件的 一次同余方程組 可以轉(zhuǎn)換為 和 其 同解 的 滿足這個條件的 一次同余方程組。下面舉例說明：
有一筐鴨蛋，1個1個數(shù)，正好數(shù)完；2個2個數(shù)，還剩1個；3個3個數(shù)，正好數(shù)完；4個4個數(shù)，還剩1個；5個5個數(shù)，還剩1個；6個6個數(shù)，還剩3個；7個7個數(shù)，正好數(shù)完；8個8個數(shù)，還剩1個；9個9個數(shù)，正好數(shù)完。請問：框里最少有多少個鴨蛋？
按照題目所述，列同余方程組如下：
顯然 1, 2, 3, 4, 5, 6, 7, 8, 9 并不兩兩互素，因此需要簡化：
一個數(shù)字必然被 1 整除，因此 ① 沒有意義，刪除； 一個數(shù)字被 9 整除，必然會被 3 整除，因此 保留 ⑨ 刪除 ③；一個數(shù)字 被 8 除余 1，則可以表示為 8x + 1，進(jìn)而有 2(4x) + 1，4(2x) + 1，于是 x 一定 可以被 2 和 4 整除，因此 保留 ⑧ 刪除 ② 和 ④；目前已經(jīng)保證了 被 2 除 余 1，可表示為 2x + 1，也保持了 被 3 整除，于是有 3(2x + 1) = 6x + 1，這說明 目前已經(jīng)保持了 被 6 除 余 3，因此 ⑥ 可以被刪除；最后剩下 ⑤ 和 ⑦ 保留。得到：
則 (8') 和 (8) 等價。由于 5,7,9,8 兩兩互素，符合 中國剩余定理 要求，于是解：
◆M = m? m? m? m? = 5 × 7 × 8 × 9 = 2520
◆M? = 7 × 8 × 9 = 504
M? = q m? + r, 504 = 100 × 5 + 4 , c? = 1;
m? = q? r + r?, 5 = 1 × 4 + 1, c? = q? = 1; (r? = 1，下標(biāo) 1 是奇數(shù)，需要再算一步 )
r = q? r? + r?, 4 = 3 × 1 + 1, c? = q?c? + c? = 3 × 1 + 1 = 4；(得到結(jié)果)
M??1 = 4， M??1 M?a? = 4 × 504 × 1 = 2016；
◆ 由于 a? = 0 所以 M??1 M?a? = 0；
◆M? =5 × 7 × 9 = 315
M? = q m? + r, 315 = 39 × 8 + 3 , c? = 1;
m? = q? r + r?, 8 = 2 × 3 + 2, c? = q? = 2;
r = q? r? + r?, 3 = 1 × 2 + 1, c? = q?c? + c? = 1 × 2 + 1 = 3；(r? = 1，下標(biāo) 2 是偶數(shù)，得到結(jié)果)
M??1 = 3， M??1 M?a? = 3 × 315 × 1 = 945；
◆由于 a? = 0 所以 M??1 M?a? = 0；
得到：
x = M??1 M?a? + M??1 M?a? + M??1 M?a? = 2016 + 0 + 945 + 0 = 2961
x > M, x = x - M = 2961 - 2520 = 441
最終答案：框里最少有 441 個鴨蛋。
最后，需要說明的是：
數(shù)學(xué)大神歐拉和高斯 對于 一般一次同余式進(jìn)行了詳細(xì)研究，獨(dú)立的得到了 中國剩余定理，后來證實(shí) 與 秦九韶『大衍求一術(shù)』相同，于是才命名該定理為：中國剩余定理。
中國剩余定理，在《抽象代數(shù)》中還有另外的形式，不過這就扯遠(yuǎn)了，就此打住。
（由于本人數(shù)學(xué)水平有限，出錯在所難免，歡迎各位老師批評指正?。?/p>
2. 韓信點(diǎn)兵快速解法大全
相傳韓信才智過人，從不直接清點(diǎn)自己軍隊的人數(shù)，只要讓士兵先后以三人一排、五人一排、七人一排地變換隊形，而他每次只掠一眼隊伍的排尾就知道總?cè)藬?shù)了。
輸入3個非負(fù)整數(shù)a,b,c ，表示每種隊形排尾的人數(shù)（a<3,b<5,c<7），輸出總?cè)藬?shù)的最小值（或報告無解）。已知總?cè)藬?shù)不小于10，不超過100 。
3. 韓信點(diǎn)兵問題最適合用的方法
韓信點(diǎn)兵的數(shù)學(xué)解法
我國漢代有一位大將，名叫韓信。他每次集合部隊，都要求部下報三次數(shù)，第一次按1～3報數(shù)，第二次按1～5報數(shù)，第三次按1～7報數(shù)，每次報數(shù)后都要求最后一個人報告他報的數(shù)是幾，這樣韓信就知道一共到了多少人。他的這種巧妙算法，人們稱為“鬼谷算”、 “隔墻算”、“秦王暗點(diǎn)兵”等。
這種問題在《孫子算經(jīng)》中也有記載：“今有物不知其數(shù)：三三數(shù)之余二，五五數(shù)之余三，七七數(shù)之余二，問物幾何?” 它的意思就是，有一些物品，如果3個3個的數(shù)，最后剩2個；如果5個5個的數(shù)，最后剩3個；如果7個7個的數(shù)，最后剩2個；求這些物品一共有多少？人們通常把這個問題叫作“孫子問題”， 西方數(shù)學(xué)家把它稱為“中國剩余定理”?，F(xiàn)在，這個問題已成為世界數(shù)學(xué)史上著名的問題。
到了明代，數(shù)學(xué)家程大位把這個問題的算法編成了四句歌訣：
三人同行七十稀，五樹梅花廿一枝；
七子團(tuán)圓正半月，除百零五便得知。
用現(xiàn)在的話來說就是：一個數(shù)用3除，除得的余數(shù)乘70；用5除，除得的余數(shù)乘21；用7除，除得的余數(shù)乘15。最后把這些乘積加起來再減去105的倍數(shù)，就知道這個數(shù)是多少。
《孫子算經(jīng)》中這個問題的算法是：
70×2＋21×3＋15×2＝233
233－105－105＝23
所以這些物品最少有23個。
根據(jù)上面的算法，韓信點(diǎn)兵時，必須先知道部隊的大約人數(shù)，否則他也是無法準(zhǔn)確算出人數(shù)的。你知道這是怎么回事嗎？
這是因?yàn)椋?/p>
被5、7整除，而被3除余1的最小正整數(shù)是70；
被3、7整除，而被5除余1的最小正整數(shù)是21；
被3、5整除，而被7除余1的最小正整數(shù)是15。
所以，這三個數(shù)的和是15×2＋21×3＋70×2，必然具有被3除余2，被5除余3，被7除余2的性質(zhì)。
以上解法的道理在于：
被3、5整除，而被7除余1的最小正整數(shù)是15；
被3、7整除，而被5除余1的最小正整數(shù)是21；
被5、7整除，而被3除余1的最小正整數(shù)是70。
因此，被3、5整除，而被7除余2的最小正整數(shù)是 15×2＝30；
被3、7整除，而被5除余3的最小正整數(shù)是 21×3＝63；
被5、7整除，而被3除余2的最小正整數(shù)是 70×2＝140。
于是和數(shù)15×2＋21×3＋70×2，必具有被3除余2，被5除余3，被7除余2的性質(zhì)。但所得結(jié)果233（30＋63＋140＝233）不一定是滿足上述性質(zhì)的最小正整數(shù)，故從它中減去3、5、7的最小公倍數(shù)105的若干倍，直至差小于105為止，即 233－105－105＝23。所以23就是被3除余2，被5除余3，被7除余2的最小正整數(shù)。
4. 韓信點(diǎn)兵快速解法視頻
中國剩余定理
民間傳說著一則故事——“韓信點(diǎn)兵”。
秦朝末年，楚漢相爭。一次，韓信將1500名將士與楚王大將李鋒交戰(zhàn)?？鄳?zhàn)一場，楚軍不敵，敗退回營，漢軍也死傷四五百人，于是韓信整頓兵馬也返回大本營。當(dāng)行至一山坡，忽有后軍來報，說有楚軍騎兵追來。只見遠(yuǎn)方塵土飛揚(yáng)，殺聲震天。漢軍本來已十分疲憊，這時隊伍大嘩。韓信兵馬到坡頂，見來敵不足五百騎，便急速點(diǎn)兵迎敵。他命令士兵3人一排，結(jié)果多出2名；接著命令士兵5人一排，結(jié)果多出3名；他又命令士兵7人一排，結(jié)果又多出2名。韓信馬上向?qū)⑹總冃迹何臆娪?073名勇士，敵人不足五百，我們居高臨下，以眾擊寡，一定能打敗敵人。漢軍本來就信服自己的統(tǒng)帥，這一來更相信韓信是“神仙下凡”、“神機(jī)妙算”。于是士氣大振。一時間旌旗搖動，鼓聲喧天，漢軍步步進(jìn)逼，楚軍亂作一團(tuán)。交戰(zhàn)不久，楚軍大敗而逃。
首先我們先求5、9、13、17之最小公倍數(shù)9945（注：因?yàn)?、9、13、17為兩兩互質(zhì)的整數(shù)，故其最小公倍數(shù)為這些數(shù)的積），然后再加3，得9948（人）。
在一千多年前的《孫子算經(jīng)》中，有這樣一道算術(shù)題：
“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”按照今天的話來說：一個數(shù)除以3余2，除以5余3，除以7余2，求這個數(shù).
這樣的問題，也有人稱為“韓信點(diǎn)兵”.它形成了一類問題，也就是初等數(shù)論中解同余式.這類問題的有解條件和解的方法被稱為“中國剩余定理”，這是由中國人首先提出的.
① 有一個數(shù)，除以3余2，除以4余1，問這個數(shù)除以12余幾？
除以3余2的數(shù)有：
2， 5， 8， 11，14， 17， 20， 23….
它們除以12的余數(shù)是：
2，5，8，11，2，5，8，11，….
除以4余1的數(shù)有：
1， 5， 9， 13， 17， 21， 25， 29，….
它們除以12的余數(shù)是：
1， 5， 9， 1， 5， 9，….
一個數(shù)除以12的余數(shù)是唯一的.上面兩行余數(shù)中，只有5是共同的，因此這個數(shù)除以12的余數(shù)是5.
如果我們把①的問題改變一下，不求被12除的余數(shù)，而是求這個數(shù).很明顯，滿足條件的數(shù)是很多的，它是 5＋12×整數(shù)，
整數(shù)可以取0，1，2，…，無窮無盡.事實(shí)上，我們首先找出5后，注意到12是3與4的最小公倍數(shù)，再加上12的整數(shù)倍，就都是滿足條件的數(shù).這樣就是把“除以3余2，除以4余1”兩個條件合并成“除以12余5”一個條件.《孫子算經(jīng)》提出的問題有三個條件，我們可以先把兩個條件合并成一個.然后再與第三個條件合并，就可找到答案.
②一個數(shù)除以3余2，除以5余3，除以7余2，求符合條件的最小數(shù).
先列出除以3余2的數(shù)：
2， 5， 8， 11， 14， 17， 20， 23， 26，…，
再列出除以5余3的數(shù)：
3， 8， 13， 18， 23， 28，….
這兩列數(shù)中，首先出現(xiàn)的公共數(shù)是8.3與5的最小公倍數(shù)是15.兩個條件合并成一個就是8＋15×整數(shù)，列出這一串?dāng)?shù)是8， 23， 38，…，再列出除以7余2的數(shù) 2， 9， 16， 23， 30，…，
就得出符合題目條件的最小數(shù)是23.
事實(shí)上，我們已把題目中三個條件合并成一個：被105除余23.
那么韓信點(diǎn)的兵在1000-1500之間，應(yīng)該是105×10+23=1073人
中國有一本數(shù)學(xué)古書「孫子算經(jīng)」也有類似的問題：「今有物，不知其數(shù)，三三數(shù)之，剩二，五五數(shù)之，剩三，七七數(shù)之，剩二，問物幾何？」
答曰：「二十三」
術(shù)曰：「三三數(shù)之剩二，置一百四十，五五數(shù)之剩三，置六十三，七七數(shù)之剩二，置三十，并之，得二百三十三，以二百一十減之，即得。凡三三數(shù)之剩一，則置七十，五五數(shù)之剩一，則置二十一，七七數(shù)之剩一，則置十五，即得?！?/p>
孫子算經(jīng)的作者及確實(shí)著作年代均不可考，不過根據(jù)考證，著作年代不會在晉朝之后，以這個考證來說上面這種問題的解法，中國人發(fā)現(xiàn)得比西方早，所以這個問題的推廣及其解法，被稱為中國剩余定理。中國剩余定理（Chinese Remainder Theorem）在近代抽象代數(shù)學(xué)中占有一席非常重要的地位。
韓信被貶淮陰侯時高祖找他聊天 高祖說：韓信你說寡人我能帶多少兵。 韓信說：10萬絕對不能超過10萬。高祖又說：你呢。韓信說：韓信點(diǎn)兵 多多益善. 高祖說：那你不是比我還厲害嗎，那你為什么會被寡人抓到呢。韓信說：皇上您是將之將 我是兵之將 當(dāng)然不如陛下您
5. 韓信點(diǎn)兵5種解法
假設(shè)人數(shù)不超過10000人。首先我們先求5、9、13、17之最小公倍數(shù)9945（注：因?yàn)?、9、13、17為兩兩互質(zhì)的整數(shù)，故其最小公倍數(shù)為這些數(shù)的積），然后再加3，得9948（人）這個數(shù)就滿足要求。
強(qiáng)推
