应用数学专业外文翻译.doc

本科毕业论文外文翻译外文译文题目（中文） ：具体数学：汉诺塔问题学 院: 专 业: 学 号:学生姓名:指导教师:日 期: 二一二年六月武汉科技大学本科毕业论文外文翻译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 investigated 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.1.1 THE TOWER OF HANOI Lets look first at a neat little puzzle called the Tower of Hanoi,invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs:The objective is to transfer the entire tower to one of the other pegs, movingonly one disk at a time and never moving a larger one onto a smaller.Lucas furnished his toy with a romantic legend about a much larger Tower of Brahma, which supposedly has 64 disks of pure gold resting on three diamond needles. At the beginning of time, he said, God placed these golden disks on the first needle and ordained that a group of priests should transfer them to the third, according to the rules above. The priests reportedly work day and night at their task. When they finish, the Tower will crumble and the world will end. Its not immediately obvious that the puzzle has a solution, but a little thought (or having seen the problem before) convinces us that it does. Now the question arises：Whats the best we can do？That is，how many moves are necessary and sufficient to perform the task?The best way to tackle a question like this is to generalize it a bit. The Tower of Brahma has 64 disks and the Tower of Hanoi has 8；lets consider what happens if there are TL disks.One advantage of this generalization is that we can scale the problem down even more. In fact, well see repeatedly in this book that its advantageous to LOOK AT SMALL CASES first. Its easy to see how to transfer a tower that contains only one or two disks. And a small amount of experimentation shows how to transfer a tower of three. The next step in solving the problem is to introduce appropriate notation：NAME ANO CONQUER. Lets say that Tn is the minimum number of moves that will transfer n disks from one peg to another under Lucass rules. Then T1 is obviously 1 , and T2 = 3. We can also get another piece of data for free, by considering the smallest case of all：Clearly T0 = 0，because no moves at all are needed to transfer a tower of n = 0 disks! Smart mathematicians are not ashamed to think small,because general patterns are easier to perceive when the extreme cases are well understood(even when they are trivial).But now lets change our perspective and try to think big；how can we transfer a large tower? Experiments with three disks show that the winning idea is to transfer the top two disks to the middle peg, then move the third, then bring the other two onto it. This gives us a clue for transferring n disks in general：We first transfer the n1 smallest to a different peg (requiring Tn-1 moves), then move the largest (requiring one move), and finally transfer the n1 smallest back onto the largest (requiring another Tn-1 moves). Thus we can transfer n disks (for n 0)in at most 2Tn-1+1 moves： Tn 2Tn1+1， for n 0. This formula uses instead of = because our construction proves only that 2Tn1+1 moves suffice; we havent shown that 2Tn1+1 moves are necessary. A clever person might be able to think of a shortcut. But is there a better way? Actually no. At some point we must move the largest disk. When we do, the n1 smallest must be on a single peg, and it has taken at least Tn1 moves to put them there. We might move the largest disk more than once, if were not too alert. But after moving the largest disk for the last time, we must trans fr the n1 smallest disks (which must again be on a single peg)back onto the largest；this too requires Tn1 moves. Hence Tn 2Tn1+1， for n 0. These two inequalities, together with the trivial solution for n = 0, yield T0=0； Tn=2Tn1+1 , for n 0. (1.1)(Notice that these formulas are consistent with the known values T1= 1 and T2= 3. Our experience with small cases has not only helped us to discover a general formula, it has also provided a convenient way to check that we havent made a foolish error. Such checks will be especially valuable when we get into more complicated maneuvers in later chapters.) A set of equalities like (1.1) is called a recurrence (a. k. a. recurrence relation or recursion relation). It gives a boundary value and an equation for the general value in terms of earlier ones. Sometimes we refer to the general equation alone as a recurrence, although technically it needs a boundary value to be complete. The recurrence allows us to compute Tn for any n we like. But nobody really like to compute from a recurrence，when n is large；it takes too long. The recurrence only gives indirect, local information. A solution to the recurrence would make us much happier. That is, wed like a nice, neat, closed form for Tn that lets us compute it quickly，even for large n. With a closed form, we can understand what Tn really is. So how do we solve a recurrence? One way is to guess the correct solution,then to prove that our guess is correct. And our best hope for guessing the solution is to look (again) at small cases. So we compute, successively,T3 = 23+1= 7; T4 = 27+1= 15; T5 = 215+1= 31; T6 = 231+1= 63. Aha! It certainly looks as if Tn = 2n1， for n0. (1.2)At least this works for n6. Mathematical induction is a general way to prove that some statement aboutthe integer n is true for all nn0. First we prove the statement when n has its smallest value,no; this is called the basis. Then we prove the statement for n n0,assuming that it has already been proved for all values between n0 and n1, inclusive; this is called the induction. Such a proof gives infinitely many results with only a finite amount of work. Recurrences are ideally set up for mathematical induction. In our case, for example，(1.2) follows easily from (1.1)：The basis is trivial，since T0 = 201= 0.And the induction follows for n 0 if we assume that (1.2) holds when n is replaced by n1： Tn= 2Tn+1= 2(2n11)+1=2n1. Hence (1.2) holds for n as well. Good! Our quest for Tn has ended successfully. Of course the priests task hasnt ended；theyre still dutifully moving disks,and will be for a while, because for n = 64 there are 2641 moves (about 18 quintillion). Even at the impossible rate of one move per microsecond, they will need more than 5000 centuries to transfer the Tower of Brahma. Lucass original puzzle is a bit more practical, It requires 281 = 255 moves, which takes about four minutes for the quick of hand. The Tower of Hanoi recurrence is typical of many that arise in applications of all kinds. In finding a closed-form expression for some quantity of interest like Tn we go through three stages：1 Look at small cases. This gives us insight into the problem and helps us in stages 2 and 3.2 Find and prove a mathematical expression for the quantity of interest. For the Tower of Hanoi, this is the recurrence (1.1) that allows us, given the inclination，to compute Tn for any n. 3 Find and prove a closed form for our mathematical expression.For the Tower of Hanoi, this is the recurrence solution (1.2).The third stage is the one we will concentrate on throughout this book. In fact, well frequently skip stages I and 2 entirely, because a mathematical expression will be given to us as a starting point. But even then, well be getting into subproblems whose solutions will take us through all three stages. Our analysis of the Tower of Hanoi led to the correct answer, but it required an“inductive leap”；we relied on a lucky guess about the answer. One of the main objectives of this book is to explain how a person can solve recurrences without being clairvoyant. For example, well see that recurrence (1.1) can be simplified by adding 1 to both sides of the equations： T0 + 1= 1; Tn + 1= 2Tn-1+ 2, for n 0. Now if we let Un = Tn+1，we have U0 =1； Un= 2Un-1， for n 0. (1.3) It doesnt take genius to discover that the solution to this recurrence is just Un = 2n；hence Tn = 2n 1. Even a computer could discover this. 5武汉科技大学本科毕业论文外文翻译Concrete MathematicsR. L. Graham, D. E. Knuth, O. PatashnikConcrete Mathematics，1.1 ，The Tower Of Hanoi R. 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.1，汉诺塔R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克第一版第六次印刷于美国，韦斯利出版公司，1989年，引用1-4页1 递归问题 本章将通过对三个样本问题的分析来探讨递归的思想。他们有两个共同特点：一是他们都被数学家反复研究;二是他们的解都使用递归的思想,即每一个样本问题的解都依赖于相同问题的几个较小的样本问题的解。1.1 汉诺塔 让我们先来看一个巧妙机智的小问题称为汉诺塔,它是由法国数学家爱德华卢卡斯在1883年提出来的。题目是有一个具有八个盘所堆成的塔，最初按尺寸从小到大的顺序堆放在三根杆中的一个上：目标是将整个塔上的盘转移到另一根杆上，每次只能移动一个盘并且在移动的过程中不允许将大盘放在小盘之上。 卢卡斯将他的这个发现运用到一个虚构的传说故事，一个更大的塔称为梵天塔。据称这个塔拥有64个纯金磁盘，按顺序放在三个金刚针上。最初上帝将这些黄金磁盘放在第一针上，并下令让一群牧师根据上面讲的规则把它们移动到第三根针上。据说，牧师们不分昼夜的忙碌这项工作，到他们完成那一天，塔将碎裂世界也将到尽头。 这个问题的解并不是显而易见的，但是仔细想一想(或者之前看过汉诺塔的问题)也不是没有解决方法。现在问题出现了：对于这个问题最好的解法是什么？也就是说，需要移动多少次才能完成这个任务。 解这样一个问题的最好办法是要一般化一下，梵天塔有64个磁盘而汉诺塔有8个;让我们考虑如果有n个磁盘会发生什么情况。 这种一般化的一个优势是，我们可以把问题的规模扩展，用来处理更多的样本。事实上我们将反复从这本书里发现先处理小规模问题的好处。例如，移动那些只有一两个盘的塔的问题的解是很容易得到，甚至于可以使用少量测验就能说明如何移动三张盘的塔。 解决这个问题的下一步是引入适当的符号：取名并求解。根据卢卡斯的规则，假设Tn是将n个盘从一根杆移动到另一根杆上最小的移动步数。则T1显然是1，T2= 3。我们还可以轻易的得到另一个值，考虑到最小的问题规模，显然是T0= 0，因为转移n0的塔不需要移动步数。精明的数学家不为思索小的情形而感到害臊,因为在极端情形下，小规模问题往往是容易理解的(即使它们有时候是无意义的)。 但现在，我们需要改变这种观点，并尽量往更大规模的问题考虑;怎样去转移大型塔？在三个磁盘的移动问题上，成功的做法是先将最上面的两个盘移动到中间杆上，然后移动第三个盘，接着把其他两个移到第三个盘上面。这给了我们一个关于如何移动n个磁盘的思路：首先将第n1个盘按最小步数移动到一个不同的柱上（需要Tn-1步数），然后移动最大的那个盘（需要一步），并最后将第n1个盘转移到最大盘上面（需要另外的 Tn-1步）。因此，我们最多可以使用2Tn-1+1步来移动n个磁盘（n0）： Tn 2 Tn-1+1， (n0)此公式使用而不是=，因为上述分析仅能证明2Tn-1+1步移动是充分的;并没有说明2Tn-1+1步移动是必要的。聪明人可能会想到的这样的一个捷径。 但有没有一个更好的办法呢？当然没有。在某些时候，我们必须移动最大的磁盘。当我们移动最大磁盘时，其他n1个较小的盘必须在一根杆上，并且至少需要Tn-1个步数来把它们移动到那里。如果我们不是太留心的话，有时候最大的磁盘可能会被移动不止一次。但在最后一次移动最大的磁盘后，我们必须要移动n-1个较小磁盘（必须在一根柱上）到最大磁盘上面，这也需要Tn-1步数。因此, Tn 2 Tn-1+1， (n0) 这两个不等式，与退化解n = 0一起，可得到 T0 = 0 Tn = 2 Tn-1+1， (n0) （1.1） （请注意，这个公式是与已知值T1=1和T2=3一致的。我们对于小规模的样本的研究，不仅有助于我们推导出通用的公式，它也把检验是否推导有误变得更加简单。这种检查是很有价值的，在后面的章节中做更复杂的演算时就会体现出来。） 像等式（1.1）那样一组等式被称为递归（又名递推关系或递归关系）。它给出了一个边界值和根据叫造纸表达一般只的一个方程。我们把一般方程单独作为一个递归，但是在技术上，它需要一个边界值来解决。 递推关系，让我们可以计算我们任何n的Tn值。但当n很大时，没有人真的喜欢使用递推;当n很大时需要的计算时间太长。递推只能提供间接的局部的信息。递推的解使我们很开心。也就是说，我们想要一个良好的