應(yīng)用數(shù)學(xué)專業(yè)外文翻譯

1、<p>　　本科畢業(yè)論文外文翻譯</p><p>　外文譯文題目（中文） ：具體數(shù)學(xué)：漢諾塔問題</p><p>　　1 Recurrent Problems</p><p>　　THIS CHAPTER EXPLORES three sample problems that give a feel for what’s to come. They ha

2、ve two traits in common: They’ve 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

3、 of the same problem.</p><p>　　1.1 THE TOWER OF HANOI</p><p>　　Let’s look first at a neat little puzzle called the Tower of Hanoi,invented by the French mathematician Edouard Lucas in 1883. We a

4、re given a tower of eight disks, initially stacked in decreasing size on one of three pegs:</p><p>　　The objective is to transfer the entire tower to one of the other pegs, moving</p><p>　　only

5、one disk at a time and never moving a larger one onto a smaller.</p><p>　　Lucas furnished his toy with a romantic legend about a much larger Tower of Brahma, which supposedly has 64 disks of pure gold restin

6、g 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 p

7、riests reportedly work day and night at their task. When they finish, the Tower will crumble and the world will end. </p><p>　　It's not immediately obvious that the puzzle has a solution, but a little

8、 thought (or having seen the problem before) convinces us that it does. Now the question arises：What's the best we can do？That is，how many moves are necessary and sufficient to perform the task?</p><p>　

9、　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；let's consider what happens if there are TL disks.</p><p>　　One advan

10、tage of this generalization is that we can scale the problem down even more. In fact, we'll see repeatedly in this book that it's advantageous to LOOK AT SMALL CASES first. It's easy to see how to transfer a

11、tower that contains only one or two disks. And a small amount of experimentation shows how to transfer a tower of three.</p><p>　　The next step in solving the problem is to introduce appropriate notation：<

12、;/p><p>　　NAME ANO CONQUER. Let's say that Tn is the minimum number of moves that will transfer n disks from one peg to another under Lucas's rules. Then T1 is obviously 1 , and T2 = 3.</p><p

13、>　　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

14、think small,because general patterns are easier to perceive when the extreme cases are well understood(even when they are trivial).</p><p>　　But now let's change our perspective and try to think big；how

15、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 t

