韩信点兵与中国剩余定理.ppt

《韩信点兵与中国剩余定理.ppt》由会员分享，可在线阅读，更多相关《韩信点兵与中国剩余定理.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1趣题找次品找次品： 1）有有5个外形相同的乒乓球，其中只有个外形相同的乒乓球，其中只有 1个重量不标准的次品乒乓球。个重量不标准的次品乒乓球。 现再给你一个标准球；请用一架不带现再给你一个标准球；请用一架不带砝码的天平，最多两次使用该天平，找砝码的天平，最多两次使用该天平，找出上述次品乒乓球。出上述次品乒乓球。2趣题找次品找次品： 2）有有12个外形相同的乒乓球，其中只有个外形相同的乒乓球，其中只有 1个重量不标准的次品乒乓球。请用一架不带个重量不标准的次品乒乓球。请用一架不带砝码的天平，最多三次使用该天平，找出上述砝码的天平，最多三次使用该天平，找出上述次品乒乓球，并判断它是重于标准球，还

2、是轻次品乒乓球，并判断它是重于标准球，还是轻于标准球。于标准球。3第三章第三章 若干数学典故中的若干数学典故中的 数学文化数学文化第三节韩信点兵与中国剩余定理第三节韩信点兵与中国剩余定理 4 一、一、“韩信点兵韩信点兵”的故事和的故事和 孙子算经孙子算经中的题目中的题目 1.“韩信点兵韩信点兵”的故事的故事 韩信阅兵时，让一队士兵韩信阅兵时，让一队士兵5人一行排队从他面前走人一行排队从他面前走过，他记下最后一行士兵的人数（过，他记下最后一行士兵的人数（1人）；再让这队士兵人）；再让这队士兵6人一行排队从他面前走过，他记下最后一行士兵的人数人一行排队从他面前走过，他记下最后一行士兵的人数（5人）

3、；再让这队士兵人）；再让这队士兵7人一行排队从他面前走过，他记人一行排队从他面前走过，他记下最后一行士兵的人数（下最后一行士兵的人数（4人），再让这队士兵人），再让这队士兵11人一行人一行排队从他面前走过，他记下最后一行士兵的人数（排队从他面前走过，他记下最后一行士兵的人数（10人）。人）。 然后韩信就凭这些数，可以求得这队士兵的总人数。然后韩信就凭这些数，可以求得这队士兵的总人数。5 这里面有什么秘密呢？这里面有什么秘密呢？ 韩信好像非常重视作除法时的韩信好像非常重视作除法时的余数余数6孙子算经孙子算经7 2.孙子算经孙子算经中的题目中的题目 我国古代数学名著我国古代数学名著孙子算经孙子算经

4、中有中有“物不知数物不知数”的的 题目：题目： 今有物不知其数，今有物不知其数， 三三数之剩三三数之剩2， 五五数之剩五五数之剩3， 七七数之剩七七数之剩2， 问物几何？问物几何？ 8 这里面又有什么秘密呢？这里面又有什么秘密呢？ 题目给出的条件，题目给出的条件， 也仅仅是作除法时的也仅仅是作除法时的余数余数9 二问题的解答二问题的解答 1从另一个问题入手从另一个问题入手 问题：问题：今有物不知其数，二二数之剩今有物不知其数，二二数之剩1，三三，三三数之剩数之剩2，四四数之剩，四四数之剩3，五五数之剩，五五数之剩4，六六数，六六数之剩之剩5，七七数之剩，七七数之剩6，八八数之剩，八八数之剩7，

5、九九数之，九九数之剩剩8，问物几何？，问物几何？10 1）筛法）筛法1，3，5，7，9，11，13，15，17，19， 21，23，25， （ 用用2除余除余1）5， 11， 17， 23， （ 用用3除余除余2）11， 23， （ 用用4除余除余3）11 再从中挑再从中挑“用用5除余除余4”的数，的数， 一直筛选下去，舍得下功夫，就一定可一直筛选下去，舍得下功夫，就一定可得结果。得结果。 并且看起来，解，还不是唯一的；可能并且看起来，解，还不是唯一的；可能有无穷多个解。有无穷多个解。12 化繁为简化繁为简的思想的思想 当问题中有很多类似的条件时，我们先只看其中两三个条件，这当问题中有很多类似

