韩信点兵问题的初等解法

[趣味数学] 韩信点兵民间故事《韩信点兵》：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的兴建立下了卓绝的功劳。

据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从1至5报数，也记下最后一个士兵所报之数；最后令士兵从1至7报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。

比如，已知军队人数大概在1000-1100左右，如果1-3报数余2人，1-5报数余3人，1-7报数余2人，则韩信立刻知道总人数1073人。

汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。

于是每次出战都士气大振，经常大获全胜。

把韩信点兵问题再换个更简单的说法，就是说，有个数除3余2，除5余3，除7余2，问你这个数字最小是几？也可以给定一个范围，问你是几。

这类问题，纠结应该怎么下手解决呢？对于这样的问题，要先观察，是否存在规律，如果符合一定的规律，则可以通过简单口诀来实现；如果没有规律，那么就要通过一些特殊方法处理。

一、有规律问题的解法重要口诀：和同加和，差同减差，余同取余，最小公倍加先来说说最后一句，最小公倍加，意思是，不管什么情况，先把最小公倍数求出来，这个是作为基础。

然后根据不同情况进行辨别，如何继续处理。

（一）和同加和意思是，如果不同被除数和余数的和相同，那么就把这个和，加到最小公倍数上。

例：一个数除5余3，除6余2，除7余1解题思路：5、6、7的最小公倍数是210，因为5＋3＝6＋2＝7＋1＝8，所以这个数最小就是8，其余满足条件的数字是210的倍数＋8，比如218、428……（二）差同减差意思是，如果不同被除数和余数的差相同，那么就把这个差，用最小公倍数减掉。

例：一个数除5余3，除6余4，除7余5解题思路：5、6、7的最小公倍数是210，因为5－3＝6－4＝7－5＝2，所以这个数最小就是：210－2＝208，其余满足条件的数字是210的倍数＋208，比如418、628……（三）余同取余这个是最简单的了，意思是，如果余数都相同，直接把余数加到最小公倍数上。

[兴趣数学] 韩信点兵民间故事《韩信点兵》：韩信是汉高祖刘邦手下的大将，他勇敢善战，智谋超群，为汉朝的兴成立下了卓越的功绩。

听说韩信的数学水平也特别高明，他在点兵的时候，为了保住军事机密，不让仇敌知道自己队伍的实力，先令士兵从 1 至3 报数，而后记下最后一个士兵所报之数；再令士兵从 1 至5 报数，也记下最后一个士兵所报之数；最后令士兵从 1 至7 报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己队伍士兵的总人数，而仇敌则一直没法弄清他的队伍终究有多少名士兵。

比方，已知军队人数大体在1000-1100 左右，假如1-3 报数余2 人，1-5 报数余 3 人，1-7 报数余 2 人，则韩信马上知道总人数1073 人。

汉军原来就服气自己的统帅，这一来更相信韩信是“仙人下凡”、“神机秒术”于。

是每次出战都士气大振，常常大获全胜。

把韩信点兵问题再换个更简单的说法，就是说，有个数除 3 余2，除 5 余3，除7 余2，问你这个数字最小是几？也可以给定一个范围，问你是几。

这种问题，纠结应当怎么下手解决呢？关于这样的问题，要先察看，能否存在规律，假如切合必定的规律，则能够经过简单口诀来实现；假如没有规律，那么就要经过一些特别方法办理。

一、有规律问题的解法重要口诀：和同加和，差同减差，余同取余，最小公倍加先来谈谈最后一句，最小公倍加，意思是，不论什么状况，先把最小公倍数求出来，这个是作为基础。

而后依据不一样情况进行鉴别，怎样持续办理。

（一）和同加和意思是，假如不一样被除数和余数的和相同，那么就把这个和，加到最小公倍数上。

例：一个数除 5 余3，除 6 余2，除7 余1解题思路：5、6、7 的最小公倍数是210 ，因为5＋3＝6＋2 ＝7＋1＝8，因此这个数最小就是8，其他知足条件的数字是210 的倍数＋8，比方218 、428⋯⋯（二）差同减差意思是，假如不一样被除数和余数的差相同，那么就把这个差，用最小公倍数减掉。

韩信点兵解法韩信点兵是一个有趣的猜数游戏。

如果你随便拿一把蚕豆（数目约在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年代被解决了，这是近代数学的五个重大成就。

穷举法—韩信点兵1. 问题描述：韩信点兵。

韩信有⼀队兵，他想知道有多少⼈，便让⼠兵排队报数。

按从1⾄ 5报数，最末⼀个⼠兵报的数为1；按从1⾄6报数，最末⼀个⼠兵报的数为5；按从 1⾄ 7报数，最末⼀个⼠兵报的数为 4；按从 1⾄ 11报数，最末⼀个⼠兵报的数为 10。

