具体数学--2007--Lec03

1、具体数学第3章 整函数主 讲: 顾 乃 杰 教授单 位: 计算机科学技术系 时 间: 2007 (秋)中国科学技术大学-计算机科学技术系Department of Computer Science & Technology2021-11-262第四章Concrete Mathematics 具体数学 作者： R. L. Graham D. E. Knuth O. Patashnik 机械工业出版社 Department of Computer Science & Technology2021-11-263评 分 原 则n平时： 40 % 作 业：20 % 学习报告：20 %n期

2、未考试：60 % 书面考试，开卷。Department of Computer Science & Technology2021-11-264第三章 整函数 整数是离散数学的主要构成部分，而且我们经常需要把分数或任意实数转换为整数。本章的目的就是：n熟悉并灵活运用这种转换；n学会它们的一些重要性质。Department of Computer Science & Technology2021-11-2653.1下整函数和上整函数 n对于所有实数x，下整（最大整数）和上整（最小整数）函数的定义如下：n =小于或等于x的最大整数；n =大于或等于x的最小整数；n图形表示，像阶梯一样

3、分布在直线f (x) = x的上下： x xDepartment of Computer Science & Technology2021-11-266几个常识n因为下整函数总是位于对角线f(x) = x之下或者相交，所以有 x，而 x。在整数点上两个函数恰好相等：n两者不同时，上整恰好比下整大1：n =x不是整数n把对角线向下平移一个单位，那它就完全位于下整函数之下：n这两个函数是关于两个坐标轴彼此对称的： x x .integeran is xxxxx xx 11xxxxx xx xxDepartment of Computer Science & Technology20

4、21-11-267四个规则 n为了实际证明下整函数和上整函数的性质，而不是仅仅从图形上看出来，下面四个规则是特别有用的： 1nxnnx xnxnx1 nxnnx1 1xnxnxDepartment of Computer Science & Technology2021-11-268相关性质n可以把整数项移进或者移出下整函数（或上整函数）：n一般不能进行像移出常数因子这种类似运算。例如，当n=2和x=1/2时，我们有n在许多场合中，下整和上整括号是多余的，例如： nxnx xnnx nxnx xnxn nxnx xnxnDepartment of Computer Science &a

