具体数学-第3章-整值函数(3.1节-3.3节)

第3章整值函数（IntegerFunctions）鞠成东E-mail：[e-mail].P.：15204679336整数函数简介整数是离散数学、组合数学的主要讨论对象。计算机系统中存储、处理和传输的信息实际上都是整数。在实际应用数学问题中，为了简化计算，我们也常常将分数或实数转换成整数。本章将主要讲解常用的“实——整”转换，及其数学属性和技巧。包括：上取整、下取整、模运算等。3.1FloorsandCeilings上取整（顶）和下取整（底）3.1顶和底•对任意实数x，下取整/上取整函数定义如下：：不大于x的最大整数——max{n|n=x}蓝实线：不小于x的最小整数——min{n|n=x}红虚线xxf(x)=xx=ex=-ef(x)x3210-1-2-3123-1-2-3取整函数的直观性质•因为下整函数总是位于对角线f(x)=x之下或者相交，所以有和。•当且仅当x为整数时，两个取整函数是相等的：•当x不是整数时，上取整恰好比下取整大1：•对角线上/下移1个单位，将完全在上/下取整函数之上/下：•两个取整函数是彼此关于原点对称的：xxxxxxxxx为整数不是整数xxx11xxxxxxxxx,f(x)=xx=ex=-ef(x)x3210-1-2-3123-1-2-3上下取整的基本规则•这些规则可以用于较为严格地证明关于取整函数的命题：1111nnxnxnxnnxxnxnxnxnnx其他性质•在加法运算中，整数项可以移进/移出取整函数：•但是在乘法运算中，一般不能移进/移出因子:例如对n=2、x=½，有•一般来说取整符号不容易操作，但在部分情形下可以略去。例如：xnnxxnnx,2212212102122121xnxnnxnxxnxnnxnx,,实数的整数部分与小数部分•x和之间的差称为x的小数部分，可以表示为：。其中被称为x的整数部分。•回顾加法操作中的整数移出/移入性质：如果n为任意的实数，等式还成立吗？xxxxxxnnxxnnx,otherwise.,1;1if,yxyxyxyxyxyx3.2Floor/CeilingApplications顶和底的应用3.2下取整/上取整的应用•𝒍𝒈𝟑𝟓等于多少？其值表示二进制的长度吗？提示：𝟐𝒎−𝟏≤𝒏𝟐𝒎;𝒎−𝟏=𝒍𝒈𝒏•𝒙是什么？•再看一个更难的问题：证明或推翻断言：𝒙=𝒙，实数𝒙≥𝟎3.2下取整/上取整的应用•推广此想法且证明更多的结果：设f(x)是任意连续的单调上升函数，而且当f为整数时必有x为整数。则可以得到：•例如f为线性函数（m、n为整数，n0）：)()(,)()(xfxfxfxfnmxnmxnmxnmx,3.2下取整/上取整的应用•设f(x)函数满足：(1)连续且单调递增；(2)若f(x)为整数则x必为整数。则有结论：•证明过程（以为例）：•首先有•当f(x)为整数时•当f(x)非整数时)()(,)()(xfxfxfxf)()()()(xfxfxfxfxx)()(int)(intxfxfxxxxf)()()()()()()(1)()()(,)(int|)(max0000000xfxfxfxfxfxffxffxffxfxxxfxzzfzff为非整数，因此有又，由于；，则设)()(xfxf如果条件2变成：若x为整数，则f(x)为整数。结论还成立吗？稍稍休闲一下……数学修炼的五境界数学工作的五个境界•第一境界给定一个论域明确的对象x，以及一个明确的断语P(x)，证明：P(x)为真。•第二境界给定一个明确的集合X，以及一个明确的断语P(x)，证明：对于所有的x∈X，P(x)为真。•第三境界给定一个明确的集合X，以及一个明确的断语P(x)，证明或者推翻：对于x∈X，P(x)为真。•第四境界给定一个明确的集合X，以及一个明确的断语P(x)，找到P(x)为真的充要条件Q(x)。•第五境界给定一个明确的集合X，找到关于其中元素的某个有趣的性质P(x)。底和顶的应用•尝试证明或推翻命题：𝑥=𝑥，实数𝑥≥0。解：𝑥=𝜋和𝑥=𝑒都成立，但𝑥=∅不成立。•那么上式成立的条件是什么？解：经观察：𝑚2𝑥𝑚2+1时不成立。成立条件是x是整数，或者𝑥不是整数。•闭区间、开区间、半开半闭区间所包含的整数个数问题。一个赌场里面的应用•具体数学俱乐部的娱乐场有一个轮盘赌，共有编号从1到1000的1000个位置。如果某次旋转得到的数n可以被它的立方根的下取整值除尽，也就是说，如果，则称n为赢者数，且娱乐场付给我们5元；否则称为输者数，且我们必须要付出1元，我们能够赢钱吗？•假设赢者数的数量为W，输者数的数量为L，则每次旋转的期望收益为nn\31000100061000)1000(510005赢者数的计算过程•结合Iverson约定，可以按部就班地分析此问题：1724314311331101/)1(,,1101)1(110001)1(10001\\1011012210122,32,33,,33,310001310001kkkmkmknmknknnkkkkkkkkkkkkmkkkmknkmnknknnknknnnW为赢者数轮盘赌问题的推广•下面进行推广。假设将1000变成任意的数N：容易知道，在一般的N上赢者数的数量为•因此，W在一般的N上为：14252311372143222313KKNKKKNKmKKNKmKkWmmNKk325212KKKNW取整运算的应用—实数的谱•我们定义实数α的谱为一个无限的整数多重集：•易证任意两个谱都不是相等的：α≠β意味着Spec(α)≠Spec(β)。•谱具有许多有趣的性质。在以下两个谱中，一个谱中没有的数字差不多都会在另一个中出现，但是没有在两个谱中同时出现的数字。（事实上可以严格证明，下面两个谱构成了正整数集的划分）,3,2,Spec,51,47,44,40,37,34,30,27,23,20,17,13,10,6,322,24,22,21,19,18,16,15,14,12,11,9,8,7,5,4,2,12SpecSpec3.3Floor/CeilingRecurrences下取整/上取整的递归3.3下取整/上取整的递归•下取整/上取整为递归关系的研究加入了很多有趣的问题。首先观察下面的递归方程：•例如K1=1+min(2K0,3K0)=3•序列的开始片断为1,3,3,4,7,7,7,9,9,10,13,……在发现确切的相关文献之前，本书作者谨慎地称这些数为Knuth数（仅此而已，后面没有了……）32102,2min11nnnKKKK下取整/上取整的递归•在“分而治之”算法中，常见与取整有关的递归关系。•例如，对n条记录进行排序，一种方法就是将其分为两个几乎等规模的部分，大小分别为，也就是说•在对每部分独立完成排序之后，最多再进行n–1次比较，就可以把两部分记录合并为完整的次序。因此，总计最多需要进行f(n)次比较：2/,2/nn2/2/nnn)1()2/()2/()(0)1(nnfnfnff下取整/上取整的递归•回顾Josephus问题的递归方程：•下面考虑更接近原始版本的Josephus问题：每次排除剩下的第三个人，而不是第二个。如果按照第一章的方法来求解，最终得到：•其中mod函数将在后面碰到。根据nmod3=0、1或2，将得到αn=–2、+1或-1/2。但是，从形式上来讲，这个方程太过复杂，很难做出进一步分析。nnJnJ12/2)(1mod3223)(33nnJnJn下取整/上取整的递归•换一种视角更便于分析。每次轮转时都对幸存者重新编号。例如，1和2变成n+1和n+2，然后跳过已选的3；4和5变成n+3和n+4，然后跳过6；3k+1和3k+2变成n+2k+1和n+2k+2，然后跳过3k+3。最后3n幸存。下面为n=10的例子•第k个被排除的人的编号为3k。所以如果能算出编号3n的最初编号，就可以找出幸存者。302928272625242322212019181716151413121110987654321下取整/上取整的递归•如果Nn，则编号N一定有前一次的编号。假设N=n+2k+1或N=n+2k+2(因此有)，则此前编号为3k+1或3k+2（排除掉了k个人）。也就是说，N的前一次编号为3k+(N–n–2k)=k+N–n。由此，可以按如下方式计算幸存者的编号：这不是的封闭形式解，而且也不是规范的递归方程。但是可以在很大的n上快速地完成求解。2/1nNk.:;21:dowhile;3:3NNJnNnNNnNnNNJ3下取整/上取整的递归•更进一步，用D=3n+1–N替换N，可以再简化一下。于是N的计算公式变成•由此将算法改写成23222213211313:DDDDDDnDnnDnnDnnD.13:;23:do2while;1:3DnnJDDnDD下取整/上取整的递归•现在算法更为简洁，涉及n的计算步骤非常简单。事实上，如果每次选出的是第q个人，幸存者编号也可以同样地计算：•例如对于q=2时，当时，D在循环结束后变成；因此有.1:;1:do)1(while;1:DqnnJqqDDnqDDqlnm212m1221)2(2)(12llnJmm下取整/上取整的递归•对一般的每次选出第q个人的问题，算法计算出D的序列，该序列可以由下面的递归方程定义：•一般来说这些序列没有很直观的特点，因此或许没有简单的封闭形式解。如果将D看做“常见”函数，则一般Josephus问题的解可以简写做：)(1)()(01:;1qnqnqDqqDDnqDmkDqnqmqk)1(|min,1)()(这里