韩信点兵算法原理是什么(韩信点兵算法解析)

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

秦朝末年的时候,战火四起,楚汉相争。在一次战斗中,韩信率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粒。

(0)
上一篇 2022年3月29日
下一篇 2022年3月29日

相关推荐