6、的条件时，我们先只看其中两三个条件，这就是就是化繁为简化繁为简。 一个复杂的问题，如果在简化时仍然一个复杂的问题，如果在简化时仍然保留了原来问题的特点和本保留了原来问题的特点和本质质，那么简化就，那么简化就“不失一般性不失一般性”。 学会学会“简化问题简化问题”与学会与学会“推广问题推广问题”一样，是一种重要的数学一样，是一种重要的数学能力。能力。 寻找规律寻找规律的思想的思想 把我们的解题方法总结为把我们的解题方法总结为筛法筛法，是重要的进步，是质的飞跃：，是重要的进步，是质的飞跃： 找到规律了。找到规律了。 筛法是一般性方法，还可以用来解决其他类似的问题。筛法是一般性方法，还可以用来解决其

7、他类似的问题。13 2 2）公倍数法）公倍数法 化繁为简化繁为简 我们还是先看只有前两个条件的简化题目。我们还是先看只有前两个条件的简化题目。 1，3，5，7，9，11，13，15，17，19，21，23，25， （ 用用2除余除余1） 5， 11， 17， 23， （ 用用3除余除余2） 上述筛选过程的第一步，得到上述筛选过程的第一步，得到: :1 1，3 3，5 5，7 7，9 9，1111，1313，1515，1717，1919，2121，2323，2525， 其实是列出了其实是列出了“用用2 2除余除余1”1”的数组成的数列。这个数列的数组成的数列。这个数列实际上是用实际上是用带余除法

8、带余除法的式子得到的。的式子得到的。14 所谓所谓“带余除法带余除法”，是指，是指整数整数的如的如下下“除法除法”： 被除数被除数 ，除数，除数 , 必唯一必唯一存在存在“商商” 和和“余余” ，使，使 q,0abqrrb0b ar15 当余当余 时，则时，则 ，称为，称为 “ 整除整除”，或，或 “ 整除整除 ”，这是通常除，这是通常除法法“ ” 的另一种表达形式。所以，的另一种表达形式。所以，带余带余除法是通常除法的推广。除法是通常除法的推广。0r abqab被baaqb16 回到求回到求“用用2除余除余1的数的数”的问题。设的问题。设这这样的数为样的数为 ，则，则 。这里。这里 是是被除

9、数，被除数，2是除数，是除数， 是商，是商，1是余，是余，且且 。x121xnx012 1n17 这就是这就是“带余除带余除法法”的式子。当取的式子。当取 时，时，用上式求得的用上式求得的 正好组成上述数列正好组成上述数列 1，3，5，7，9，11，13，15，17，19，21，23，25， 121(012),xn 10,1,2,3,4,n x18 接着从中筛选出接着从中筛选出“用用3除余除余2”的的数，就是挑出符合下面数，就是挑出符合下面“带余除法带余除法”表达表达式式的数，这里的数，这里 可取可取0，1，2，3，4， 再继续做下去再继续做下去 232,(023)xn2n19 如果我们不分上

10、面两步，而是一上如果我们不分上面两步，而是一上来就来就综合综合考虑考虑两者两者，则就是要解联立方，则就是要解联立方程组程组 1221.32xnxxn中的20 那么，为了解这个方程组，除了刚才的筛法那么，为了解这个方程组，除了刚才的筛法外，还有没有更加巧妙的解法？外，还有没有更加巧妙的解法？ 我们考察上边两个方程的特点，发现，两个我们考察上边两个方程的特点，发现，两个“带余除法带余除法”的式子，都是的式子，都是“余数比除数少余数比除数少1 1”。 于是想到，如果于是想到，如果把被除数再加把被除数再加1 1，不是余数就，不是余数就为为0 0了吗？换句话说，不是就出现了吗？换句话说，不是就出现整除整