16、ransferring n disks in general：We first transfer the n?1 smallest to a different peg (requiring Tn-1 moves), then move the largest (requiring one move), and finally transfer the n?1 smallest back onto the largest (requ&l

17、t;/p><p>　　Tn ≤2Tn—1+1， for n > 0. </p><p>　　This formula uses '≤' instead of '=' because our construction proves only that 2Tn—1+1 moves suffice; we haven't shown that

18、 2Tn—1+1 moves are necessary. A clever person might be able to think of a shortcut. </p><p>　　But is there a better way? Actually no. At some point we must move the largest disk. When we do, the n?1 smallest

19、 must be on a single peg, and it has taken at least Tn?1 moves to put them there. We might move the largest disk more than once, if we're not too alert. But after moving the largest disk for the last time, we must tr

20、ans fr the n?1 smallest disks (which must again be on a single peg)back onto the largest；this too requires Tn?1 moves. Hence</p><p>　　Tn ≥ 2Tn—1+1， for n > 0. </p><p>　　These two inequa

21、lities, together with the trivial solution for n = 0, yield</p><p><b>　　T0=0；</b></p><p>　　Tn=2Tn—1+1 , for n > 0. (1.1)</p><p>　　(Notice that the

22、se 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 haven't m

23、ade a foolish error. Such checks will be especially valuable when we get into more complicated maneuvers in later chapters.)</p><p>　　A set of equalities like (1.1) is called a recurrence (a. k. a. recurrenc

24、e 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

25、 a boundary value to be complete.</p><p>　　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 onl

26、y gives indirect, "local" information. A solution to the recurrence would make us much happier. That is, we'd like a nice, neat, "closed form" for Tn that lets us compute it quickly，even for lar

27、ge n. With a closed form, we can understand what Tn really is.</p><p>　　So how do we solve a recurrence? One way is to guess the correct solution,</p><p>　　then to prove that our guess is correc

28、t. And our best hope for guessing the solution is to look (again) at small cases. So we compute, successively,</p><p>　　T3 = 2×3+1= 7; T4 = 2×7+1= 15; T5 = 2×15+1= 31; T6 = 2×31+1= 63. &l

29、t;/p><p>　　Aha! It certainly looks as if</p><p>　　Tn = 2n?1， for n≥0. (1.2)</p><p>　　At least this works for n≤6. </p><p>　　Mathematical induction i

30、s a general way to prove that some statement about</p><p>　　the integer n is true for all n≥n0. First we prove the statement when n has its smallest value,no; this is called the basis. Then we prove the stat

31、ement for n > n0,assuming that it has already been proved for all values between n0 and n?1, inclusive; this is called the induction. Such a proof gives infinitely many results with only a finite amount of work.<

32、/p><p>　　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 = 20?1= 0.And the induction follows for n > 0 if we

33、assume that (1.2) holds when n is replaced by n?1：</p><p>　　Tn= 2Tn+1= 2(2n?1?1)+1=2n?1. </p><p>　　Hence (1.2) holds for n as well. Good! Our quest for Tn has ended successfully.</p><

34、p>　　Of course the priests' task hasn't ended；they're still dutifully moving disks,and will be for a while, because for n = 64 there are 264?1 moves (about 18 quintillion). Even at the impossible rate of on

35、e move per microsecond, they will need more than 5000 centuries to transfer the Tower of Brahma. Lucas's original puzzle is a bit more practical, It requires 28?1 = 255 moves, which takes about four minutes for the q

36、uick of hand.</p><p>　　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

37、stages：</p><p>　　1 Look at small cases. This gives us insight into the problem and helps us in stages 2 and 3.</p><p>　　2 Find and prove a mathematical expression for the quantity of interes

38、t.</p><p>　　For the Tower of Hanoi, this is the recurrence (1.1) that allows us, given the inclination，to compute Tn for any n. </p><p>　　3 Find and prove a closed form for our mathematical

39、 expression.For the Tower of Hanoi, this is the recurrence solution (1.2).</p><p>　　The third stage is the one we will concentrate on throughout this book. In fact, we'll frequently skip stages I and

40、2 entirely, because a mathematical expression will be given to us as a starting point. But even then, we'll be getting into subproblems whose solutions will take us through all three stages.</p><p>　　Our

41、 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 recu

42、rrences without being clairvoyant. For example, we'll see that recurrence (1.1) can be simplified by adding 1 to both sides of the equations：</p><p>　　T0 + 1= 1;</p><p>　　Tn + 1= 2Tn-1+ 2,

43、 for n >0. </p><p>　　Now if we let Un = Tn+1，we have</p><p><b>　　U0 =1；</b></p><p>　　Un= 2Un-1， for n > 0. (1.3) </p><p>

44、;　　It doesn't take genius to discover that the solution to this recurrence is just Un = 2n；hence Tn = 2n ?1. Even a computer could discover this.</p><p>　　Concrete Mathematics</p><p>　　R. L.

45、 Graham, D. E. Knuth, O. Patashnik</p><p>　　《Concrete Mathematics》，1.1 ，The Tower Of Hanoi </p><p>　　R. L. Graham, D. E. Knuth, O. Patashnik</p><p>　　Sixth printing, Printed in the

46、United States of America </p><p>　　1989 by Addison-Wesley Publishing Company，Reference 1-4 pages</p><p><b>　　具體數(shù)學(xué)</b></p><p>　　R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克</p><p&

47、gt;　　《具體數(shù)學(xué)》，1.1，漢諾塔</p><p>　　R.L.格雷厄姆，D.E.克努特，O.帕塔希尼克</p><p>　　第一版第六次印刷于美國，</p><p>　　韋斯利出版公司，1989年，引用1-4頁</p><p><b>　　1 遞歸問題</b></p><p>　　本章將通

48、過對(duì)三個(gè)樣本問題的分析來探討遞歸的思想。他們有兩個(gè)共同特點(diǎn)：一是他們都被數(shù)學(xué)家反復(fù)研究;二是他們的解都使用遞歸的思想,即每一個(gè)樣本問題的解都依賴于相同問題的幾個(gè)較小的樣本問題的解。</p><p><b>　　1.1 漢諾塔</b></p><p>　　讓我們先來看一個(gè)巧妙機(jī)智的小問題稱為漢諾塔,它是由法國數(shù)學(xué)家愛德華·盧卡斯在1883年提出來的。題目是有

49、一個(gè)具有八個(gè)盤所堆成的塔，最初按尺寸從小到大的順序堆放在三根桿中的一個(gè)上：</p><p>　　目標(biāo)是將整個(gè)塔上的盤轉(zhuǎn)移到另一根桿上，每次只能移動(dòng)一個(gè)盤并且在移動(dòng)的過程中不允許將大盤放在小盤之上。</p><p>　　盧卡斯將他的這個(gè)發(fā)現(xiàn)運(yùn)用到一個(gè)虛構(gòu)的傳說故事，一個(gè)更大的塔稱為梵天塔。據(jù)稱這個(gè)塔擁有64個(gè)純金磁盤，按順序放在三個(gè)金剛針上。最初上帝將這些黃金磁盤放在第一針上，并下令讓一群牧

50、師根據(jù)上面講的規(guī)則把它們移動(dòng)到第三根針上。據(jù)說，牧師們不分晝夜的忙碌這項(xiàng)工作，到他們完成那一天，塔將碎裂世界也將到盡頭。</p><p>　　這個(gè)問題的解并不是顯而易見的，但是仔細(xì)想一想(或者之前看過漢諾塔的問題)也不是沒有解決方法。現(xiàn)在問題出現(xiàn)了：對(duì)于這個(gè)問題最好的解法是什么？也就是說，需要移動(dòng)多少次才能完成這個(gè)任務(wù)。</p><p>　　解這樣一個(gè)問題的最好辦法是要一般化一下，梵天塔有

51、64個(gè)磁盤而漢諾塔有8個(gè);讓我們考慮如果有n個(gè)磁盤會(huì)發(fā)生什么情況。</p><p>　　這種一般化的一個(gè)優(yōu)勢是，我們可以把問題的規(guī)模擴(kuò)展，用來處理更多的樣本。事實(shí)上我們將反復(fù)從這本書里發(fā)現(xiàn)先處理小規(guī)模問題的好處。例如，移動(dòng)那些只有一兩個(gè)盤的塔的問題的解是很容易得到，甚至于可以使用少量測驗(yàn)就能說明如何移動(dòng)三張盤的塔。</p><p>　　解決這個(gè)問題的下一步是引入適當(dāng)?shù)姆?hào)：取名并求解。根據(jù)

