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

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

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

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

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

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

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

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

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

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

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

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

60、方法。首先，我們證明當(dāng)n為最小值n0時命題成立，這稱為基礎(chǔ)。然后我們需要證明n≥n0時的命題成立，先假設(shè)n0到n?1之間的值已經(jīng)被證明成立，這成為歸納。這樣的證明提供無限多的結(jié)果，只用數(shù)量有限的工作。</p><p>　　數(shù)學(xué)歸納法為遞推提供了完美的解決準(zhǔn)備。在我們的案例中，從（1.1）很容易得到（1.2）：因為T0＝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>　　因此對于（1.2），問題規(guī)模為n也成立。我們關(guān)于Tn的問題已成功結(jié)束。</p><p>　　當(dāng)然，牧師的任務(wù)還沒有結(jié)束，他們?nèi)匀槐M職盡責(zé)地移動磁盤，還需要一段時間，因為對于n = 64需要移動264-1步（約18×10006）。即使以不可能速率每微秒移動一次，他

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

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

64、lt;p>　　分析漢諾塔可以找到問題的正確答案，但它要求一個“歸納飛躍”，這里的解答依賴于僥幸的猜測。這本書的一個主要目標(biāo)是解釋如何解遞歸式而并不要求讀者具有超人的洞察力。例如我們會看到遞歸表達式（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)，這個遞歸式的解是Un = 2n。因此Tn = 2n