11、除的情况了吗？的情况了吗？21 于是把上边每个方程两边都加上于是把上边每个方程两边都加上1，成为，成为 这说明，这说明， 既是既是2的倍数，又是的倍数，又是3的的倍数，因此，它是倍数，因此，它是2与与3的公倍数。由此想到的公倍数。由此想到1212(1)13(1)xnxn 1x22对整个问题寻找规律对整个问题寻找规律问题：问题： 今有物不知其数，二二数之剩今有物不知其数，二二数之剩1，三三，三三数之剩数之剩2，四四数之剩，四四数之剩3，五五数之剩，五五数之剩4，六六，六六数之剩数之剩5，七七数之剩，七七数之剩6，八八数之剩，八八数之剩7，九九，九九数之剩数之剩8，问物几何？，问物几何？23 寻找

12、规律寻找规律 设问题中，需要求的数是设问题中，需要求的数是 ，则，则 被被2，3，4，5，6，7，8，9去除，所得的余数都去除，所得的余数都是比除数少是比除数少1，于是我们把被除数，于是我们把被除数 再加再加1， 则则 就可被就可被2，3，4，5，6，7，8，9均均整除。也就是说，整除。也就是说， 是是2,3,4,5,6,7,8,9的公倍数，从而是其最小公倍数的公倍数，从而是其最小公倍数2,3,4,5,6,7,8,9的倍数。的倍数。xxx1x1xx24 即即 这就是原问题的全部解，有无穷多个解，其中第这就是原问题的全部解，有无穷多个解，其中第一个解是一个解是2519；我们只取正数解，因为；我们

13、只取正数解，因为“物体的物体的 个数个数”总是正整数。总是正整数。 12,3,4,5,6,7,8,92520,1,2,3,xkkk 25201,1,2,3,xkk25 思思： 求求“用用2除余除余1，3除余除余2， 用用m除余除余 m 1”的数。的数。 求求“用用a除余除余a 1，用，用b除余除余b1，用，用c除余除余c1”的数。的数。 （a,b,c是任意大于是任意大于1的自然数）的自然数） 求求“用用2，3，4，5，6，7，8，9除除 都都余余1”的数。的数。 求求“用用5，7，9，11 除都余除都余2”的数。的数。26 2孙子算经孙子算经中中“有物不知其数有物不知其数” 问题的解答问题的解

14、答 问题：问题：今有物不知其数，今有物不知其数， 三三数之剩三三数之剩2， 五五数之剩五五数之剩3， 七七数之剩七七数之剩2， 问物几何？问物几何？271）筛法）筛法.2，5，8，11，14，17，20，23，26，29，（用（用3除余除余2）8，23， （用（用5除余除余3）23， （用（用7除余除余2） 由此得到，由此得到，23是最小的一个解。是最小的一个解。 至于下一个解是什么，要把至于下一个解是什么，要把“”写出来才知道；写出来才知道； 实践以后发现，是要费一点儿功夫的。实践以后发现，是要费一点儿功夫的。28 2）公倍数法）公倍数法 现在仿照上边用过的现在仿照上边用过的“公倍数法公倍数

15、法”，设要求的数为设要求的数为 ，则依题意，得联立，则依题意，得联立方程组方程组x1233253(*)72xnxnxn29 按上一问题中按上一问题中“公倍数法公倍数法”解决问题的解决问题的思路：把思路：把方程两边同时加上或减去方程两边同时加上或减去一个什么一个什么样的数，就能使三个等式的右边分别是样的数，就能使三个等式的右边分别是3 3，5 5，7 7的倍数，从而等式左边就是的倍数，从而等式左边就是3 3，5 5，7 7的公倍的公倍数了。数了。 这要通过这要通过反复反复的试算去完成。的试算去完成。30一种试算的方法一种试算的方法1233253(*)72xnxnxn31 从第三个等式入手，两边加

16、从第三个等式入手，两边加5（或减（或减2）则则得得 357(1)xn3(27)xn或32 则右边是则右边是7的倍数了，但两边加的倍数了，但两边加5（或减（或减2）并不并不能使前两式的右边分别是能使前两式的右边分别是3的倍数和的倍数和5的倍数，所以的倍数，所以两边加两边加5（或减（或减2）并不能使右边成为并不能使右边成为3，5，7的公的公倍数。再继续从第三个等式入手，为使第三个等式倍数。再继续从第三个等式入手，为使第三个等式右边仍然保持是右边仍然保持是7的倍数，可再加的倍数，可再加 （或再减（或再减 ），则则 （或（或 ） 将将 代入试算、分代入试算、分 析，析，7l3577(1)xlnl 32

