​韩信点兵算法原理是什么（韩信点兵算法解析）

韩信点兵算法原理是什么（韩信点兵算法解析）

韩信是中国古代一位有名的军事家，民间流传着许多他的故事，韩信点兵便是其中之一。

秦朝末年的时候，战火四起，楚汉相争。在一次战斗中，韩信率1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，于是，韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗，韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。

他命令士兵3人排成一排整队，结果多出2名：接着韩信又命令士兵5人排成一排整队，结果

多出3名：他又命令上兵7人排成一排整队，结果又多出2名。于是韩信马上说道：“ 我军有1073名见弟，追兵不过区区500人，我们一定能够打败敌人。”

韩信是如何快速计算士兵人数的呢？

其实在一千多年前的《孙子算经》中，就有这道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

明代数学家程大位还用诗歌概括了这一算法，他写道：

三人同行七十稀，五树梅花廿一枝，

七子团圆月正半，除百零五便得知。

按照今天的话来说：一个数除以3余2，除以5余3，除以7余2，求这个数。这样的问题，有人称为“韩信点兵”，也叫“中国剩余定理”。

那我们现在来解这道题：

第1步：先列出满足其中一个条件的数（一般从小到大），即除以3余2的数：2， 5， 8， 11， 14， 17， 20， 23， 26，…； 第2步：再列出满足其中第二个条件的数，即除以5余3的数：3， 8， 13， 18， 23， 28，….； 第3步：归纳前面第3步首先出现的公共数是8.8就是满足除以3余2，除以5余3的最小的那个数。3与5的最小公倍数是15.两个条件合并成一个就是8＋15×n(n=0，1，2，…)。列出这一串数是8， 23， 38，…；第4步：再列出满足其中第三个条件的数，即除以7余2的数 2， 9， 16， 23， 30，…；第5步：归纳第3步第4步得到的数列。就得出符合题目条件的最小数是23；事实上，我们已把题目中 三个条件合并成一个。3，5，7的最小公倍数是 105 ，满足三个条件的所有数是23+105×n(n=0，1，2，…)； 第6步：那么韩信点的兵在1000-1100之间，应该是23+105×10=1073人。

如果你随便拿一把蚕豆（数目约在100粒以内），假如3粒一数余1粒，5粒一数余2粒，7粒一数余2粒，那么，原有蚕豆有多少粒呢？

中国剩余定理（韩信点兵）的计算方法是：

第1步：用3个一数剩下的余数，将它乘以70（因为70既是5与7的倍数，又是以3去除余1的数）； 第2步：用5个一数剩下的余数，将它乘以21（因为21既是3与7的倍数，又是以5去除余1的数）； 第3步：7个一数剩下的余数，将乘以15（因为15既是3与5的倍数，又是以7去除余1的数）； 第4步：将这些数加起来，若超过105（105是3,5,7的最小公倍数），就减掉105，如果剩下来的数目还是比105大，就再减去105，直到得数比105小为止。这样，所得的数就是原来的数了。根据这个道理，你可以很容易地把前面的题目列成算式： 1×70＋2×21＋2×15－105 ＝142－105 ＝37。因此，可以知道，原来这一堆蚕豆有37粒。