52、盧卡斯的規(guī)則，假設(shè)Tn是將n個(gè)盤從一根桿移動(dòng)到另一根桿上最小的移動(dòng)步數(shù)。則T1顯然是1，T2= 3。我們還可以輕易的得到另一個(gè)值，考慮到最小的問題規(guī)模，顯然是T0= 0，因?yàn)檗D(zhuǎn)移n＝0的塔不需要移動(dòng)步數(shù)。精明的數(shù)學(xué)家不為思索小的情形而感到害臊,因?yàn)樵跇O端情形下，小規(guī)模問題往往是容易理解的(即使它們有時(shí)候是無意義的)。</p><p>　　但現(xiàn)在，我們需要改變這種觀點(diǎn)，并盡量往更大規(guī)模的問題考慮;怎樣去轉(zhuǎn)移大型塔？

53、在三個(gè)磁盤的移動(dòng)問題上，成功的做法是先將最上面的兩個(gè)盤移動(dòng)到中間桿上，然后移動(dòng)第三個(gè)盤，接著把其他兩個(gè)移到第三個(gè)盤上面。這給了我們一個(gè)關(guān)于如何移動(dòng)n個(gè)磁盤的思路：首先將第n?1個(gè)盤按最小步數(shù)移動(dòng)到一個(gè)不同的柱上（需要Tn-1步數(shù)），然后移動(dòng)最大的那個(gè)盤（需要一步），并最后將第n?1個(gè)盤轉(zhuǎn)移到最大盤上面（需要另外的 Tn-1步）。因此，我們最多可以使用2Tn-1+1步來移動(dòng)n個(gè)磁盤（n>0）：</p><p>

