具体数学--毕业论文外文翻译.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 8-16 pages 具体数学R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克具体数学，1.3，约瑟夫环问题R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克第一版第六次印刷于美国，韦斯利出版公司，1989年，引用8-16页1. 递归问题本章主要研究三个样本问题,这三个问题给出了递归问题的感性知识.它们有两个共同特点:即都是数学家们一直研究的问题;它们的解都用了递归的概念，按照递归概念,每个问题解都依赖于相同的问题的若干个较小场合的解.2. 约瑟夫环问题 我们最后一个例子是一个以Flavius Josephus命名的古老的问题变形,他是第一世纪一位著名的历史学家.据传说,如果没有Josephus的数学天赋，他就不可能活下来然后成为著名的学者,当时在犹太罗马战争中,他是被困在一个山洞中的41个犹太叛军其中一人，这些叛军宁死不屈，都决定在罗马人俘虏他们之前自刎，他们站成一圈,从1开始,依次杀掉编号是3的倍数的那个人，直到一个人也不剩.但在这些叛军中Josephus和他的同伴觉得这么做没有意义，所以他就快速的计算出他和他的朋友应该站在这个圈的哪个位置.在这个变形的问题中,我们以个人开始,从1到编号围成一圈，每次消灭第二个人一直到只剩下一个人.例如,在这里我们以设开始. 这时的消灭顺序为,.所以编号是的人活了来.这个问题:就是定位了最后活下来的那个人的数字.我们刚刚看到是的情况.我们可能会推测当是偶数的时候;而且当的时候结论同样验证了假设:.但是另外一些数字比较小的情况告诉我们当的时候这个假设是错误的.于是我们又回到了起点;让我们尝试着来个更好的猜测.看起来总是奇数.这个现象的原因是：围成的圈的第一轮消灭了所有编号是偶数的人.之后我们又回到了与我们开始时候类似情形，除了人数只有原来一半，而且他们的编号也改变了.所以,让我们假设最开始有个人,在第一轮消灭结束后,我们剩下而且编号3将是下一个出局的.这个就像是以个人开始的情况了，除了每个人的编号变为两倍减一.就是，;当：现在我们可以快速的去计算一下当比较大的时候的那个值,例如,我们知道,所以：同样知J()=,从而我们可以推算出 但是,奇数的情况是怎么样的呢？当有个人的时候，编号是的那人会在第个人出局后紧接就会出局,然后,我们剩下我们再次获得形如个人的情况,但是这次他们的编号变为两倍加一.所以;当；与等式(1)=1组合,我们得到一个定义的所有取值递推式:；;当；当这个公式不是从计算,这个递归式更加的“高效”了，因为它以为因子使递减了一半或更多.我们再次可以计算(;),如上所示，我们只要应用次(1)式.但是，我们仍然要寻找一个闭合形式的公式，因为那样会更加快速和有意义.用我们的递归式,可以很快地建造一张较小取值的表.我们可以通过这张表看出模式并猜出结果, 从上我们可以以2的幂分组(通过表中的竖线);在每组的开始,总是1,而且在一组内以递增.所以，如果把写成形如的公式,当是不超过的2的最大次幂,且是剩余的数.这样我们的递归式的解法是(+)=2+1 当0且0 （2）(注意如果, 那么余下的数l =- 满足不等式02M+1-=.) 我们现在必须证明(2)式.如我们使用的数学归纳法一样，但是这次数学归纳是基于变量的.当=0我们一定有;因此(2)式的基础就变成(1)=1,这时是正确的.通过l是奇数还是偶数，这次的归纳证明分为两部分.如果且+=那么l是偶数.且通过(1)式和归纳法假设可得(+)=2(+/2)-1=2(2/2+1)-1 = 2+ 1;这个就是我们想要的.奇数的情况证明方法和它类似,当+=2+1.我们可能也注意到了式子(1)还表达这样一个关系(2+1)-(2)=2 总之，这个数学归纳法证明完毕,且(2)式被证明了.为了展示解法(2)式,来计算一下.在这个例子中,我们有 =+,所以(100) = 2*36 + 1 = 73. 现在，我们解决了艰难的部分(解决问题.我们再来说点轻松的：每解决一个问题都可以泛化，使得可以应用到一大类问题.当已经掌握一项技巧，完整的去研究它，看看借助它我们可以走多远是非常有意义的.所以，在这节的余下部分，我们将会研究解法(2)式以及研究递归式(1)的一些扩展.这些研究将展示出所有这样问题的结构和基础.在我们寻找解法的时候，2的幂起到了重要作用,所以很自然的,我们想用2的基数表示和(),假设的二进制表达式为;也就是=,每个的取值是0或，且最高位是1.回想一下=+我们先后得到如下表达式，22+1(n)(最后一个式子是因为以及.) 我们已经证明; (3)这样，用计算机编程解释就是我们从计算()只需要做一位循环左移！多么神奇.例如，如果, 那么()=(1100100)2=(1001001)2, 也就是64 + 8 + 1 = 73.如果我们从开始就一直用二进制方法研究,我们可能会立即发现这个模式.如果我们以个人开始,迭代函数次,计算机将会作次的一位循环左移；所以当是一个()位的数字，我们可能希望最后又得到.但是实际上不是的.举个简单例子,当=13，我们有,但是之后, 这时处理过程中断了;当出现在首位的时候会被忽略掉.事实上,根据定义,()必须总是, 因为()是存活着的人的编号;所以如果()我们不可能通过继续迭代溯回到. 重复的应用过程产生一个递减的序列值,最终到达一个“固定的值”,也就是当() =的时候.这种循环位移特点使得很容易观察出这个固定的值将会是多少:迭代这个方法足够多次数，总会产生每个位都是1的模式，其值为-1,当v()是1位在整个二进制序列的出现的次数.所以，当，我们有2或更多的(. (13).) = 23 1 = 7;同样的8或更多(.(101101101101011)2.) = 210 1 = 1023;很奇怪,但是是正确的.让我们回到这个问题最初猜想,也就是当n是偶数的时候()=2.一般而言这个结论明显但不正确,我们现在可以看看它到底在什么情况下是正确的： () =2; 2l+ 1 =(+l)/2 l =1/3(-2)如果这个式子l =1/3(-2) 是一个整数，那么=+l将会是一个解，因为会小于 不难验证当是奇数，-2是的倍数，但当是偶数的时候不成立.(我们将会在第四章研究这个问题.)所以有无穷多个解可以满足() =/2，以如下形式开头： 注意这个模式中最右边的一列.这些二进制数一位循环左移结果和一位循环右移的结果一样.(结果都是减半).好了,我们对函数了解的全面;下一步是将这个问题一般化.如果我们的问题得到一个像(1)的递归式,但是常数不同，将会发生什么？我们可能就没有这么幸运能猜到答案了,因为答案可能很复杂.让我们通过引入常量,和研究这个问题.并尝试为较一般的递归式找到一个闭合形式的公式(1) = ;(2) = 2 () + , 当 1; （4）(2 + 1) = 2 () + , 当 1.(我们开始的递归式中，且.)以开始计算,我们可以构建出来接下来的广义形式递归式的对取值较小的表： 可以看出来的系数是小于的最大的2的幂.另外,在2的幂的范围内,的系数每次减,直到0.而的系数则从0开始每次增加1.所以,我们的表达式()的形式是() = ()+()+(), （6）通过与之相关的,和分离,可得() = 2;() = 2;() = l.（7）这里跟以往一样,= 2+ l且0 l 2,当1. 使用数学归纳法证明(6)式和(7)式并不是一件非常艰难的事情,但是这个计算过程是繁杂而且没有技术含量的.而且现在有个更好的方法来计算,通过带入选定具体的值,然后对比计算他们.13让我们通过具体的例子 = 1, = = 0来说明这个方法,当假设()等于()：递归式(4)变为(1) = 1;(2) = 2();当1;(2 + 1) = 2();当1;可以肯定的是,(2+ l) = 2是正确的(通过对进行数学归纳法可以证明).接下来，我们将反用递归式(4)以及解法(6)式.我们以一个简单()函数开始,看看是否有常数(, , )可以确定.将常函数() = 1带入递归式(4)可得1 = ;2 = 21 + ;3 = 21 + ;所以取值(, , ) = (1,1,1)满足这些等式，且有() () ()=()=1.同样我们可以带入() =：1 =;2= 2+;2+ 1 = 2+ ;当 = 1, = 2且 = 1的时候，这些等式对于所有的成立，所以我们不必用数学归纳法证明这些参数满足() =.我们已经知道() =在这个例子中是解，因为递归式(4)为每个的取值唯一的定义了().现在我们已经完成了核心的部分！我们已经表示(6)式的函数(),()以及()，他们解决了广义的(4)式，满足公式() = 2,当= 2+ l且0 l 2;() () () =1;() +() =.我们的对于(7)式的推测可以通过如下的式子立即解出来:() =() = l以及() =()1C() = 2.这个过程已经接近于展示一个惊奇、有用的repertoire method来解决递归式问题.首先，我们要寻找我们的解决方法中已知的通用参数;这给予了我们能解得各个部分的特例.我们需要跟独立参数数量(在这个例子中是三个,和)同样多的独立的特解.练习16和20提供了更多的相关例子.我们知道原来的递归式J有一个神奇的解法,也就是二进制： ()2 = ()2,和.这就是我们的结果.所以Josephus以及犹太罗马战争留给我们一些有趣的广义递归式.1. Recurrent ProblemsThis chapter explores three sample problems that give a feel for whats to come. They have two traits in common: Theyve all been invective-gated repeatedly by mathematicians; and their solutions all use the idea of recurrence, in which the solution to each problem depends on the solutions to smaller instances of the same problem.2. The Josephus ProblemIn our all introductory example is a variant of an ancient problem named for Flavins Josephus, a variation, we start with people numbered 1 to n around a circle, and we eliminate every second remaining person until only one survives. For example, heres the starting conguration for =10:The elimination order is2, 4, 6, 8, 10, 3, 7, 1, 9, so 5survives. The problem:Determine the survivors number,().We just saw that(10) =5. We might conjecture that() =2when nis even; and the case =2supports the conjecture:(2) =1. But a few other small cases dissuade us the conjecture fails for =4 and =6.Its back to the drawing board; lets try to make a better guess.()always seems to be odd. And in fact, theres a good reason for this: The rest trip around the circle eliminates all the even numbers. Furthermore, if n itself 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 lets suppose that we have 2 people originally. After the rest go-round, were left withnd3will be the next to go. This is just like starting out with people, except that each persons number has been doubled and decreased by1. That is,(2) = 2()-1; when 1:We can now go quickly to largen. For example, we know that (10) =5, so(20) = 2(10)-1 = 2*5-1 = 9:Similarly (40) = 17，and we can deduce that (5*)= +1But what about the odd case? With2+1 people, it turns out that person number1is wiped out just after person number 2, and were left with Again we almost have the original situation with people, but this time their numbers are doubled and increased by1. Thus(2+ 1) = 2() + 1; for 1;Combining these equations with J(1) = 1 gives us a recurrence that denes J in all cases:(1) = 1;(2) = 2()-1; for 1; (2+ 1) = 2() + 1; for 1;Instead of getting ()from(-1), this recurrence is much more effcient ,because it reduces by a factor of2or more each time its applied. We could compute (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 well 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);() is always 1at the beginning of a group and it increases by 2 within a group. So if we write in the form =+, whereis the largest power of 2not exceedingand where l is whats left, the solution to our recurrence seems to be(+)=2+1 for 0 and 0 （2）(Notice that if, the remainder l =- satises 00and+=2 , then l is even and(+)=2(+/2)-1=2(2/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 +=2+1.We might also note that(1) implies the relation(2+1)-(2)=2Either way, the induction is complete and (2) is established.To illustrate solution (1.9), lets compute(100). In this case we have100 =26+ 36, so (100) = 236 + 1 = 73Now that weve done the hard stuff (solved the problem) we seek the soft: Every solution to a problem can be generalized so that it applies to a wider class of problems. Once weve learned a technique, its 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 problems.Powers of 2 played an important role in our finding the solution, so its natural to look at the radix 2 representations of n and (). Suppose n s binary expansion is;that is,=where each is either 0or1and where the leading bit is 1. Recalling that=+, we have, successively,22+1()(The last step follows because() = 2+ 1 and becauseand.)We have proved that; (3)that is, in the lingo of computer programming, we get() from n by doing a one-bit cyclic shift left! Magic. For example, if=100=(1100100)2 then() =(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 n and iterate the function +1 times, were doing +1 one-bit cyclic shifts; so, since nis an (+1)-bit number, we might expect to end up with n again. But this doesnt quite work. For instance=13 we have(1101)2=(1011)2, but then(1011)2=(111)2, and the process breaks down; the 0disappears when it becomes the leading bit.In fact, J() must always be , by dentition, since() is the survivors number; hence if () we can never get back up ton by continuing to iterate.Repeated application of J produces a sequence of decreasing values that eventually reach a fixed point, where () = .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 all1s whose value is -1 where v() is the number of 1bits in the binary representation of. Thus, since v(13) = 3，we have2 or more (.(13).) = 23 1 = 7;Similarly8or more(.(101101101101011)2.) = 210 1 = 1023;Curious, but true.Lets return briefly to our rest guess, that () =/2 when nis even. This is obviously not true in general, but we can now determine exactly when it is true:() = =2;2+ 1 =(+l)/2l =1/3(-2)If this number l =1/3(-2) is an integer, then n=+l will be a solution, because l will be less than 2m. Its not hard to verify that -2 is a multiple of3whenmis odd, but not when mis even. (We will study such things in Chapter 4.) Therefore there are in nicely many solutions to the equation() =/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 the function pretty well; the next step is to generalize it. What would have happened if our problem had produced a recurrence that was something like (1), but with different constants? Then we might not have been lucky enough to guess the solution, because the solution might have been really weird. Lets investigate this by introducing constants ， and and trying to need a closed form for the more general recurrence(1) = ;(2) = 2() + , for 1;（4）(2 + 1) = 2() + , for 1.(Our original recurrence had = 1， = 1 and = 1.) Starting with (1) = and working our way up, we can construct the following general table for small values of:It seems that s cosentient is s largest power of 2. Furthermore, between powers of2, s cosentient decreases by 1down to0 and s increases by 1 up from0. Therefore if we express () in the form () =() +() +(), （6）by separating out its dependence on ， and , it seems that() = 2;() = 2 1 l;() = l.（7）Here, as usual, = 2+ l and 0 l 2，for 1.Its not terribly hard to prove (1.13) and (1.14) by induction, but the calculations are messy and uninformative. Fortunately theres a better way to proceed, by choosing particular values and then combining them. Lets illustrate this by considering the special case = 1， = = 0 when f() is supposed to be equal to (): Recurrence (1.11) becomes(1) = 1;(2) = 2()；for 1;(2+ 1) = 2()；for 1;Sure enough, its true (by induction on m) that ,(2 + l) = 2Next, lets use recurrence (1.11) and solution (1.13)in reverse, by starting with a simple function ()and seeing if there are any constants(, , ) that will dene it. Plugging the constant function f() =1 into (1.11) says that A neat idea!1 = ;2 = 2 1 + ;3 = 2 1 + ;hence the values(, , ) = (1, 1, 1) satisfying these equations will yield () () () =() = 1. Similarly, we can plug in f() =:1 = ;2 = 2 + ;2 + 1 = 2 + ;These equations hold for allwhen = 1， = 2 and = 1, so we dont need to prove by induction that these parameters will yield f() =. We already know that f() = will be the solution in such a case, because the recurrence (1.11) uniquely denes f() for every value of . And now were essentially done! We have shown that the functions (),(), and () of (1.13), which solve (1.11) in general, satisfy the equations() = 2,or = 2+ l and 0 l 2;() () () = 1;() +() =.Our conjectures in (1.14) follow immediately, since we can solve these equations to get () =() = l and () =() 1 () = 2 1 l.This approach illustrates a surprisingly useful repertoire method for solving recurrences. First we need settings of general parameters for which we know the solution; this gives us a repertoire of special cases that we can solve.Then we obtain the general case by combining the special cases. We need as many independent special solutions as there are independent parameters (in this case three, for ， and ) Exercises 16 and 20 provide further examples of the repertoire approach.We know that the original J-recurrence has a magical solution, in binary: ()2 = ()2, when .which is our answer.Thus Josephus and the Jewish Roman war have led us to some interesting general recurrences.