数学 外文翻译 外文文献 英文文献 具体数学.doc

Concrete MathematicsR. L. Graham, D. E. Knuth, O. PatashnikConcrete 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，约瑟夫环问题R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克第一版第六次印刷于美国，韦斯利出版公司，1989年，引用8-16页1. 递归问题本章研究三个样本问题。这三个样本问题给出了递归问题的感性知识。它们有两个共同的特点：它们都是数学家们一直反复地研究的问题；它们的解都用了递归的概念，按递归概念，每个问题的解都依赖于相同问题的若干较小场合的解。2. 约瑟夫环问题我们最后一个例子是一个以Flavius Josephus命名的古老的问题的变形，他是第一世纪一个著名的历史学家。据传说，如果没有Josephus的数学天赋，他就不可能活下来而成为著名的学者。在犹太|罗马战争中，他是被罗马人困在一个山洞中的41个犹太叛军之一，这些叛军宁死不屈，决定在罗马人俘虏他们之前自杀，他们站成一个圈，从一开始，依次杀掉编号是三的倍数的人，直到一个人也不剩。但是在这些叛军中的Josephus和他没有被告发的同伴觉得这么做毫无意义，所以他快速的计算出他和他的朋友应该站在这个恶毒的圆圈的哪个位置。在我们的变形了的问题中，我们以n个人开始，从1到n编号围成一个圈，我们每次消灭第二个人直到只剩下一个人。例如，这里我们以设n= 10做开始。这时的消灭顺序是2, 4, 6, 8, 10, 3, 7, 1, 9。所以编号是5的人活下来了。这个问题：就是定位最后活下来的人的数字J(n)。我们刚刚看到的是J(10) = 5的情况。我们可能会推测当n是偶数的时候J(n) =n=2；而且当n= 2的时候结论验证了假设：J(2) = 1。但是其他一些数字比较小的情况告诉我们|当n= 4和n= 6的时候这个假设错误了。于是我们回到了起点；让我们试着来个更好的猜测。呃.，J(n)看起来总是奇数。而且事实上，这个现象的原因是：围成的圆圈的第一轮消灭了所有的编号是偶数的人。之后我们又回到了与我们开始的时候类似的情形，除了人数只有原来一半的人，而且他们的编号改变了。所以，让我们假设最开始有2n个人，在第一轮结束后，我们剩下而且3将是下一个出局的。这个就像是以n个人开始的情况，除了每个人的编号变为两倍减一。那就是，J(2n) = 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; 当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的2的最大次幂，且l是剩余的数。这样我们的递归式的解法看起来是J(2M+L)=2L+1 当m0且0L<2M （2）(注意如果2Mn<2M+1, 那么余下的数l =n-2M 满足不等式0L<2M+1-2M=2M.)我们现在必须证明(2)式。如我们以前使用的数学归纳法一样，但是这次我们的数学归纳是基于变量m的。当m= 0我们一定有l = 0；因此(2)式的基础就变成了J(1) = 1，这时是正确的。通过l是奇数还是偶数，这次的归纳证明分两部分。如果m >0且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 =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，且最高位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) = 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我们决不可能通过继续迭代回溯到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(101101101101011)2.) = 210 1 = 1023;很奇怪，但是是正确的。让我们回到这个问题的最初猜想，也就是当n是偶数的时候J(n) =n=2。一般而言这个结论是明显但不正确的，但我们现在可以看看它到底在什么情况下是正确的： 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)的递归式，但是常数不同，将会发生什么？我们可能就没有这么幸运能猜到答案了，因为答案可能很复杂。让我们通过引入常量，和 12 研究这个问题，并尝试为较一般的递归式找到一个闭合形式的公式f (1) = ;f (2n) = 2f (n) + , 当 n 1;（4）f (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) + 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 = ;2n = 2 · n + ;2n + 1 = 2 · n + ;当 = 1， = 2且 = 1的时候，这些等式对于所有的n成立，所以我们不必用数学归纳法证明这些参数满足f(n) = n。我们已经知道f(n) = n在这个例子中是解，因为递归式(4)为每个n的取值唯一的定义了f(n)。现在我们已经完成了核心的部分！我们已经表示了(6)式的函数A(n)，B(n)以及C(n)，他们解决了广义的(4)式，满足公式A(n) = 2m,当 n = 2m + l且0 l < 2m;A(n) B(n) C(n) = 1;A(n) + C(n) = n.我们的对于(7)式的推测可以通过如下的式子立即解出来：C(n) = n A(n) = l以及B(n) = A(n) 1 C(n) = 2m 1 l。这个过程已经接近于展示一个惊奇、有用的repertoire method来解决递归式问题。首先，我们要寻找我们的解法中已知的通用参数；这给予了我们能解得各个部分的特例。我们需要跟独立的参数数量(在这个例子中是三个，和)同样多的独立的特解。练习16和20提供了更多的相关例子。我们知道原来的递归式J有一个神奇的解法，也就是二进制：J (bmbm1.b1b0)2 = (bm1.b1b0bm)2, 当 bm = 1.那么，广义的Josephus递归式也能如此神奇么？当然，为什么不呢？我们可以把这个广义的递归式(4)重写成如下形式f(1) = ;f(2n + j) = 2f(n) + j, 当 j = 0, 1且n （8）若我们设0 = 且1 = 。这个递归式的展开式，二进制表示如下：f (bmbm1.b1b0)2 = 2f (bmbm1.b1)2 + b0 = 4f (bmbm1.b2)2 + 2b1 + b1 = 2mf (bm)2 + 2m1bm1 + . . + b0 = 2m + 2m1bm1 + . . .+ b0.假设我们现在不管162的基数标记，随便让数字取代二进制中的0和1。这样就会得到 f (bmbm1.b1b0)2 = (bm1bm2 . . . b1 + b0)2. （9）好了。如果我们把(5)式换一种写法17，我们会更早些看到这个模式：举个例子，当n = 100 = (1100100)2的时候，我们原来的Josephus取值为 = 1， = 1，且 = 1带入后构造结论跟之前一样。这个循环左移的特点之所以能满足是因为每个二进制数据块(10.000)2在表示n的时候的时候转化为(1 1. 1 1)2 = (0 0 . 0 1)2.所以我们改变曾给出的对递归式(8)的精简的解法(9)式。如果我们已经不受约束了，我们就可以使它更加一般化18，所以递归式f(j) = aj,当1 j < d;f(dn + j) = cf(n) + j 当0 j < d且n 1, （10）如同之前的那个，除了我们的起始的数字的基数是d，产生值是基数c。所以，这个基数改变了的解法是f (bmbm1.b1b0)d = (bmbm1bm2 . . . b1b0)c. （11）例如，假设一个幸运的巧合19下我们获得了一个递归式f(1) = 34f(2) = 5,f(3n) = 10f(n) + 76 当n 1f(3n + 1) = 10f(n) 2 当n 1f(3n + 2) = 10f(n) + 8, 当n 1假设我们想计算f(19)。这里我们有d = 3和c = 10。现在19 = (201)3，通过这个基数改变了的解法，我们把数字一位一位的替换，把每个数字从基于基数3的表示方法替换为基数是10的。所以，使2变为5，并假设0和1变成76和-2，代入f(19) = f (201)3 = (576 2)10 = 1258,这就是我们的结果。所以Josephus以及犹太罗马战争留给我们一些有趣的广义递归式。1. Recurrent ProblemsTHIS CHAPTER EXPLORES three sample problems that give a feel forwhat's to come. They have two traits in common: They've all been investi-gated repeatedly by mathematicians; and their solutions all use the idea ofrecurrence, in which the solution to each problem depends on the solutionsto smaller instances of the same problem.1.3 THE JOSEPHUS PROBLEMIn our Our nal introductory example is a variant of an ancient problem named for Flavius Josephus, a variation, we start withnpeople numbered 1 tonaround a circle, and we eliminate everysecondremaining person until only one survives. For example, here's the starting conguration forn=10:The elimination order is2, 4, 6, 8, 10, 3, 7, 1, 9, so 5survives. The problem:Determine the survivor's number,J(n).We just saw thatJ(10) =5. We might conjecture that J(n) =n=2when nis even; and the case n=2supports the conjecture: J(2) = 1. But a few other small cases dissuade us | the conjecture fails forn=4andn=6.It's back to the drawing board; let's try to make a better guess. Hmmm : : :J(n)always seems to be odd. And in fact, there's a good reason for this: The rst trip around the circle eliminates all the even numbers. Furthermore, if nitself is an even number, we arrive at a situation similar to what we began with, except that there are only half as many people, and their numbers have changed.So let's suppose that we have2npeople originally. After the rst go-round, we're left withnd3will be the next to go. This is just like starting out withnpeople, except that each person's number has been doubled and decreased by1. That is,J(2n) = 2J(n)-1; 当n 1:We can now go quickly to largen. For example, we know that J(10) =5, soJ(20) = 2J(10)-1 = 2*5-1 = 9:Similarly J(40) = 17，and we can deduce that J(5*2M)=2M+1 +1But what about the odd case? With2n+1 people, it turns out that person number1is wiped out just after person number 2n, and we're left with Again we almost have the original situation withnpeople, but this time their numbers are doubled andincreased by1. ThusJ(2n+ 1) = 2J(n) + 1; for n 1;Combining these equations with J(1) = 1 gives us a recurrence that denes J in all cases:J(1) = 1;J(2n) = 2J(n)-1; for n 1; J(2n+ 1) = 2J(n) + 1; for n 1;Instead of gettingJ(n)from J(n-1), this recurrence is much more effcient,"because it reducesnby a factor of2or more each time it's applied. We could computeJ(1000000), say, with only 19 applications of (1.8). But still, we seek a closed form, because that will be even quicker and more informative. After all, this is a matter of life or death.Our recurrence makes it possible to build a table of small values very quickly. Perhaps we'll be able to spot a pattern and guess the answer.Voila! It seems we can group by powers of 2 (marked by vertical lines in the table);J(n) is always 1at the beginning of a group and it increases by2 within a group. So if we writenin the form n=2M+J, where 2M is the largest power of 2not exceedingnand wherel is what's left, the solution to our recurrence seems to beJ(2M+L)=2L+1 for m0 and 0L<2M （2）(Notice that if 2Mn<2M+1, the remainder l =n-2M satises 0L<2M+1-2M=2M.)We must now prove (2). As in the past we use induction, but this timethe induction is on m. When m=0we must havel =0; thus the basis of reduces to J(1) = 1, which is true. The induction step has two parts, depending on whetherl is even or odd. If m >0and2M+L=2n , then l is even andJ(2M+L)=2J(2M-1+L/2)-1=2(2L/2+1)-1 = 2l+ 1;by (1) and the induction hypothesis; this is exactly what we want. A similar proof works in the odd case, when 2M+L=2L+1。We might also note that(1) implies the relationJ(2n+1)-J(2n)=2Either way, the induction is complete and (2) is established.To illustrate solution (1.9), let's compute J(100). In this case we have100 =26+ 36, so J(100) = 2*36 + 1 = 73Now that we've done the hard stuff (solved the problem) we seek thesoft: Every solution to a problem can be generalized so that it applies to a wider class of problems. Once we've learned a technique, it's instructive to look at it closely and see how far we can go with it. Hence, for the rest of this section, we will examine the solution (2) and explore some generalizations of the recurrence (1). These explorations will uncover the structure that underlies all such problemsPowers of 2 played an important role in our finding the solution, so it'snatural to look at the radix2 representations of nandJ(n). Suppose n'sbinary expansion isn=(bmbm-1.b1b0)2;that is,n=bm2m+bm-12m-1+.b12+b0where each bi is either 0or1and where the leading bit bm is 1. Recalling that n=2M+L, we have, successively, 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(The last step follows because J(n) = 2l+ 1 and because bm=2L+1 and bm=1。)We have proved thatJ(bm-1bm-2.b1b0)2)= (bm-1bm-2.b1b0m)2; (3)that is, in the lingo of computer programming, we get J(n) from nby doing a one-bit cyclic shift left! Magic. For example, if n= 100 =(1100100)2 then J(n) = J(1100100)2=(1001001)2, which is 64+8+1=73. If we had been working all along in binary notation, we probably would have spotted this pattern immediately.if we start with nand iterate theJ function m+1 times, we're doing m+1 one-bit cyclic shifts; so, sincenis an (m+1)-bit number, we might expect to end up with nagain. But this doesn't quite work. For instanceif n=13 we have J(1101)2=(1011)2, but then J(1011)2=(111)2, and the process breaks down; the 0disappears when it becomes the leading bit.In fact, J(n) must always be n, by denition, sinceJ(n) is the survivor's number; hence if J(n) < nwe can never get back up tonby continuing to iterate.Repeated application ofJproduces a sequence of decreasing values that eventually reach a "fixed point," where J(n) = n The cyclic shift property makes it easy to see what that fixed point will be: Iterating the function enough times will always produce a pattern of all1's whose value is 2v(n)-1 where v(n) is the number of 1bits in the binary representation ofn. Thus, since v(13) = 3，we have2 or more JJ(J(.J (13).) = 23 1 = 7;Similarly8or moreJ(J(.J(101101101101011)2.) = 210 1 = 1023;Curious, but trueLet's return briefly to our rst guess, thatJ(n) =n/2whennis even. This is obviously not true in general, but we can now determine exactly when it is true:J(n) = n=2;2l+ 1 =(2m+l)/2l =1/3(2m-2)If this number l =1/3(2m-2) is an integer, then n=2m+lwill be a solution, becauselwill be less than 2m. It's not hard to verify that 2m-2 is a multiple of3whenmis odd, but not when mis even. (We will study such things in Chapter 4.) Therefore there are innitely many solutions to the equationJ(n) =n/2 beginning as follows:Notice the pattern in the rightmost column. These are the binary numbers for which cyclic-shifting one place left produces the same result as ordinary-shifting one place right (halving).OK, we understand theJfunction pretty well; the next step is to general-ize it. What would have happened if our problem had produced a recurrence that was something like (1), but with diferent constants? Then we might not have been lucky enough to guess the solution, because the solution might have been really weird. Let's investigate this by introducing constants ， and and trying to nd a closed form for the more general recurrencef (1) = ;f (2n) = 2f (n) + , for n 1;（4）f (2n + 1) = 2f (n) + , for n 1.(Our original recurrence had = 1， = 1 and = 1。) Starting with f (1) = and working our way up, we can construct the following general table for small values of n:It seems that s coecient is n's largest power of 2. Furthermore, between powers of2, s coecient decreases by 1down to0 and s increases by 1 up from0. Therefore if we express f(n) in the formf(n) = A(n) + B(n) + C(n), （6）by separating out its dependence on ， and , it seem