5、mp; Technology2021-11-269分数部分 nx和 之间的差称为x的分数部分，可以表示为：x=x-n 也称为x的整数部分。n 的性质：n 如果x= +x，并且y= +y； x x xyx yxyxyx x yDepartment of Computer Science & Technology2021-11-26103.2 下整上整的应用 n先看下面的命题：n没能找到反例意味着等式普遍成立n可以证明普遍成立。n推广此想法且证明更多的结果：设f(x)是任意连续的单调上升函数，可以得到：n特殊情况： xx )()(xfxf )()(xfxf nmxnmx nmxnmxDep

6、artment of Computer Science & Technology2021-11-2611数学的层次n层次1 给定一个明确的对象x和一个明确的性质P (x)，证明P (x)为真。n层次2 给定一个明确的集合X和一个明确的性质P (x)，证明对于所有的xX，P (x)为真。n层次3 给定一个明确的集合X和一个明确的性质P(x)，证明或者推翻对于xX，P(x)为真。n层次4 给定一个明确的集合X和一个明确的性质P(x)，找P(x)为真的必要充分条件Q(x)。n层次5 给定一个明确的集合X，找到其中元素的一个有趣性质P (x)。Department of Computer Sc

7、ience & Technology2021-11-2612一个应用n具体数学俱乐部的娱乐场有一个轮盘赌，共有编号从1到1000的1000个位置。如果一次旋转得到的数n可以被它的立方根的下整除尽，也就是说，如果 则称为赢者数，且娱乐场付给我们5元；否则称为输者数，且我们必须要付出1元，我们能够赢钱吗？n赢者数的平均数目为,3nn.1000100061000)1000(510005WWWLWDepartment of Computer Science & Technology2021-11-2613整个系统方案n利用Iverson关于取值为0或1的逻辑表达式的约定，就能系统分析整

8、个方案： .172923171431/1331101/111011110001110001 winnera is 10110122,32,33,33,310001310001 kkmkmknmknknnkkkkkkkkkmkkkmknkmnknknnknknnnWDepartment of Computer Science & Technology2021-11-2614推广n让我们进行推广。假设将1000变为1000000，或改变为更大的数N：n仔细地处理k的最大值K：n对于一般的N，赢者数的总数为：n一般解答为：.3nK ./42523/1137214322231 mmmKkKNK

9、mKKKNKmKKNKmKkW325212KKKNWDepartment of Computer Science & Technology2021-11-2615谱n我们定义实数的谱为一个无限的整数多重集：n易证任意两个谱都不是相等的 意味着Spec()Spec() n谱具有许多极好的性质。以下两个谱中：看起来在一个谱中缺少的数字会在另一个中出现，但是没有数字在两个谱中同时出现 .,3,2,Spec.,51,47,44,40,37,34,30,27,23,20,17,13,10, 6 , 3)22(,24,22,21,19,18,16,15,14,12,11, 9 , 8 , 7 ,

10、5 , 4 , 2 , 1)2(SpecSpecDepartment of Computer Science & Technology2021-11-26163 3. .3 3 下整下整/ /上整递归上整递归n下整和上整为递归关系的研究开拓了一个新的有趣视野。我们进而讲述下整和上整的一个有趣的新的方面，也就是研究递归关系。让我们首先观察下面这个递归： (3.16)n这样 是1min(2 ，3 ) = 3；序列起始为1，3，3，4，7，7，7，9，9，10，13，。本书的作者之一谨慎地决定称这些数为Knuth数。 01231;1min(2,3)nnnKKKK 1K0K0KDepartme

11、nt of Computer Science & Technology2021-11-2617下整下整/ /上整递归上整递归n习题25要求证明或者推翻命题：对于所有n0， n。刚才列出的前面少数几个K值确实满足这个不等式，所以这个命题很可能普遍成立。让我们尝试用归纳法来证明，从递归方程的定义可以直接得到基础n0。对于归纳步，假设对于小于某个指定的非负整数n的所有值，不等式成立，我们试着证明 n1。由递归方程可知 1min(2 ，3 )。归纳假设告诉我们2 2 ，3 3 。可是，2 可以小到n1，3 可以小到n2。根据我们的归纳假设最多能推得 1 + (n2），这远达不到 n1。n我们现

12、在有理由怀疑Knn的真值性，所以让我们试着推翻它。若能找到一个n使得2n或者3n，而换句话说就是使得n我们将得到 n1。这可能吗？我们会在习题25进行讨论，所以这里最好不给出解答。, 3/or 2/3/2/nKnKnnnK1nK1nK1nK1nK2nK2nK3nK3nK2n2n3n3n1nKDepartment of Computer Science & Technology2021-11-2618下整下整/ /上整递归上整递归n涉及下整和或上整的递归关系经常出现在计算机科学中，因为很多算法都是基于重要的“分而治之”技巧的，因此经常把大小为n的问题简化为多个大小为n的部分的类似问题的解

13、。例如，一种n条记录的分类方法（n1）就是把它们分为两个几乎相等的部分，一部分大小为，另一部分为。（顺便提一句，注意这个公式迟早会经常用到。） (3.17) n在对每部分各自进行分类之后（用相同方法，递归应用），最多多再进行n1次比较，就能把记录合并为最终的次序。因此最多需要进行f (n)次比较，其中 (3.18);2/2/nnn(1)0;( )(/2 )(/2 )1, 1ff nfnfnnnDepartment of Computer Science & Technology2021-11-2619下整下整/ /上整递归上整递归n第一章中的Josephus问题有一个类似的递归方程，它

14、能变成形式n我们已经可以使用比第一章中多的工具了，所以让我们考虑更正式的Josephus问题：问题中每次排除剩下的第三个人，而不是第二个人。如果我们将第一章中使用的方法应用到这个更困难的问题，最终得到下面的递归方程：n后面我们会其中的mod函数作简要分析，而且根据n mod 3 = 0，1或2得到 = 2，+1，或。但是很难对这个递归作进一步讨论。 . 1for ,12/2)(; 1) 1 (nnJnJJn, 1mod3223)(33nanJnJnnDepartment of Computer Science & Technology2021-11-2620下整下整/ /上整递归上整递

15、归n另一种解Josephus问题的方法给出了一种好得多的构造。每次轮转时，我们对幸存的人都分配一个新的编号。于是，1和2变成n1和n2，而3被执行；4和5变成n3和n4，而6被执行；，3k1和3k2变成n2k1和n2k2，而3k3被执行；，最后3n被执行（或留下幸存）。例如，当n10，编号为第k个被排除的人的编号为3k。所以如果我们能计算出编号为3n的人原先的编号，那么我们就能判断出谁是幸存者。302928272625242322212019181716151413121110987654321Department of Computer Science & Technology202

16、1-11-2621下整下整/ /上整递归上整递归n如果Nn，那么编号人数N一定有前一次的编号，而我们也能这样找到它：设N = n + 2k + 1或者N = n + 2k + 2，那么k = ，他们以前各自的编号为3k + 1或3k + 2。也就是说，编号N的前一次的编号是3k + (N n 2k) = k + N n。因此我们能计算幸存者数 如下：这并不是 的闭形式，甚至连递归都不是。但是它至少告诉我们在n很大时，如何足够快地求解。(1) 2Nn(3)( )Jn(3)( )Jn .:;21: do while;3:3NnJnNnNNnNnNDepartment of Computer Sci

17、ence & Technology2021-11-2622下整下整/ /上整递归上整递归n幸运的是，我们可以用变量D = 3n + 1 N替换N，这样就可以简化这个算法。（这种符号改变表示对应于用从3n下降到1的编号，代替从1上升到3n的编号，有几分像倒计时。）于是结构复杂的N的赋值公式就变为n我们可以把算法改写为：,23222213211313:DDDDDDnDnnDnnDnnD .13:;23: do 2 while; 1:3DnnJDDnDDDepartment of Computer Science & Technology2021-11-2623下整下整/ /上整递归

18、上整递归n这看来好得多了，因为n以一种十分简单的方式进入计算。事实上，同样的推导可以得到当每次消除第q个人时，幸存者 可以计算如下： (3.19)在我们十分了解q=2的情况中，当 时，D变大为 ；因此 . .1:;1: do 1 while; 1:DqnnJDqqDnqDDq( )qJn2mnl12m12( )2(2)1221mmJnll Department of Computer Science & Technology2021-11-2624下整下整/ /上整递归上整递归n式(3.19)中的方法计算出的整数序列，可以由下面的递归方程定义： (3.20)除了q=2的情况外，这些数看

19、起来并不是简单地与任何常见的函数相关，因此它们也许没有好的闭形式。但是如果我们愿意接受序列为“常见”函数值，那么就容易描述一般Josephus问题的解：幸存者 为 ，其中k需要尽可能地小以满足 。( )0( )( )11; 01qqqnnDqDDnq( )qJn( )1qkqnD ( )(1)qkDqnDepartment of Computer Science & Technology2021-11-26253 3. .4 4 MOD: MOD: 二元运算二元运算n当m和n是正整数时，m除n的商是。m除n的剩余也有一个简单方便的符号表示，称为n mod m。基本公式n告诉我们，可以把

20、n mod m表示为nm。我们能把这种表示推广到负整数，实际上可以推广到任意实数： (3.21)n这就把mod定义为一个二元运算，就像加法和减法是二元运算那样。 remainderquotientmnmnmnmod/mod/, 0 xyxy x yyDepartment of Computer Science & Technology2021-11-2626MOD: MOD: 二元运算二元运算n当x或y是正实数时，我们容易领会x mod y的直观意义：如果我们假设有一个周长为y的圆，圆周上的点对应于区间0.y）中的实数。如果我们从0开始沿着圆周移动距离x，那我们的结束点就是x mod

21、y。（我们移动过程中时遇到0的次数为 。）n当x或y是负数时，为了确切地理解它，我们需要仔细看一看定义。这里有一些整数值的例子：/x y. 2)3/(5)3(53mod5; 13/5353mod5; 1)3/(5)3(53mod5; 23/5353mod5Department of Computer Science & Technology2021-11-2627MOD: MOD: 二元运算二元运算nmod后面的数称为模数；至今无人对mod前面的数命名。在应用中，模数通常是正的，但是当模数为负时，定义也完全有意义。两种情况中，x mod y的值均在0和模数之间：n当y = 0时情况如何

22、呢？这种情况下定义式（3.21）无定义，为了避免被零除，同时也为了完整性起见，我们可以定义 (3.22)n这个约定保持了x mod y总与x相差为y的倍数的性质。（看来通过定义 可以更自然地使函数在0点连续。但是在第四章中我们将看到这个没多大用处。连续性不是mod运算的重要方面。）. 0for ,mod0; 0for ,mod0yyyxyyyxmod0 xx0mod0lim mod0yxxyDepartment of Computer Science & Technology2021-11-2628MOD: MOD: 二元运算二元运算n当我们用x划分为它的整数部分和分数部分x x时，我

23、们就得到了mod的一种不易发觉的特殊情况。分数部分也可以记为x mod 1，因为我们有注意，在此公式中不需要圆括号，因为我们认为mod的运算优先级比加法或者减法高。n定义mod时用到了下整函数，却没有用到上整函数。我们也许可以用上整来定义类似于mod的运算，如 n在前面用到的圆周类比情况中，这表示行进者需要继续行进的距离，在行进距离x之后，返回到起始点0。当然我们需要一个比mumble更好的名字。如果出现足够多的应用，它也许就会有一个合适的名字。x . 1modxxx;/ mumble xyxyyxDepartment of Computer Science & Technology2

24、021-11-2629MOD: MOD: 二元运算二元运算n分配律是mod的最重要的代数性质：对于所有实数c，x和y，我们有 c(x mod y) = (cx) mod (cy) (3.23) （有些人认为mod的运算优先级比乘法要低，这样就可以从右边也移去圆括号。）根据定义（3.21）容易证明分配律，因为若cy0，则而且在模数为零的情况平凡地成立。我们的四个例子（用5和3）两次证明了这个定律，其中c1。如式（3.23）的等式使我们相信mod的定义比较恰当。n我们将在本节余下部分中讨论一种应用。mod在其中虽然不是关键所在，但是却很有用。这个问题在各种场合中经常：把n个事物划分为尽可能相等的m

25、组。,mod/modcycxcycxcycxyxyxcyxcDepartment of Computer Science & Technology2021-11-2630MOD: MOD: 二元运算二元运算n例如，假设我们有n行短文，需要排成m列。为了整齐，我们要把列按长度的下降次序排列（实际为非升次序）；而且长度差不多相等也就是任何两列之差不大于一行文本。如果把37行文本分为5列，我们会因此更愿意选择右边的排列：3224168312315730221463729211353628201243527191133426181023325179158888linelinelinelinel

26、inelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelineline1683730231573629221463528211353427201243326191133225181023124179177788linelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelinelin

27、elinelinelinelinelinelinelinelinelinelinelinelineDepartment of Computer Science & Technology2021-11-2631MOD: MOD: 二元运算二元运算n此外我们应该按列分配各行文本首先决定多少行进入第一列，然后考虑第二列，第三列，等等，因为这是人们的阅读习惯。逐行分配能够在每列中得到正确的行数，但是次序不对。（我们这样得到的排列和上图右边类似，但是列1将包含行1，6，11，36而不是要求的行1，2，3，8。）n虽然不能用逐行分配对策，但它确实告诉我们在每列中应该放入多少行。如果n不是m的倍数，

28、那么逐行分配过程清楚地表明每个长列应该包含 行，而每个短列应该包含 行。这样长列恰好有n mod m个（而且结果表明，短列恰好有n mumble m个）。/n m/n mDepartment of Computer Science & Technology2021-11-2632MOD: MOD: 二元运算二元运算n让我们推广这些名词，用事物和组来代替行和列。我们刚才已经判断出，第一组将包含 个事物；所以下面的连续分配机制应该有效：当m0时，为了把n个事物分配为m组，首先把 个事物放入一组，然后反复进行下列过程：把余下的nn 个事物放入mn1个其他组中。n例如，若n314，m6，分配方

29、案如下：n这是行得通的。尽管除数在分配过程中一直在改变，我们仍然取得了大小接近相同的组。/n m/n m/n m52152522104523156524208535261536314 /groupsthingsgroups remaining thingsremainingDepartment of Computer Science & Technology2021-11-2633MOD: MOD: 二元运算二元运算n这种方法为什么有效呢？一般我们可以假设nqmr，其中q ，rn mod m。如果r0，处理很简单：我们把 q个事物放入第一组，且用nnq替换n，把剩下的nqm个事物放入余下