《数学外文翻译外文文献英文文献具体数学》由会员分享，可在线阅读，更多相关《数学外文翻译外文文献英文文献具体数学（17页珍藏版）》请在金锄头文库上搜索。
1、Concrete MathematicsR. L. Graham, D. E. Knuth, O. Patashnik?Concrete Mathematics?，1.3 THE JOSEPHUS PROBLEMR. L. Graham, D. E. Knuth, O. PatashnikSixth printing, Printed in the United States of America 1989 by Addison-Wesley Publishing Company，Reference 1-4 pages具体数学R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克?具体数学?，1.3
2、，约瑟夫环问题R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克第一版第六次印刷于美国，韦斯利出版公司，1989年，引用8-16页1. 递归问题本章研究三个样本问题。这三个样本问题给出了递归问题的感性知识。它们有两个共同的特点：它们都是数学家们一直反复地研究的问题；它们的解都用了递归的概念，按递归概念，每个问题的解都依赖于相同问题的假设干较小场合的解。2. 约瑟夫环问题我们最后一个例子是一个以Flavius Josephus命名的古老的问题的变形，他是第一世纪一个著名的历史学家。据传说，如果没有Josephus的数学天赋，他就不可能活下来而成为著名的学者。在犹太|罗马战争中，他是被罗马人困在一个
3、山洞中的41个犹太叛军之一，这些叛军宁死不屈，决定在罗马人俘虏他们之前自杀，他们站成一个圈，从一开始，依次杀掉编号是三的倍数的人，直到一个人也不剩。但是在这些叛军中的Josephus和他没有被揭发的同伴觉得这么做毫无意义，所以他快速的计算出他和他的朋友应该站在这个恶毒的圆圈的哪个位置。在我们的变形了的问题中，我们以n个人开始，从1到n编号围成一个圈，我们每次消灭第二个人直到只剩下一个人。例如，这里我们以设n= 10做开始。这时的消灭顺序是2, 4, 6, 8, 10, 3, 7, 1, 9。所以编号是5的人活下来了。这个问题：就是定位最后活下来的人的数字J(n)。我们刚刚看到的是J(10) =
4、 5的情况。我们可能会推测当n是偶数的时候J(n) =n=2；而且当n= 2的时候结论验证了假设：J(2) = 1。但是其他一些数字比拟小的情况告诉我们|当n= 4和n= 6的时候这个假设错误了。于是我们回到了起点；让我们试着来个更好的猜测。呃.，J(n)看起来总是奇数。而且事实上，这个现象的原因是：围成的圆圈的第一轮消灭了所有的编号是偶数的人。之后我们又回到了与我们开始的时候类似的情形，除了人数只有原来一半的人，而且他们的编号改变了。所以，让我们假设最开始有2n个人，在第一轮结束后，我们剩下而且3将是下一个出局的。这个就像是以n个人开始的情况，除了每个人的编号变为两倍减一。那就是，J(2n)
5、 = 2J(n)-1; 当n 1:我们现在可以快速的计算一下当n比拟大的时候的值。例如，我们知道J(10) = 5，所以J(20) = 2J(10)-1 = 2*5-1 = 9:同样可知J(40) = 17，进一步我们可以推算出J(5*2M)=2M+1 +1但是，奇数的情况呢？当有2n+ 1个人的时候，编号是1的人会在第2n个人出局后紧接着出局，然后，我们剩下我们再次获得了形如n个人的情况，但是这次他们的编号是两倍加一。所以J(2n+ 1) = 2J(n) + 1; 当n 1;与等式J(1) = 1组合，我们得到一个定义了J的所有取值的递推式:J(1) = 1;J(2n) = 2J(n)-1;
6、 当n 1; J(2n+ 1) = 2J(n) + 1; 当n 1;这个公式不是从J(n-1)计算J(n)，这个递归式更加的“高效，因为他以2为因子使n递减了一半或更多。我们可以计算J(1;000;000)，如上所示，我们只要应用19次(1)式。但是，我们依旧要寻找一个闭合形式的公式，因为那样会更加快速和更有意义。总之，这是非常重要的事情。用我们的递归式，我们可以很快地建造一张较小取值的表。可能我们可以通过这张表看出模式并猜出结果。瞧！看起来我们可以以2的幂分组(通过表中的竖线)；在每组的开始，J(n)总是1，而且在一组内以2递增。所以，如果我们把n写成形如n=2M+J的公式，当2M是不超过n
7、的2的最大次幂，且l是剩余的数。这样我们的递归式的解法看起来是J(2M+L)=2L+1 当m0且0L2M 2(注意如果2Mn2M+1, 那么余下的数l =n-2M 满足不等式0L0且2M+L=2n那么l是偶数。且通过(1)式和归纳法假设可得J(2M+L)=2J(2M-1+L/2)-1=2(2L/2+1)-1 = 2l+ 1;这个就是我们想要的。奇数的情况证明方法类似，当2M+L=2L+1。我们可能也注意到式子(1)还表达了这样一个关系J(2n+1)-J(2n)=2总之，这个数学归纳法证明完毕，且(2)式被证明了。为了展示解法(2)式，让我们来计算一下J(100)。在这个例子中，我们有100 =
8、26+ 36，所以J(100) = 2*36 + 1 = 73现在，我们解决了艰难的局部(解决问题)。我们再说点轻松的：每解决一个问题都可以泛化，使得可以应用一大类问题。当我们已经掌握一项技巧，完整的研究它，看看借助它我们可以走多远是非常值得的。所以，在这节的余下局部，我们将会研究我们的解法(2)式以及研究递归式(1)的一些扩展。这些研究将会展示出所有这样问题的结构和根底。在我们寻找解法的时候，2的幂起到了重要的作用，所以很自然的，我们想用2的基数表示n和J(n)。假设n的二进制表达式是n=(bmbm-1.b1b0)2;也就是n=bm2m+bm-12m-1+.b12+b0每个bi 取值是0或1
9、，且最高位bm 是1. 回想一下n=2M+L我们先后得到如下表达式，n=(1bm-1bm-2.b1b0)2L=(0bm-1bm-2.b1b0)22L=( bm-1bm-2.b1b0)22L+1=(bm-1bm-2.b1b01)2J(n)= (bm-1bm-2.b1b0m)2(最后一个式子是因为J(n) = 2l+ 1以及bm=2L+1以及bm=1。) 我们已经证明J(bm-1bm-2.b1b0)2)= (bm-1bm-2.b1b0m)2; (3)这样，用计算机编程的专业术语解释就是我们从n计算J(n)只需要做一位循环左移！多么神奇。例如，如果n= 100 =(1100100)2, 那么J(n)
10、 = J(1100100)2=(1001001)2, 也就是64 + 8 + 1 = 73。如果我们从一开始就一直用二进制方法研究，我们可能会立即就发现这个模式。如果我们以n个人开始，迭代J函数m+ 1次，计算机将会作m+ 1次的一位循环左移；所以当n是一个(m+ 1)位的数字，我们可能希望最后又得到n。但是实际上不是。举个例子，当n= 13， 我们有J(1101)2=(1011)2, 但是之后J(1011)2=(111)2, 这时处理过程中断了；当0出现在首位的时候会被忽略。事实上，根据定义，J(n)必须总是n, 因为J(n)是存活着的人的编号；所以如果J(n) n我们决不可能通过继续迭代回
11、溯到n。 重复的应用过程J产生一个递减的序列值，最终到达一个“固定的值，也就是当J(n) = n的时候。这种循环位移特点使得很容易观察出来这个固定的值将会是多少：迭代这个方法足够多的次数，总会产生每个位都是1的模式，其值为 2v(n)-1 , 当v(n)是1-位在整个二进制序列的出现的次数。所以，当v(13) = 3，我们有 2或更多的JJ(J(.J (13).) = 23 1 = 7;同样的8或更多J(J(.J.) = 210 1 = 1023;很奇怪，但是是正确的。让我们回到这个问题的最初猜测，也就是当n是偶数的时候J(n) =n=2。一般而言这个结论是明显但不正确的，但我们现在可以看看它
12、到底在什么情况下是正确的： J(n) = n=2;2l+ 1 =(2m+l)/2l =1/3(2m-2)如果这个式子l =1/3(2m-2) 是一个整数，那么n=2m+l将会是一个解，因为l会小于2m 不难验证当m是奇数，2m-2是3的倍数，但当m是偶数的时候不成立。(我们将会在第四章研究这个问题。)所以有无穷多个解可以满足J(n) =n/2，以如下形式开头：注意这个模式中最右边的一列。这些二进制数一位循环左移的结果和一位循环右移的结果一样。(结果都是减半)。好了，我们对函数J了解的全面了；下一步是将这个问题一般化。如果我们的问题得到一个像(1)的递归式，但是常数不同，将会发生什么？我们可能就
13、没有这么幸运能猜到答案了，因为答案可能很复杂。让我们通过引入常量，和 12 研究这个问题，并尝试为较一般的递归式找到一个闭合形式的公式f (1) = ;f (2n) = 2f (n) + , 当 n 1;4f (2n + 1) = 2f (n) + , 当 n 1.(我们开始的递归式中 = 1， = 1，且 = 1。)以f (1) = 开始计算，我们可以构建出来接下来的广义形式递归式的对n取值较小的表： 可以看出来的系数是小于n的最大的2的幂。另外，在2的幂的范围内，的系数每次减1，直到0。而的系数那么从0开始每次增加1。所以，我们的表达式f(n)的形式是f(n) = A(n) + B(n)
14、+ C(n), 6通过与之相关的，和别离，可得A(n) = 2m;B(n) = 2m 1 l;C(n) = l.7这里跟以往一样，n = 2m + l且0 l 2m，当n 1。使用数学归纳法证明(6)式和(7)式并不是一件非常艰难的事情，但是这个计算过程是繁杂而且没有技术含量的。而且现在有个更好的方法来计算，通过带入选定具体的值，然后比照计算他们。13让我们通过具体的例子 = 1， = = 0来说明这个方法，当假设f(n)等于A(n)：递归式(4)变为A(1) = 1;A(2n) = 2A(n)；当 n 1;A(2n + 1) = 2A(n)；当 n 1;可以肯定的是,A(2m + l) = 2m是正确的(通过对m进行数学归纳法可以证明)。接下来，我们将反用递归式(4)以及解法(6)式。我们以一个简单的f(n)函数开始，看看是否存在常数(, , )可以确定它。将常函数f(n) = 1带入递归式(4)可得1 = ;2 = 2 1 + ;3 = 2 1 + ;所以取值(, , ) = (1, 1, 1)满足这些等式，且有A(n) B(n) C(n) =f(n) = 1。同样我们可以带入f(n) = n：1 = ;
