應(yīng)用數(shù)學(xué)專業(yè)外文翻譯-其他專業(yè)-wenkub
2023-01-30 11:08:51 本頁面
【正文】 e two traits in mon: They’ve all been investigated repeatedly by mathematicians。s 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, we39。s say that Tn is the minimum number of moves that will transfer n disks from one peg to another under Lucas39。 instead of 39。t shown that 2Tn—1+1 moves are necessary. A clever person might be able to think of a shortcut. 武漢科技大學(xué)本科畢業(yè)論文外文翻譯 3 But is there a better way? Actually no. At some point we must move the largest disk. When we do, the n?1 smallest 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 we39。 T4 = 27+1= 15。 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， () follows easily from ()： The basis is trivial， since T0 = 20?1= the induction follows for n 0 if we assume that () holds when n is replaced by n?1： Tn= 2Tn+1= 2(2n?1?1)+1=2n?1. Hence () holds for n as well. Good! Our quest for Tn has ended successfully. Of course the priests39。s original puzzle is a bit more practical, It requires 28?1 = 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 closedform 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 () that allows us, given the inclination， to pute Tn for any n. 3 Find and prove a closed form for our mathematical the Tower of Hanoi, this is the recurrence solution (). The third stage is the one we will concentrate on throughout this book. In fact, we39。 Tn + 1= 2Tn1+ 2, for n 0. Now if we let Un = Tn+1， we have U0 =1； Un= 2Un1， for n 0. () It doesn39。 漢諾塔 讓我們先來看一個巧妙機智的小問題稱為漢諾塔 ,它是由法國數(shù)學(xué)家愛德華據(jù)稱這個塔擁有 64 個純金磁盤，按順序放在三個金剛針上?，F(xiàn)在問題出現(xiàn)了：對于這個問題最好的解法是什么？也就是說，需要移動多少次才能完成這個任務(wù)。事實上我們將反復(fù)從這本書里發(fā)現(xiàn)先處理小規(guī)模問題的好處。則 T1顯然是 1， T2= 3。怎樣去轉(zhuǎn)移大型塔？在三個磁盤的移動問題上，成功的做法是先將最上面的兩個盤移動到中間桿上，然后移動第三個盤，接著把其他兩個移到第三個盤上面。而不是 39。聰明人可能會想到的這樣的一個捷徑 。如果我們不是太留心的話，有時候最大的磁盤可能會被移動不止一次。這種檢查是很有價值的，在后面的章節(jié)中做更復(fù)雜的演算時就會體現(xiàn)出來。 遞推關(guān)系，讓我們可以
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1