《韩信点兵(胡)》由会员分享,可在线阅读,更多相关《韩信点兵(胡)(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分别被