17、77()xhnh1,2,3l 7h(1,2,3)h 或33 最后发现，为达到目的最后发现，为达到目的（三个等式的右边分别是（三个等式的右边分别是3，5，7的倍的倍数），最小的加数是数），最小的加数是82（ 时时 ）（或最小的减数是（或最小的减数是23，即即 时时 ）。11l 5782l3h 2723h34 用等式两边加用等式两边加82来求解，有来求解，有 用等式两边减用等式两边减23来求解，有来求解，有 多了一个多了一个“ ” ，因这时，因这时 也是正数，也是正数，合合 要求要求。0k123823(28)825(17)823,5,7105827(12)10582,1,2,3,xnxnxkkxn

18、xkk123233(7)235(4)233,5,7105237(3)10523,0,1,2,3,xnxnxkkxnxkkx35 这两组解是一样的，都是这两组解是一样的，都是“23，23+105，23+2105，”。 原因是原因是82+23=105，故令，故令 ， 第一组解就成为第一组解就成为 便转化成第二组解。便转化成第二组解。1kk105(1)821051058210523xkkk36 但是，这但是，这82和和23来之不易；并且如果来之不易；并且如果题目中的余数题目中的余数变了，就得重新试算，所以变了，就得重新试算，所以这方法缺少一般性，为使它具有一般性，这方法缺少一般性，为使它具有一般性，

19、要做根本的修改。要做根本的修改。37 3）单因子构件凑成法）单因子构件凑成法 我们先对前几页（我们先对前几页（*）式作两个方面的简化：）式作两个方面的简化：一方面一方面是是每次只考虑每次只考虑“一个除式一个除式”有余数的情况（即另两个除式都有余数的情况（即另两个除式都是整除的情况）；是整除的情况）；另一方面另一方面是把余数都简化为最简单的是把余数都简化为最简单的1。这样得到三组方程。这样得到三组方程。1233253(*)72xnxnxn11122233331335(1);51(2);5(3)7771xnynznxnynznxnynzn38 （1）式意味着，在）式意味着，在5和和7的公倍数中（的

20、公倍数中（35，70，105，）寻找被）寻找被3除余除余1的数；的数； （2）式意味着，在）式意味着，在3和和7的公倍数中（的公倍数中（21，42，63，）寻找被）寻找被5除余除余1的数；的数； （3）式意味着，在）式意味着，在3和和5的公倍数中（的公倍数中（15，30，45，）寻找被）寻找被7除余除余1的数。的数。11122233331335(1);51(2);5(3)7771xnynznxnynznxnynzn39 对（对（1）式而言，这个数可以取）式而言，这个数可以取70，对（，对（2）式而言，）式而言，这个数可以取这个数可以取21，对（，对（3）式而言，这个数可以取）式而言，这个数可以

21、取15。 于是（于是（1）式两边同减）式两边同减70变为这样：变为这样：第二个等式右边仍第二个等式右边仍是是5的倍数，第三个等式右边仍是的倍数，第三个等式右边仍是7的倍数，而第一个等式的倍数，而第一个等式右边因为减的右边因为减的70是是“用用3除余除余1”的数，正好原来也多一个的数，正好原来也多一个1，减没了。第一个等式右边也成为了倍数，是减没了。第一个等式右边也成为了倍数，是3的倍数。的倍数。 11122233331335(1);51(2);5(3)7771xnynznxnynznxnynzn40（2）式两边同减）式两边同减21变为变为 1112113703(23)703,5,7105705

22、(14)10570,0,1,2,707(10)xnxkkxnxkkxn1222223213(7)213,5,7105215(4)10521,0,1,2,217(3)ynykkynykkyn41 （3）式两边同减）式两边同减15变为变为 于是得到于是得到 1332332153(5)153,5,7105155(3)10515,0,1,2,157(2)znzkkznzkkzn 123105701052110515xkykzk42 现在重复一下：所得的现在重复一下：所得的x是是被被3除余除余1，被，被5和和7除余除余0的数；的数；y是是被被5除余除余1，被，被3和和7除余除余0的数；的数；z是是被被7