54、;　　Tn ≤ 2 Tn-1+1， (n＞0)．</p><p>　　此公式使用'≤'而不是'='，因?yàn)樯鲜龇治鰞H能證明2Tn-1+1步移動(dòng)是充分的;并沒有說明2Tn-1+1步移動(dòng)是必要的。聰明人可能會(huì)想到的這樣的一個(gè)捷徑。</p><p>　　但有沒有一個(gè)更好的辦法呢？當(dāng)然沒有。在某些時(shí)候，我們必須移動(dòng)最大的磁盤。當(dāng)我們移動(dòng)最大磁盤時(shí)，其他n?1個(gè)較小

55、的盤必須在一根桿上，并且至少需要Tn-1個(gè)步數(shù)來把它們移動(dòng)到那里。如果我們不是太留心的話，有時(shí)候最大的磁盤可能會(huì)被移動(dòng)不止一次。但在最后一次移動(dòng)最大的磁盤后，我們必須要移動(dòng)n-1個(gè)較小磁盤（必須在一根柱上）到最大磁盤上面，這也需要Tn-1步數(shù)。因此,</p><p>　　Tn ≥ 2 Tn-1+1， (n＞0)． </p><p>　　這兩個(gè)不等式，與退化解n = 0一

56、起，可得到</p><p><b>　　T0 = 0</b></p><p>　　Tn = 2 Tn-1+1， (n＞0)． （1.1） （請(qǐng)注意，這個(gè)公式是與已知值T1=1和T2=3一致的。我們對(duì)于小規(guī)模的樣本的研究，不僅有助于我們推導(dǎo)出通用的公式，它也把檢驗(yàn)是否推導(dǎo)有誤變得更加簡單。這種檢查

57、是很有價(jià)值的，在后面的章節(jié)中做更復(fù)雜的演算時(shí)就會(huì)體現(xiàn)出來。）</p><p>　　像等式（1.1）那樣一組等式被稱為遞歸（又名遞推關(guān)系或遞歸關(guān)系）。它給出了一個(gè)邊界值和根據(jù)叫造紙表達(dá)一般只的一個(gè)方程。我們把一般方程單獨(dú)作為一個(gè)遞歸，但是在技術(shù)上，它需要一個(gè)邊界值來解決。</p><p>　　遞推關(guān)系，讓我們可以計(jì)算我們?nèi)魏蝞的Tn值。但當(dāng)n很大時(shí)，沒有人真的喜歡使用遞推;當(dāng)n很大時(shí)需要的計(jì)

58、算時(shí)間太長。遞推只能提供間接的局部的信息。遞推的解使我們很開心。也就是說，我們想要一個(gè)良好的，簡潔的“封閉形式”，讓我們能夠快速計(jì)算即使是大的n。依據(jù)一個(gè)封閉的形式，我們可以了解到真正的Tn。</p><p>　　那么，我們?nèi)绾谓鉀Q遞推呢？一種方法是猜測正確的解，然后，證明我們的猜測是正確的。而且我們最希望的猜測解是看小規(guī)模情況下的情況。因此，我們依次計(jì)算T3=2×3+1=7；T4=2×7+1