你知道韩信⾄少有多少兵吗？2、【算法思想】设兵数为x，则按题意x应满⾜下述关系式：x%5 ==1 && x%6==5 &&x %7==4 && x%11==10采⽤穷举法对x从 1开始试验，可得到韩信⾄少有多少兵。

3、代码实战：穷举法，设置标志find#include<stdio.h>#include "stdlib.h"int main( ){int x =1;int find = 0; /*设置找到标志为假*/while (!find){if (x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10){find = 1;}x++;printf(" x = %d\n", x);}system("pause"); /*解决快闪问题*/}运⾏结果：（运⾏结果是从1—找到的最⼩数）4、其他代码：goto1 #include<stdio.h>2 #include "stdlib.h"3int main( )4 {5int x ;6for(x=1; ;x++)7 {8if(x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10 ) 9 { printf("最⼩值是x= %d\n ",x);10goto end;11 }12 }13 end:;14 system("pause");15 }break语句执⾏代码1 #include<stdio.h>2 #include "stdlib.h"3int main( )4 {5int x ;6for(x=1; ;x++)7 {8if(x % 5 == 1 && x % 6 == 5 && x % 7 == 4 && x % 11 == 10 ) 9 { printf("最⼩值是x= %d\n ",x);10break;11 }12 }1314 system("pause");15 }结果相同，不再赘述。

【2017年整理】韩信点兵问题的初等解法“韩信点兵”问题的初等解法研究王晓东河北省卢龙县燕河营镇中学 066407韩信，是我国汉代刘邦手下的一员能征善战，智勇双全的大将。

历史上流传着一个关于他运用奇特方法点兵的传说。

有一天，韩信来到操练场，检阅士兵操练。

他问部将，今天有多少士兵操练，部将回答:“大约两千三百人。

”韩信走上点兵台，他先命全体士兵排成7路纵队，问最后一排剩几人，部将说，剩2人;他又命全体士兵排成5路纵队，问最后一排剩几人，部将说，剩3人;最后，他又让全体士兵排成3路纵队，问最后一排剩几人，部将说，剩2人。

韩信告诉部将，今天参加操练的士兵有2333人。

从现代数学的观点来看，解决韩信点兵问题，可以这样思考:设操练士兵的总数为M，则M=3x+2=5y+3=7z+2其中，x，y，z分别表示排成3路纵队，5路纵队，7路纵队的纵队数目。

求出了x，y，z以后，M也求求出来了。

而求x，y，z可以看成求方程组3x+2=5y+33x+2=7z+2的正整数解。

在上面的方程组中，未知数的个数多于方程的个数，则把这种方程(组)叫做不定方程(组)。

不定方程(组)的解是不确定的，一般不定方程总有无穷多个组解，但若加上整数(或正整数)解的特定限制，则不定方程(组)的解有三种可能:有无限组解，有限组解，或无解。

我国古代人民对于不定方程(组)这类问题解法的探讨有着悠久的历史，在中国古代的《孙子算经》中曾作为一个典型问题进行论述。

其中的一个经典例题是:今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物有几何,答曰:二十三。

术曰:三三数之剩二，则置一百四十;五五数之剩三，则置六十三;七七数之剩二，则置三十;并之得二百三十三，以二百一十减之，即得。

凡三三数之剩一，则置七十;五五数之剩一，则置二十一;七七数之剩一，则置十五。

一百(零)六以上，以一百(零)五减之，即得。

在中国民间还广为流传着一个口诀:三人同行七十稀，五树梅花二十一。

韩信点兵数学竞赛题中国剩余定理中国古代将领韩信是我国历史上著名的军事家，在战争中常常运用智谋胜敌。

他点兵数学竞赛题是一道以韩信命名的数学竞赛题，这个问题是一个典型的中国剩余定理的问题。

下面我们来详细解答这个问题。

1. 问题描述韩信点兵数学竞赛题描述：韩信带兵攻打赵国，他手下共有兵士三万人，分为三个团队。

第一天，第一队出兵了，但是他们出发之前被派去买饭了。

第二队出发了，但是他们也遇到了意外，少了一半人。

第三队没有遇到什么问题，全军出发。

结果三队同时到达目的地，没有人掉队。

问：韩信至少有多少兵？2. 分析这个问题的解决方法是使用中国剩余定理。

我们先将题目翻译成数学语言：设韩信的军队共有x人，第一队共有a人，第二队共有b 人，第三队共有c人。

已知：- x≡a(mod m1)- x≡b(mod m2)- x≡c(mod m3)其中，m1，m2和m3是三个正整数，说明模数不一样，我们需要使用中国剩余定理来解决。

3. 解决方法韩信点兵数学竞赛题的解决方法是使用中国剩余定理，步骤如下：1. 求出模数m1，m2和m3的最小公倍数M，即M=lcm(m1, m2, m3)。

2. 求出t1，t2和t3，使得M/m1=t1，M/m2=t2和M/m3=t3，即t1，t2和t3是M/m1，M/m2和M/m3的商数。