23、除余除余1，被，被3和和5除余除余0的数。的数。43 那么，凑出那么，凑出 ， s 不就是我们需要求的数吗？不就是我们需要求的数吗？ 232sxyz44 因为，用因为，用3去除去除s时，除时，除y及除及除z均余均余0 除除3y及除及除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时余时余

24、2。45 于是我们要于是我们要求的数求的数是是 这就是这就是孙子算经孙子算经中中“物不知其数物不知其数”一题的解，有无穷多解，最小的正整数解是一题的解，有无穷多解，最小的正整数解是23（ 时）。时）。1231232322(10570)3(10521)2(10515)(70221 3152)105(232)70221 31521052, 1,0,1,2,3,sxyzkkkkkkkk 2k 46 这里，（这里，（1），（），（2），（），（3）三式分别叫三个）三式分别叫三个“单子因构件单子因构件”，分，分别解得别解得 每个单因子构件，都是用某一个数去除余每个单因子构件，都是用某一个数去除余1，用另

25、两个数去除均余，用另两个数去除均余0的情况。再据题目要求余数分别是的情况。再据题目要求余数分别是2，3，2的情况，凑成的情况，凑成11122233331335(1);51(2);5(3)7771xnynznxnynznxnynzn232sxyz123105701052110515xkykzk47 所以，上述方法叫所以，上述方法叫“单因子构件凑成法单因子构件凑成法” 解决解决“由几个平行条件表述的问题由几个平行条件表述的问题”的方法的方法 （ 也称也称“孙子孙子华方法华方法”） 这种方法的最大优点是，可以这种方法的最大优点是，可以任意改变余数任意改变余数，加，加以以推广推广： 题：题： 有物不知

26、其数，三三数之剩有物不知其数，三三数之剩a，五五数，五五数 之剩之剩b，七七数之剩，七七数之剩c，问物几何？，问物几何？ 答：答：解为解为 （ 的选取应使的选取应使 ）.702115105sabck,kkZ0s 48 4）歌诀）歌诀 推广了的推广了的“物不知其数物不知其数”问题的解为问题的解为 明朝数学家程大位在明朝数学家程大位在算法统宗算法统宗中把上式总结为一首中把上式总结为一首通俗易懂的歌决：通俗易懂的歌决： 三人同行七十稀，五树梅花廿一枝，三人同行七十稀，五树梅花廿一枝， 七子团圆正半月，除百零五便得知。七子团圆正半月，除百零五便得知。 其中正半月是指其中正半月是指15，这个口诀把，这个

27、口诀把3，5，7；70，21，15及及105这几个关键的数都总结在内了。详细说，歌诀的含这几个关键的数都总结在内了。详细说，歌诀的含义是：用义是：用3除的余数乘除的余数乘70，5除的余数乘除的余数乘21，7除的余数乘除的余数乘15，相加后再减去（，相加后再减去（“除除”当当“减减”讲）讲）105的适当倍数，的适当倍数，就是需要求的（最小）解了。就是需要求的（最小）解了。702115105sabck49 当然，解，不是唯一的，每差当然，解，不是唯一的，每差105，都是另一个解答，但如果结合实际问题，都是另一个解答，但如果结合实际问题，答案往往就是唯一的了。例如一队士兵的答案往往就是唯一的了。例如

28、一队士兵的大约人数，韩信应是知道的。大约人数，韩信应是知道的。50 三、中国剩余定理三、中国剩余定理 1247年南宋的数学家秦九韶把年南宋的数学家秦九韶把孙子算经孙子算经中中“物不知其数物不知其数”一题的方法推广到一般的情况，得一题的方法推广到一般的情况，得到称之为到称之为“大衍求一术大衍求一术”的方法，在的方法，在数书九章数书九章中发表。这个结论在欧洲要到十八世纪才由数学家中发表。这个结论在欧洲要到十八世纪才由数学家高斯和欧拉发现。所以世界公认这个定理是中国人高斯和欧拉发现。所以世界公认这个定理是中国人最早发现的，特别称之为最早发现的，特别称之为“中国剩余定理中国剩余定理”（Chinese

