12韩信点兵

12韩信点兵 12(韩信点兵 民间传说着一则故事——“韩信点兵”。 秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名;接着命令士兵5人一排，结果多出3名;他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布:我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步进逼，楚军乱作一团。交战不久，楚军大败而逃。 韩信是如何凭借交换队列的方式及三个余数，快速算出了士兵的总数的呢, 其实，韩信根本不是什么“神仙下凡”，也不是有什么“神机妙算”的法术。他算得快，算得准，是因为他掌握了这一类问的求解与技巧。 这类问题就是著名的“孙子算经”和“中国剩余定理”所解决的问题。 我国古代数学名著《孙子算经》中，提出了闻名于世的“物不知数”问题。原文是: “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何,” 中还给出了其解法。韩信就是根据这个问题的解法推算出将士的准确数字的。 下面我们来研究这个问题的解法。 (?)“笨”算法 原来的问题题意是:求一数，三除余二，五除余三，七除余二。这问题太容易回答了:因为以3除余2，以7除余2的数，以21除也余2，而23是以3，7除余2的最小数， 它刚好又是以5除余3的数。所以心算快的人很快就能算出。 我们再来解决另一个问题吧～ “三除余二，五除余三，七除余四，求原数”。 下面先介绍解决这一问题的“笨”算法: 在算盘上先打上(或纸上写上)2，每次加3，加到以5除余 3的时候暂停下来，再在这个数上每次加15，到得出以7除余4的数的时候，就是答数。具体地说:从2加3，再加3得，即 2，2，3=5， 5，3=8( 它是以5除余3的最小数，然后在8上加15，再加15，第三次加15，得53，即 8，8，15=23，23，15=38，38，15=53( 经过验算，53用3除余2，5除余3，7除余4，所以53就是符合要求的最小数。 这个方法的道理是什么呢,很简单:先从以3除余2的数中去找以5除余3的数，再从“3除余2，5除余3”的数中去找7除余4的数，如此而已。这方法虽然拙笨些，但这是一个步步能行的方法，是一个值得推荐的、朴素的方法。 上述问题的解答，不但53有此性质，而53，105=158，158，105=263都有此性质，因此，问题的确切提法应当是:求出三除余二，五除余三，七除余四的最小的正整数。 我们再介绍一个麻烦得多的问题。原文如下: “今有数不知总。以五累减之无剩，以七百十五累减之剩十，以二百四十七累减之剩一百四十，以三百九十一累减之剩二百四十五，以一百八十七累减之剩一百零九。问总数若干。” 看来问题比较麻烦，但通过细心观察，有窍门可找。你看:第一句“以五累减之无剩”其实是多余的，因为这个数以715除余10必定是5的倍数。第三句话“以247累减之剩140”，就是说此数减去247的若干倍后还余140，140是5的倍数，此数也是5的倍数，那么减去的247的倍数也应是5的倍数。因此这句话可改为“以247×5=1235累减之剩140”。同样第四句话也可改为“以391×5=1955累减之剩245”。 现在我们可以完全仿照前面的方法进行计算，从245逐次加1955，直至得到的数用1235除余数为140止。计算 过程如下: 逐次加1955 245，2200，4155，6110，8065，10020(用1235去除的余数965，450，1170，655，140( 最后得到10020满足这两项要求。经检验10020的确符合全部条件，它就是我们要求的数。 下面再看一个古算题。 “二数余一，五数余二，七数余三，九数余四，问本数。” 首句与末句条件合起来是“18除余13”，再由 13，13，18=31，31，18=49，49，18=67， 67是五除余2的数，再由 67，67，5×18=67，90=157( 经检验，157符合全部条件:以2除余1，以5除余2，以7除余3，以9除余4，所以157就是解答了。 (?)古代的口诀解法 程大位著的《算法统宗》，对“物不知其数”的问题(见P(44第6行)的解答方法用下面的口诀标出: “三人同行七十稀，五树梅花廿一枝， 七子团圆正半月，除百零五便得知。” 它的意义是: 以70乘用3除的余数2，21乘用5除的余数3，15乘用7除的余数2，然后总加起来。如果它大于105，则减105，若仍大再减，„„最后得出来的正整数就是答数了。 它的形式是: 2×70，3×21，2×15=233， 两次减去105，得23，这就是答数了。 为什么70，21，15有此妙用,这70，21，15是怎样求出来的, 先看70，21，15的性质:70是这样一个数:用3除余1，5与7都除得尽的数，所以70a是一个用3除余a而5与7除都除得尽的数。21是用5除余1，3与7除得尽的数，所以21b是用5除余b，而3与7除得尽的数。同理，15c是用7除余c而3与5除得尽的数。总起来: 70a，21b，15c 是一个3除余a，5除余b，7除余c的数，也就是可能的解答之一，但可能不是最小的。这数加减105后都仍然有同样的性质，所以可以多次减去105而得出解答来。 在程大位的口诀里，前三句的意义是点出3，5，7与70，15，21的关系，后一句说明为了寻求最小正整数解还须减105，或再减105等。 这个方法是很好的。但是如何找出这70，21，15三个数呢,可用凑的方法: 在算盘上先打上35，它不是用3除余1，再加上35，得70，它是用3除余1了。其它可仿此求出。 现在我们可以来揭示“韩信点兵”的秘密了: 我们容易看出:韩信在点兵布阵时，士兵3人一排多出2人，就是士兵的总数被3除余2;5人一排多出3名，就是士兵数被5除余3;7人一排多出2名，就是士兵数被7除余2( 3，5，7的最小公倍数是105，所以105，105×2，105×3，„，105×10等等，都能被 3，5，7整除。而韩信根据“物不知其数问题”知道满足条件“被3除余2，被5除余3，被7除余2”的最小正整数23，并且他还知道自己的兵力略多于1000人，于是就迅速地算出了确切的士兵数: 105×10，23=1073(人)( 现在再将口诀解法推广一下。先回顾口诀: “三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知”。用现代术语翻译，其口诀实际上是: N=70r，21r，15r-105p， 123 其中r(i=1，2，3)分别是余数，p是使N,0的任一整数。 i 以上方法可以概括成更普遍的式子: 若某数N分别被称为定母的d，d，d，„，d除得的123n余数为r，r，r，„，r，则 123n N=kr，kr，kr，„，kr-pq， 112233nn 其中k是d，d，d，„，d的公倍数，且被d除余1;k1234n12是d，d，d，„，d的公倍数，且被d 除余1;„k是d，134n2n1 d，d，„，d的公倍数，且被d除余1(p是任意整数，23n-1n 是d，d，d，„，d的最小公倍数。 q123n 上式实际上是一条定理，而其关键又在于“求一”，即求“一个数的多少倍除以另一数，所得余数为1”的方法，也即求出公式中的“k”( i 这个方法的研究，是由我国宋代著名数学家秦九韶(约1202,1261)在其名著《数书九章》一书中完满解决的。他把它称作“大衍求一术”。类似的理论成果，在欧洲直到18，19世纪才由著名数学家欧拉和高斯获得，最早出现 年出版的《算术研究》一书里。而这，已是秦在高斯1801 九韶之后500多年的事了。因而，上述成果被称为“中国剩余定理”，或“孙子定理”。 现在，让我们也来当一回韩信吧～假如让士兵1至5报数，1至7报数，1至9报数，值日军官告诉我们余数分别是3，2，2(算一算士兵有多少。 显然，问题的提法与“韩信点兵”的传说中变换队列的方法是一致的。它的定母为d=5，d=7，d=9，余数为123 r=3，r=2，r=2(因为k是7与9的公倍数且以5除余1的数，1231 经计算知k=126，类似地知，k=225，k=280，q=315(取123 p=4，则 N=kr，kr，kr-pq 112233 =126×3，225×2，280×2-4×315=128( N,128，只不过是个符合条件的最小的数。假若要学“韩信将兵，多多益善”的话，我们可以在“128×n”(n为自然数)中任意取值。