3. 分别求出M/m1，M/m2和M/m3关于m1，m2和m3的逆元r1，r2和r3，即r1*(M/m1)≡1(mod m1)，r2*(M/m2)≡1(mod m2)和r3*(M/m3)≡1(mod m3)。

4. 按照以下公式求解x：x≡a*t1*r1+b*t2*r2+c*t3*r3(mod M)4. 求解过程下面我们逐步求解韩信点兵数学竞赛题，求解过程如下：1. 求出模数m1，m2和m3的最小公倍数M，即M=lcm(3, 2, 1)=6。

2. 求出t1，t2和t3，使得M/m1=t1，M/m2=t2和M/m3=t3，即t1，t2和t3是2，3和6。

韩信点兵问题的神解法定理1：一个数除以a余数x，除以b余数y，a、b互质且a<b，求这个数的最小值。

设这个数为z，则z=b(an+x-y)/(b-a)+y (1)或z=a(bn+x-y)/(b-a)+x (2)其中n为使(bn+x-y)/(b-a)为正整数的最小值。

证明：设z=al+x=bm+y 则：al+x-y-am=(b-a)m所以m=(a(l-m)+x-y)/(b-a)将变量l-m用独立变量n代替：m= (an+x-y)/(b-a)将m代入以上等式得到：z=b(an+x-y)/(b-a)+y同理可以证明等式2定理2：在定理1等式中，0<=n<=b-a。

证明：从定理1等式中可知n=l-m，因为a<b，所以l>=m，故n>=0假设n=h(b-a)+k，k<=b-a 代入以上算式z=b(ah(b-a)+ak+x-y)/(b-a)+y=ahb+b(ak+x-y)/(b-a)，由此可知，n可以取值为k。

根据以上两个定理来计算韩信点兵问题，具有两个方面的优点：1、将两个变量合并成了一个变量，从而只需要尝试一个变量即可。

2、这一个变量的范围被两个除数的值界定，需要尝试的最多次数是确定的。

例1：一个数除以9余5，除以13余4，求这个数的最小值列出算式：13*(9n+5-4)/(13-9)+4=13*(9n+1)/4+4显然能让相除结果为整数的n的最小值为3，代入则得：13*(9*3+1)/4+4=95。

例2：一个数除以13余10，除以17余5，求这个数的最小值列出算式：17*(13n+10-5)/(17-13)+5=17*(13n+5)/4+5显然能让相除结果为整数的n的最小值也为3，代入则得：17*(13*3+5)/4+5=192以上算法比传统算法更简便，但依然有缺陷，即如果除数的值比较大时，要获得满足条件的n的值尝试的次数也会相应增大，从而对于大数相除时也会计算量太大，无法手算，用计算机计算也会比较耗时。

－韩信点兵问题汉朝大将韩信善于用兵。

据说韩信每当部队集合，他只要求部下士兵作1~3、1~5、1~7报数后，报告一下特各次的余数，便可知道出操公倍数和缺额。

这个问题及其解法，大世界数学史上颇负盛名，中外数学家都称之为“孙子定理”或“中国剩余定理”。

这类问题的解题依据是：1、如果被除数增加(或减少)除数的若干倍，除数不变，那么余数不变。

例如：20÷3=6 (2)(20-3×5)÷3=21 (2)(20+3×15)÷3=1 (2)2、如果被除数扩大(缩小)若干倍，除数不变，那么余数也扩大(缩小)同样的倍数。

例如：20÷9=2 (2)(20×3)÷9=6 (6)(20÷2)÷9=1 (1)例1、一个数除以3余2，除以5余3，除以7余2。

求适合这些条件的最小的数。

1、求出能被5和7整除，而被3除余1的数，并把这个数乘以2。

70×2=1402、求出能被3和7整除，而被5除余1的数，并把这个数乘以3。

21×3=633、求出能被5和3整除，而被7除余1的数，并把这个数乘以2。

15×2=304、求得上面三个数的和140+63+30=2335、求3、57的最小公倍数［3、5、7］=1056、如果和大于最小公倍数，要从和里减去最小公倍数的若干倍233–105×2=23例2、一个数除以3余2，除以5余2，除以7余4，求适合这些条件的最小的数。

解法一：70×2+21×2+15×4=242［3、5、7］=105242–105×2=32解法二、35+21×2+15×4=137［3、5、7］=105137–105=32例3、一个数除以5余3，除以6余4，除以7余1，求适合这些条件的最小的数。

1、因为［6、7］=42，而42÷5余2，根据第二个依据，42×4÷5应余8(2×4)，实际余3，所以取42×4=1682、因为［7、5］=35，而35÷6余5，则取35×2=703、［5、6］=30,30÷7余2，则取30×4=1204、［5、6、7、］=2105、 168+70+120–210=148例4、我国古代算书上有一道韩信点兵的算题：卫兵一队列成五行纵队，末行一人；列成六行纵队末行五人；列成七行纵队，末行四人；列成十一行纵队，末行十人。