这个博客已经过去了很久……

不过,你可以通过以下方式找到我

现在的位置: 首页 > 谈前端 > JavaScript > 正文
韩信点兵算法
2013年10月22日 JavaScript ⁄ 共 1640字 等你评论

韩信点兵是一个有趣的猜数游戏。如果你随便拿一把蚕豆(数目约在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年代被解决了,这是近代数学的五个重大成就。据证明人说,在解决问题的过程中,他是受到了“中国剩余定理”的启发的。

接下来,韩信开始点兵了,要 程序猿 编程解答:

话说有一次韩信带兵,人数在百人左右,然后它就那些士兵排队,3个人一行排的时候多了一个人,7个人一列排的时候少2个人,5个人排的时候刚刚好。

 

刚开始碰到到这道题的时候,不过后来突然想到了一个函数,问题就比较好解决了。

 

在解决这个问题之前,请大家看一个方法:Math.DivRem()

 

DivRem(int a,int b,int out result):它的意思是说,输入2个整数,然后输出它们的余数。

 

这里有out关键字:C# 参考之方法参数关键字:params、ref及out 如果有兴趣的话,可以学习学习。

 

到这里,想到了那个方法,韩信点兵的算法的根源就是余数问题:

  1. static int HanXinAlgorithm()  
  2.         {  
  3.             int num1 = 0;  
  4.             int num2 = 0;  
  5.             int num3 = 0;  
  6.             int result = 0;  
  7.             for (int i = 0; i < 100; i++)  
  8.             {  
  9.                 Math.DivRem(i, 3, out num1);  
  10.                 Math.DivRem(i, 5, out num2);  
  11.                 Math.DivRem(i, 7, out num3);  
  12.                 if (num1 == 1 && num2 == 0 && num3 == 5)  
  13.                     result = i;  
  14.             }  
  15.             return result;  
  16.         }  

得到的结果就是: 额…… 自己算吧

友荐云推荐
×