59、=15；T5=2×15+1=31；T6=2×31+1=63。確實(shí)滿足，</p><p>　　Tn =2n?1， (n≥0). （1.2）</p><p>　　至少對(duì)于n≤6成立。</p><p>　　數(shù)學(xué)歸納法是證明某個(gè)命題當(dāng)整數(shù)n(n≥n0時(shí))成立的一個(gè)一般性

60、方法。首先，我們證明當(dāng)n為最小值n0時(shí)命題成立，這稱為基礎(chǔ)。然后我們需要證明n≥n0時(shí)的命題成立，先假設(shè)n0到n?1之間的值已經(jīng)被證明成立，這成為歸納。這樣的證明提供無限多的結(jié)果，只用數(shù)量有限的工作。</p><p>　　數(shù)學(xué)歸納法為遞推提供了完美的解決準(zhǔn)備。在我們的案例中，從（1.1）很容易得到（1.2）：因?yàn)門0＝20-1＝0，所以基礎(chǔ)是微不足道的。假設(shè)當(dāng)n被n?1取代后（1.2）成立且n>0：<

61、/p><p>　　Tn= 2Tn-1+1= 2(2n?1?1)+1=2n?1.</p><p>　　因此對(duì)于（1.2），問題規(guī)模為n也成立。我們關(guān)于Tn的問題已成功結(jié)束。</p><p>　　當(dāng)然，牧師的任務(wù)還沒有結(jié)束，他們?nèi)匀槐M職盡責(zé)地移動(dòng)磁盤，還需要一段時(shí)間，因?yàn)閷?duì)于n = 64需要移動(dòng)264-1步（約18×10006）。即使以不可能速率每微秒移動(dòng)一次，他

62、們也需要5000多世紀(jì)的時(shí)間轉(zhuǎn)移梵天塔。盧卡斯最初的難題實(shí)際一些，需要28-1 = 255的步數(shù)，快的話需時(shí)約4分鐘。</p><p>　　漢諾塔的遞推思想在解決各種應(yīng)用提出的問題中是很典型的。在尋找一個(gè)封閉的表達(dá)式來解決像Tn這樣有趣的問題時(shí)，我們經(jīng)歷了三個(gè)階段：</p><p>　　1看小規(guī)模問題。這一步讓我們深入了解問題，并為第2和第3階段提供幫助。</p><p

63、>　　2找到并證明關(guān)系量的一個(gè)數(shù)學(xué)表達(dá)式。對(duì)于漢諾塔問題，遞推表達(dá)式（1.1），讓我們可以計(jì)算任意n的Tn值。</p><p>　　3為我們的數(shù)學(xué)表達(dá)找到并證明一個(gè)封閉形式，對(duì)于漢諾塔問題，這是遞推的解(1.2)。第三階段是我們將在整本書都集中精力研究的一個(gè)階段。事實(shí)上，我們經(jīng)常會(huì)跳過階段1和2，因?yàn)槲覀儞碛幸粋€(gè)作為起點(diǎn)的數(shù)學(xué)表達(dá)式。但即使這樣，子問題的解仍然將通過所有的三個(gè)階段。</p>&

64、lt;p>　　分析漢諾塔可以找到問題的正確答案，但它要求一個(gè)“歸納飛躍”，這里的解答依賴于僥幸的猜測。這本書的一個(gè)主要目標(biāo)是解釋如何解遞歸式而并不要求讀者具有超人的洞察力。例如我們會(huì)看到遞歸表達(dá)式（1.1）通過等式兩邊加1來簡化：</p><p>　　T0 + 1= 1;</p><p>　　Tn + 1= 2Tn-1+ 2, (n >0).</p><p

65、>　　現(xiàn)在我們讓Un = Tn-1+1，可以得到， </p><p><b>　　U0 =1；</b></p><p>　　Un= 2Un-1， (n > 0). （1.3）</p><p>　　不難發(fā)現(xiàn)，這個(gè)遞歸式的解是Un = 2n。因此Tn = 2n