具体数学--外文翻译.doc

本科生毕业论文（设计）翻译

Concrete Mathematics

R. L. Graham, D. E. Knuth, O. Patashnik

《Concrete Mathematics》，1.3 THE JOSEPHUS PROBLEM
R. L. Graham, D. E. Knuth, O. Patashnik
Sixth 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 =- 满足不等式0≤<2M+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.回想一下=+我们先后得到如下表达式，

2
2+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以及() =()−1−C() = 2.
这个过程已经接近于展示一个惊奇、有用的repertoire method来解决递归式问题.首先，我们要寻找我们的解决方法中已知的通用参数;这给予了我们能解得各个部分的特例.我们需要跟独立参数数量(在这个例子中是三个α,β和γ)同样多的独立的特解.练习16和20提供了更多的相关例子.我们知道原来的递归式J有一个神奇的解法,也就是二进制：
()2 = ()2,和.
这就是我们的结果.
所以Josephus以及犹太—罗马战争留给我们一些有趣的广义递归式.

1. Recurrent Problems
This chapter explores three sample problems that give a feel for what's to come. They have two traits in common: They've 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 Problem
In 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, here's the starting conguration for =10:

The elimination order is2, 4, 6, 8, 10, 3, 7, 1, 9, so 5survives. The problem:Determine the survivor's 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.

It's back to the drawing board; let's try to make a better guess.()always seems to be odd. And in fact, there's 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 let's suppose that we have 2 people originally. After the rest go-round, we're left with

nd3will be the next to go. This is just like starting out with people, except that each person's 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*)= +1
But what about the odd case? With2+1 people, it turns out that person number1is wiped out just after person number 2, and we're 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 it's 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 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);() 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 what's left, the solution to our recurrence seems to be
(+)=2+1 for ≥0 and 0≤< （2）
(Notice that if≥<, the remainder l =- satises 0≤<-=.)
We must now prove (2). As in the past we use induction, but this time the induction is on m. When =0 we must have l =0; thus the basis of reduces to (1) = 1, which is true. The induction step has two parts, depending on whether l is even or odd. If m >0and+=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)=2
Either way, the induction is complete and (2) is established.
To illustrate solution (1.9), let's compute(100). In this case we have100 =26+ 36, so
(100) = 236 + 1 = 73
Now that we've 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 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 problems.
Powers of 2 played an important role in our finding the solution, so it's 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,

2
2+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, we're doing +1 one-bit cyclic shifts; so, since nis an (+1)-bit number, we might expect to end up with n again. But this doesn't 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 survivor's number; hence if () fixed point will be: Iterating the function enough times will always produce a pattern of all1's whose value is -1 where v() is the number of 1bits in the binary representation of. Thus, since v(13) = 3，we have
2 or more
((...(13)...)) = 23 − 1 = 7;
Similarly
8or more
((...(101101101101011)2.)) = 210 − 1 = 1023;
Curious, but true.
Let's 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)/2
l =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. It's 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. Let's 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.
It's not terribly hard to prove (1.13) and (1.14) by induction, but the calculations are messy and uninformative. Fortunately there's a better way to proceed, by choosing particular values and then combining them. Let's 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, it's true (by induction on m) that ,(2 + l) = 2
Next, let's 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 don't 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 we're 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.
目 录
第一章　项目概要 1
1.1 项目背景 1
1.2 项目建设内容与工期 2
1.3 投资估算和资金筹措 3
1.3.1投资估算 3
1.3.2 资金筹措方案 3
1.4 效益分析 4
1.4.1 经济效益 4
1.4.2 社会效益 5
1.4.3 生态效益 5
第二章 项目区概况 6
2.1 自然概况 6
2.2 社会经济状况 8
第三章 项目建设的必要性和可行性 10
3.1 项目区农业发展的制约因素 10
3.2项目建设的必要性 10
3.3 项目建设的可行性 13
第四章 水资源评价及水利工程设施 14
4.1 项目区水资源概况 14
4.2 水利工程措施 14
第五章 规划设计 18
5.1 指导思想 18
5.2 选项原则 18
5.3 建设标准 18
5.4 道路建设 19
5.5 建设规模 20
5.6 规划布局 20
第六章 开发任务与开发原则 22
6.1 开发任务 22
6.2 开发原则 22