29、remainder theorem）。）。51 该该定理定理用现在的语言表达如下：用现在的语言表达如下： 设设 两两互素，设两两互素，设 分别被分别被 除所得的余数为除所得的余数为 ，则，则 可表示为下式可表示为下式 其中其中 是是 的最小公倍数；的最小公倍数； 是是 的公倍数，而且被的公倍数，而且被 除所得除所得余数为余数为1； 是任意整数。是任意整数。 id12,nd dd12,nd dd12,nr rr1122nnxkrkrkrkD12,nd ddik111,iinddddDkxx52 要注意的是，用上述定理时，要注意的是，用上述定理时， 必须两两互素。前面的问题中，必须两两互素。前面的

30、问题中，3，5，7是两是两两互素的，所以两互素的，所以“三三数，五五数，七七数三三数，五五数，七七数”得得余数后可用此公式。但余数后可用此公式。但“四四数，六六数，九四四数，六六数，九九数九数”得余数后就不能用此公式，因为得余数后就不能用此公式，因为4、6、9并不是两两互素的。并不是两两互素的。12,nd dd53 “中国剩余定理中国剩余定理”不仅有光辉的历史意义，直到现在不仅有光辉的历史意义，直到现在还是一个非常重要的定理。还是一个非常重要的定理。1970年，年轻的苏联数学家年，年轻的苏联数学家尤里尤里. .马季亚谢维奇（）（）（28岁）解决了希岁）解决了希尔伯特提出的尔伯特提出的23个问题

31、中的第个问题中的第10个问题，轰动了世界数个问题，轰动了世界数学界。他在解决这个问题时，用到的知识十分广泛，而学界。他在解决这个问题时，用到的知识十分广泛，而在一个关键的地方，就用到了我们的祖先一千多年前发在一个关键的地方，就用到了我们的祖先一千多年前发现的这个现的这个“中国剩余定理中国剩余定理”。5440年前年前“中国剩余定理中国剩余定理”的一个应用的一个应用 “中国剩余定理中国剩余定理”不仅有光辉的不仅有光辉的历史意义，直到现在还是一个非常重历史意义，直到现在还是一个非常重要的定理。要的定理。1970年，年轻的苏联数学年，年轻的苏联数学家家尤里尤里. .马季亚谢维奇（）（28岁）岁） (英

32、文译名英文译名Yuri Matiyasevich) 解决了希尔解决了希尔伯特提出的伯特提出的23个问题中的第个问题中的第10个问题，个问题，轰动了世界数学界。他在解决这个问轰动了世界数学界。他在解决这个问题时，用到的知识十分广泛，而在一题时，用到的知识十分广泛，而在一个关键的地方，就用到了我们的祖先个关键的地方，就用到了我们的祖先一千多年前发现的这个一千多年前发现的这个“中国剩余定中国剩余定理理”。55希尔伯特的第10个问题： 丢番图方程的可解性 能求出一个整系数方程的整数根，称为丢番图方程可解。希尔伯特问，能否用一种由有限步构成的一般算法判断一个丢番图方程的可解性？1970年，苏联的IO.B

33、.马季亚谢维奇证明了希尔伯特所期望的算法不存在。 希尔伯特56 四、有趣的应用四、有趣的应用 某单位有某单位有100把锁，分别编号为把锁，分别编号为1，2，3，100。现在要对钥匙编号，使外单位。现在要对钥匙编号，使外单位的人看不懂，而本单位的人一看见锁的号码的人看不懂，而本单位的人一看见锁的号码就知道该用哪一把钥匙。就知道该用哪一把钥匙。 57 能采用的方法很多，其中一种就是利用中国能采用的方法很多，其中一种就是利用中国剩余定理，把锁的号码被剩余定理，把锁的号码被3，5，7去除所得的三个去除所得的三个余数来作钥匙的号码（首位余数是余数来作钥匙的号码（首位余数是0时，也不能省时，也不能省略）。

