《韩信点兵(胡)》由会员分享，可在线阅读，更多相关《韩信点兵(胡)（44页珍藏版）》请在金锄头文库上搜索。
1、第三模块重点学习内容韩信点兵与中国剩余定理1u韩信是中国古代一位有名的大元帅。他少年时 就父母双亡，生活困难，曾靠乞讨为生，还经常 受到某些泼皮的欺凌，胯下之辱讲的就是韩信少 年时被泼皮强迫从胯下钻过的事。u后来他投奔刘邦，展现了他杰出的军事才能， 为刘邦打败了楚霸王项羽立下汗马功劳，开创了 刘汉皇朝四百年的基业。u民间流传着一些以韩信为主角的有关聪明人的 故事，韩信点兵的故事就是其中的一个。一、“韩信点兵”的故事与孙子算经中的题目2相传有一次，韩信将1500名将士与楚王大将李锋 交战。双方大战一场，楚军不敌，败退回营。而汉军也有 伤亡，只是一时还不知伤亡多少。于是，韩信整顿兵马也 返回大本营
2、，准备清点人数。当行至一山坡时，忽有后军 来报，说有楚军骑兵追来。韩信驰上高坡观看，只见远方 尘土飞扬，杀声震天。汉军本来已经十分疲惫了，这时不 由得人心大乱。韩信仔细地观看敌方，发现来敌不足五百 骑，便急速点兵迎敌。不一会儿，值日副官报告，共有 1035人。他还不放心，决定自己亲自算一下。 1.“韩信点兵”的故事3韩信阅兵时，让一队士兵5人一行排队从他面前走 过，他记下最后一行士兵的人数（1人）；再让这队士兵6 人一行排队从他面前走过，他记下最后一行士兵的人数（5 人）；再让这队士兵7人一行排队从他面前走过，他记下最 后一行士兵的人数（4人），再让这队士兵11人一行排队从 他面前走过，他记下
3、最后一行士兵的人数（10人）。然后 韩信就凭这些数，可以求得这队士兵的总人数。思考题：这里面有什么秘密呢？韩信好像非常重视作 除法时的余数。 “数的除法运算以及余数”是小学数学的 内容。现在，每个学生都具有这样的基础，但能否会运用 就有差别了，你能够分析它吗？4约成书于四、五世纪，作者生平和编写年代都不清楚 。现在传本的孙子算经共三卷。卷上叙述算筹记数的 纵横相间制度和筹算乘除法则，卷中举例说明筹算分数算 法和筹算开平方法。卷下第31题，可谓是后世“鸡兔同笼 ”题的始祖，后来传到日本，变成“鹤龟算”。2.孙子算经书中是这样叙述的：“今有鸡兔 同笼，上有三十五头，下有九十四足 ，问鸡兔各几何？这
4、四句话的意思是 ：有若干只鸡兔同在一个笼子里，从 上面数，有35个头；从下面数，有94 只脚。求笼中各有几只鸡和兔？孙子算经5我国古代数学名著孙子算经中有“物不知数 ”的题目：今有物不知其数，三三数之剩2，五五数之剩3，七七数之剩2，问物几何？孙子算经中的题目这里面又有什么秘密呢？题目给出的条件，也仅仅是 作除法时的余数。6问题：今有物不知其数，二二数之剩1，三三数之剩2， 四四数之剩3，五五数之剩4，六六数之剩5，七七数之 剩6，八八数之剩7，九九数之剩8，问物几何？二、问题的解答1先从另一个问题入手思考：此问题是否比原问题简单些吗？7再从中挑“用5除余4”的数，一直筛选下去，舍得下功夫，就
5、一定可得结果。并 且看起来，解，还不是唯一的；可能有无穷多个解。1,3,5,7,9,11,13,15,17,19,21,23,（用2除余1 ） 5,11,17,23, （用3除余2 ） 11,23, （用4除余3 ）1）筛法思考一下：解题的思路是什么？8当问题中有很多类似的条件时，我们先只看其中两 三个条件，这就是化繁为简。一个复杂的问题，如果在简化时仍然保留了原来问 题的特点和本质，那么简化就“不失一般性”。学会“简化问题”与学会“推广问题”一样，是一 种重要的数学能力。化繁为简的思想寻找规律的思想把我们的解题方法总结为筛法，是重要的进步，是质 的飞跃找到规律了。筛法是一般性方法，还可以用来
6、解决其他类似的问题 。 9 化繁为简我们还是先看只有前两个条件的简化题目。1,3,5,7,9,11,13,15,17,19,21,23,25,（用2除余1）5,11,17,23, （用3除余2）上述筛选过程的第一步，得到:1,3,5,7,9,11,13,15,17,19,21,23,25,其实是列出了“用2除余1”的数组成的数列。这个数列实际上是用带余除法的式子得到的。2)公倍数法10对任意给定被除数a，不为零的除数b，必唯一存 在商q和余数r，使所谓“带余除法”，是指整数的如下 “除法”：当余数r =0时，则 a=bq，称为 “a被b整除”，或“b整除a”，这是通常除法“ ” 的另一种表达形
7、式。所以，带余除法是通常除法的推广。11就是“带余除法”的式子.当取 时，用上式求得的x正好组成上述数列 1,3,5,7,9,11,13,15,17,19,21,23,25, 设这样的数为x，则 。这里x是被除数，2是除数， 是商，1是余数，且 。回到求“用2除余1的数”的问题。12接着从中筛选出“用3除余2”的数，就是挑出符合下面“带余除法”表达式的数，这里 可取0，1，2，3，4， 再继续做下去如果我们不分上面两步，而是一上来就综合考虑两者，则就是要解联立方程组13那么，为了解这个方程组，除了刚才的筛法外，还有 没有更加巧妙的解法？ 我们考察上边两个方程的特点，发现，两个“带余除法 ”的式
8、子，都是“余数比除数少1”。于是想到，如果把被除数再加1，不是余数就为0了吗？ 换句话说，不是就出现整除的情况了吗？于是把上边每个方程两边都加上1，成为14这说明， x+1既是2的倍数，又是3的倍数，因此，它 是2与3的公倍数。由此想到对整个问题寻找规律。再看问题： 今有物不知其数，二二数之剩1，三三数之剩2，四四数之剩3，五五数之剩4，六六数之剩5，七七数之剩6，八八数之剩7，九九数之剩8，问物几何？对整个问题寻找规律15寻找规律设问题中,需要求的数是x,则被2,3,4,5,6,7,8,9去除，所得的余数都是比除数少1，于是我们把被除数x再加1,则 x+1就可被2,3,4,5,6,7,8,9
9、均整除.也就是说，x+1是2,3,4,5,6,7,8,9的公倍数，从而是其最小公倍数 2,3,4,5,6,7,8,9的倍数。即 这就是原问题的全部解，有无穷多个解，其中第一个解是2519；我们只取正数解，因为“物体的个数”总是正整数 。16思考题：求“用2除余1,3除余2,用m除余m-1”的数。求“用a除余a-1,用b除余b-1,用c除余c-1”的数.（a,b,c是任意大于1的自然数） 求“用2,3,4,5,6,7,8,9除都余1”的数。 求“用5,7,11 除都余2”的数。172.孙子算经中“有物不知其数” 问题的 解答 问题：今有物不知其数，三三数之剩2，五五数之剩3，七七数之剩2，问物几
10、何？181）筛法:2,5，8，11，14，17，20，23，26，29，（用3除余2）8，23， （用5除余3）23， （用7除余2）由此得到，23是最小的一个解。至于下一个解是什么，要把“”写出来才知道；实践以后发现，是要费一点儿功夫的。192）公倍数法现在仿照上边用过的“公倍数法”，设要求的数为x ，则依题意，得联立方程组按上一问题中“公倍数法”解决问题的思路：把方程两边同时加上或减去一个什么样的数，就能使三个等式的右边分别是3，5，7的倍数，从而等式左边就是3，5，7的公倍数了。20一种试算的方法从第三个等式入手，两边加5（或减2）则得这要通过反复的试算去完成。21则右边是7的倍数了，但
11、两边加5（或减2）并不能使前两式的右边分别是3的倍数和5的倍数，所以两边加5（或减2）并不能使右边成为3，5，7的公倍数。再继续从第三个等式入手，为使第三个等式右边仍然保持是7的倍数，可再加7l（或再减7l），（或 ）最后发现，为达到目的（三个等式的右边分别是3,5,7的倍数）,最小的加数是82(l=11时,5+7l=82）（或最 小的减数是23，即h=3,2+7h=23）。将 代入试算、分析，22多了一个“ ” ，因这时x也是正数，合要求 。用等式两边加82来求解，有用等式两边减23来求解，有23这两组解是一样的，都是“23，23+105，23+2105，”。原因是82+23=105，故令
12、第一组解就成为 便转化成第二组解。但是，这82和23来之不易；并且如果题目中的余数变了，就得重新试算，所以这方法缺少一般性，为使它具 有一般性，要做根本的修改。243）单因子构件凑成法我们先对前几页（*）式作两个方面的简化:一方面是每 次只考虑“一个除式”有余数的情况(即另两个除式都是整 除的情况):另一方面是把余数都简化为最简单的1。这样得 到三组方程。25（1）式意味着,在5和7的公倍数中（35,70,105, ）寻找被3除余1的数；（2）式意味着,在3和7的公倍数中（21,42,63,）寻找被5除余1的数；（3）式意味着,在3和5的公倍数中（15,30,45，）寻找被7除余1的数。对（1
13、）式而言，这个数可以取70，对（2）式而言，这个数可以取21，对（3）式而言，这个数可以取15。26于是（1）式两边同减70变为这样：第二式右边仍是5的倍数，第三式右边仍是7的倍数，而第一式右边因为减的70是“用3除余1”的数，正好原来也多一个1，减没了。第一式右边也成为了倍数，是3的倍数。 27（2）式两边同减21变为（3）式两边同减15变为28现在重复一下：所得的x是被3除余1，被5和7除余0的数；y是被5除余1，被3和7除余0的数；z是被7除余1，被3和5除余0的数。于是得到那么，凑出s =2x+3y+2z , s不就是我们需要求的数吗？ 29因为用3去除s时，除y及除z均余0 , 除3
14、y及除2z均余0 ，又除x余1 ,除2x余2，用3除s时余2。用5去除s时，除x及除z均余0, 除2x及除2z均余0， 又除y余1 除3y余3，用5除s时余3。用7去除s时，除x及除y均余0 , 除2x及除3y均余0，又除z余1 除2z余2， 用7除s时余2。30于是我们要求的数是 这就是孙子算经中“物不知其数” 一题的解，有 无穷多解，最小的正整数解是23（k=-2时）。31这里,(1),(2),(3)三式分别叫三个“单子因构件 ”,分别解得每个单因子构件,都是用某一个数去除余1,用另两个数去除 均余0的情况。再据题目要求余数分别是2,3,2的情况,凑成再看由（*）式得到的下面三个式子：32
15、所以，上述方法叫“单因子构件凑成法”解决“由几个平行条件表述的问题”的方法 （ 也称“孙子华方法”）这种方法的最大优点是，可以任意改变余数，加以推广：问题：有物不知其数，三三数之剩a，五五数之剩b，七七数之剩c，问物几何？答：解为 （ 的选取应使 ）.33推广了的“物不知其数”问题的解为明朝数学家程大位在算法统宗中把上式总结为一 首通俗易懂的歌决：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。 其中正半月是指15,这个口诀把3,5,7;70,21,15及105这几 个关键的数都总结在内了。详细说,歌诀的含义是:用3除 的余数乘70,5除的余数乘21,7除的余数乘15,相加后再减 去（“除”当“减”讲）105的适当倍数,就是需要求的（ 最小）解了。4）歌诀34当然，解，不是唯一的，每差105，都是另一个解答，但如果结合实际问题，答案往往就是唯一的了。例如一队士兵的大约人数，韩信应是知道的。35三、中国剩余定理1247年南宋的数学家秦九韶把孙子算经中“物不知其数”一题的方法推广到一般的情况，得到称之为“大衍求一术”的方法，在数书九章中发表。这个结论在欧洲要到十八世纪才由数学家高斯和欧拉发现。所以世界公认这个定理是中国人最早发现的，特别称之为“中国剩余定理”（Chinese remainder theorem）。该定理用现在的语言表达如下：36设 两两互素，设x分别被
