2、韩信点兵.doc

7 韩信点兵游戏内容老师说，我先给同学们讲一个韩信点兵的故事。相传韩信拜相时，问书记官：今天参加阅兵的共有多少兵士？ 书记官说：大概9000人。韩信问准确人数，书记官回答不出。于是韩信先让士兵5人一排从阅兵台前走过；再让士兵6人一排从阅兵台前走过；再让士兵7人一排从阅兵台前走过；最后让士兵11人一排从阅兵台前走过。韩信一边与汉高祖谈论着治国方略，一边记下了最后一排士兵的人数分别为1、5、4、10。韩信对汉高祖说，今天参加检阅的兵士准确人数为9041个。老师说：你们知道韩信是如何计算出总人数的吗？为了弄清这个问题，先做一个简单的练习，计算一下我这里有多少粒粉笔头？老师把粉笔盒中的粉笔头倒在桌面上，三三数之剩2，五五数之剩3，七七数之剩2。老师于是在黑板上写出了如下题目：三三数之剩2，五五数之剩3，七七数之剩2，问共有多少粒粉笔头？（粉笔头个数小于105）分班讨论，看哪班取胜？规律总结列4元一次方程是无法求解的。因为根据条件，我们只有三个方程： 所以解不出w来。解1：筛选法。第一遍筛子。三三数之剩2的数，有 5，8，11，14，17，20，23，26，29，32、35、38，第二遍筛子。从中找出五五数之剩3的数，有 8，23，38，第三遍筛子。从中找出七七数之剩2的数，有23，解不是唯一的。考虑到小于105的条件限制，则此数为23。这种筛选法，虽然不必再考察每一个自然数是否满足条件，也算是一种进步，但是求解还是相当繁琐的。上面所说的筛选法是“先细后粗”，如果把筛子的顺序颠倒一下，变成“先粗后细”，工作量将会大大减少。第一遍筛子。七七数之剩2的数，有 9，16，23，30，37、44，51，58，第二遍筛子。从中找出五五数之剩3的数，有 23，58，第三遍筛子。从中找出三三数之剩2的数，有23，解2：公倍数法。设此数为，按题目条件被3除余2，被5除余3，被7除余2。如果令，那末被3和7都能整除，被5除余1，显然。 所以。这种方法只适合于求解余数有某些特殊规律的情况。本题就是满足其中2个余数相同。对于一些特殊情形：如被3、5、7除的余数是2、1、3，我们把此数加上4以后，则恰好能被3、5、7整除，即105，故所求的数为101。再如，被3、5、7除的余数是1、2、3，我们把此数乘上2以后，余数则变为2、4、6，即为104，故所求的数为52。这种方法技巧性很强，不易掌握。解3：单因子构件凑成法。使用如下口诀：三人同行七十稀，五支梅花二十一，七子团圆正半月，除百零五便得知（明朝数学家程大位算法统宗）。即：把被3除的余数乘以70，被5除的余数乘以21，被7除的余数乘以15。3个数之和除以105，余数便为所求。对于此题则有 这里的70、21、15是如何得来的呢？仔细分析不难发现：70是被5和7能够整除、被3除余1的最小整数；21则是被3和7能够整除、被5除余1的最小整数；15是被3和5能够整除、被7除余1的最小整数。它们分别乘以各自对应的余数后，求和，当然也就满足原来的余数条件了。但是，这个解不是唯一的，每加上105，余数不变。因此，要给出一个满足条件的最小整数，除以105 所得的余数便是。这种方法民间称为“韩信点兵”，现代数学界又称之为“单因子构件凑成法”。为何称为单因子构件凑成法呢？请看一个简单的问题：某数能被5和7整除，被3除余1，求该数。设此数为，根据条件，有如下方程组：故： 所以 。这就是被3除余1的单因子构件。不管放大多少倍，它永远不会改变被5和7整除的性质。同理，可以推出被5除余1、被7除余1的单因子构件：由单因子构件凑出的和必然满足被3、5、7除余的条件。中国剩余定理1247 年南宋的数学家秦九韶把孙子算经中的“物不知其数”问题推广到一般情况，得到“大衍求一术”，写入数书九章中。600年后，直到18世纪，高斯和欧拉才发现了这个规律。所以称之为中国剩余定理。（韩信点兵发生在公元前200多年前，比秦九韶又早了1400多年。）该定理表述如下：设两两互素，设分别被除 所得的余数为，则可表示为其中D是的最小公倍数；是的公倍数，且被除余数为1；是任意整数，可以取负值。请注意“两两互素”的条件。如果知道分别被3、4、5除的余数，可以使用此方法。如果知道分别被4、6、7除的余数，则不能用此方法求得该数。应用举例：某单位有100个房间，编号从1到100，每个房间的门上配了一把三个数字的号码锁，为防止遗忘，又要保密，使外来人看不懂，就采用了中国剩余定理。把房间号分别被3、5、7除，所得的余数作为锁的号码。如：8号房间的号码为231，25号房间的号码为104，52号房间的号码为123。本单位的人只需把房间号作3次求余除法，就知道该房间号码锁的编号了。思考 韩信算法为请问式中的单因子1386、385、330、210是如何来的？为什么要加2310？这个数的意义何在？ 粉笔头若干，三三取之余2，五五取之余4，七七取之余6，问共有多少个粉笔头？ 粉笔头若干，三三数之余2，四四数之余1，五五数之余3，问共有多少个粉笔头？请找出计算此题的单因子？并用来计算此题。 请编辑一段程序，随机产生被3、5、7除所得的余数，让用户求出该数，并判断正确与否？题：单因子1386是能被6、7、11整除被5除余1的最小整数；单因子385是能被5、7、11整除被6除余1的最小整数；单因子330是能被5、6、11整除被7除余1的最小整数；单因子210是能被5、6、7整除被11除余1的最小整数。题： 题：被3、4、5整除问题的单因子为40、45、36。 题：“韩信点兵”程序设计一、窗体设计窗体设计很简单，只有3个按键：出题按键、回答按键和退出按键。二、程序设计 出题部分：主要功能是生成3个随机数，分别小于3、5、7。把它们作为某数被3、5、7除所得的余数。而后把题目显示在屏幕上。Dim n1 As Integer, n2 As Integer, n3 As Integer, m As IntegerPrivate Sub Command1_Click() n1 = 0: n2 = 0: n3 = 0: Cls Randomize (Timer) n1 = Int(3 * Rnd(1) n2 = Int(5 * Rnd(1) n3 = Int(7 * Rnd(1) FontBold = True :FontSize = 16 ForeColor = QBColor(12) CurrentX = 3800: CurrentY = 300 FontSize = 20: Print 题 目 FontSize = 14: ForeColor = QBColor(0) CurrentX = 3100: CurrentY = 700 Print 今有小球若干(小于105）。 CurrentX = 2500 Print 三三数之余; n1; ,五五数之余; n2; , CurrentX = 2500 Print 七七数之余; n3; ,问共有多少个 CurrentX = 2500 Print 小球？End Sub 判断对错：由用户回答小球的个数，电脑算出正确结果与用户的回答进行比较，如果相等，则显示“真聪明。回答正确！”；否则显示“很遗憾,回答错误！”，并告诉用户实际上是多少个。Private Sub Command3_Click() FontSize = 16: ForeColor = QBColor(12) CurrentX = 3800: CurrentY = 2000 FontSize = 20: Print 回 答 n = InputBox(您算出有多少小球？, 输入, 20, 5220, 1600) FontSize = 14: ForeColor = QBColor(0) CurrentX = 2500: CurrentY = 2400 Print 您的回答是，有; n; 小球。 m = (70 * n1 + 21 *