34、略）。 这样每把钥匙都有一个三位数编号。这样每把钥匙都有一个三位数编号。 例如例如23号锁的钥匙编号是号锁的钥匙编号是232号，号，52号锁的钥匙号锁的钥匙编号是编号是123号。号。58 8号锁号锁231 19号锁号锁145 45号锁号锁003 52号锁号锁123 因为只有因为只有100把锁，不超过把锁，不超过105，所以锁的号与，所以锁的号与钥匙的号是一一对应的。钥匙的号是一一对应的。 如果希望保密性再强一点儿，则可以把刚才所如果希望保密性再强一点儿，则可以把刚才所说的钥匙编号加上一个固定的常数作为新的钥匙编说的钥匙编号加上一个固定的常数作为新的钥匙编号系统。甚至可以每过一个月更换一次这个常

35、数。号系统。甚至可以每过一个月更换一次这个常数。这样，仍不破坏锁的号与钥匙的号之间的一一对应，这样，仍不破坏锁的号与钥匙的号之间的一一对应，而外人则更难知道了。而外人则更难知道了。59趣题找次品找次品： 1）有有5个外形相同的乒乓球，其中只有个外形相同的乒乓球，其中只有 1个重量不标准的次品乒乓球。个重量不标准的次品乒乓球。 现再给你一个标准球；请用一架不带现再给你一个标准球；请用一架不带砝码的天平，最多两次使用该天平，找砝码的天平，最多两次使用该天平，找出上述次品乒乓球。出上述次品乒乓球。60最优化思想最优化思想最少次数完成预定任务最大限度发挥该天平的作用61趣题找次品找次品： 2）有有12

36、个外形相同的乒乓球，其中只有个外形相同的乒乓球，其中只有 1个重量不标准的次品乒乓球。请用一架不带个重量不标准的次品乒乓球。请用一架不带砝码的天平，最多三次使用该天平，找出上述砝码的天平，最多三次使用该天平，找出上述次品乒乓球，并判断它是重于标准球，还是轻次品乒乓球，并判断它是重于标准球，还是轻于标准球。于标准球。62思考题思考题 如果只要求找出次品乒乓球，并不要如果只要求找出次品乒乓球，并不要求判断次品是过重还是过轻，那么三次使求判断次品是过重还是过轻，那么三次使用不带砝码的天平，最多可以用不带砝码的天平，最多可以从多少个从多少个乒乓球乒乓球中中找出找出唯一唯一的次品？的次品？63本节结束本

37、节结束谢谢！谢谢！64思考题解答思考题解答65 思思： 求求“用用2除余除余1，用，用3除除2， 用用m除余除余m 1”的数。的数。 答：答：2,3, 1,1,2,3,xkmk66 求求“用用a除余除余a1，用，用b除余除余b1，用，用c除余除余c1”的数（的数（a,b,c是任意是任意大于大于1的自然数）的自然数） 答：答： , , 1,1,2,3,xka b ck67 求求“用用2，3，4，5，6，7，8，9除都余除都余1”的数。的数。 答：答： 12,3,4,5,6,7,8,9,2,3,91,0,1,2,3,xkxkk 68 求求“用用5，7，9，11 除都余除都余2”数。数。 答：答：2

38、5,7,9,11,5,7,9,112,0,1,2,3,xkxkk6970 2）筛法）筛法 先只看前两个条件先只看前两个条件 用用2除余除余1，用，用3除余除余2，求这样的数，一种普通，求这样的数，一种普通的办法就是；先把的办法就是；先把“用用2除余除余1”的数全列出来：的数全列出来： 1，3，5，7，9，11，13，15，17，19， 21，23，25， 再从中筛选，挑出其中再从中筛选，挑出其中“用用3除余除余2”的数来：的数来： 5， 11， 17， 23， 71 再看所有的条件再看所有的条件 这就启发我们想到，只这就启发我们想到，只要从上边筛选下的数中，继续挑出要从上边筛选下的数中，继续挑出“用用4除余除余3”的数：的数： 11， 23， 再挑再挑“用用5除余除余4”的数，的数，一直筛选下去，舍一直筛选下去，舍得下功夫，就一定可得结果，并且看起来，解，得下功夫，就一定可得结果，并且看起来，解，还不是唯一的，可能有无穷多个解。还不是唯一的，可能有无穷多个解。